그래프 알고리즘(다익스트라)

작성일 | In

그래프 알고리즘-1

다익스트라 최단 경로 알고리즘을 알아보자

  • 그래프는 정점(vertex)의 집합과 정점들을 잇는 에지(edge)의 집합으로 구성된다
  • G = <V, E>
  • 만약 에지에 방향이 있다면 방향 그래프, 없으면 무방향 그래프, 에지에 가중치가 있으면 가중 그래프, 없으면 비가중 그래프

그래프는 객체(정점)과 객체 사이의 관계(에지)를 표현 할 수 있다.

다익스트라 최단 경로 알고리즘

보통 g=<v,e> 주어지고 시작 정점과 목적 정점이 주어지고 최소 비용 경로를 구하라고 한다.

다익스트라 알고리즘은 음수 가중치가 없는 그래프에서 동작하는 최단 경로 탐색 알고리즘으로 프림 MST알고리즘을 약간 변경한 형태

  • 프림 알고리즘은 경계로부터 최소 거리를 정점의 거리 값으로 설정하지만, 다익스트라 알고리즘은 시작 정점으로부터 각 정점까지의 전체 거리를 사용한다.
  • 다익스트라 알고리즘은 목적 정점이 나타나면 종료하지만 프림 알고리즘은 모든 정점을 방문해야 종료됨

알고리즘 동작

  1. 모든 정점의 거리 값을 무한대로 초기화. 시작정점은 자기자신까지의 거리이므로 0으로 설정, 그리고 모든 거리 값을 최소 힙H에 추가
  2. 최소 힙H로 부터 정점을 하나 꺼낸다. 이 정점을 U라고 하면, 정점 U는 시작 정점에서 가장 가까운 정점, 만약 U가 목적 정점이면 최단 경로를 찾은 것이므로 알고리즘을 종료
  3. U와 인접한 모든 정점V에 대해, 만약 V의 거리 값이 (U의 거리 값 + (U,V) 에지 가중치) 보다 크면 V까지 다다르는 더 짧은 경로를 찾은 것으로 볼 수 있다. ⇒ V의 거리 값을 (U의 거리 값 + (U,V) 에지 가중치) 값으로 설정
  4. 방문하지 않은 정점이 남아 있다면 2단계로 이동

예제

1753번: 최단경로

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<iostream>
#include<algorithm>
#include<queue>
#include<limits>
#include<functional>

using namespace std;

int V, E, K;
int minValue[20001]; //각 정점의 거리값
vector<pair<int,int>> vertex[20001]; //[연결 하는 노드]<연결된 노드, 가중치>

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    /**
    *우선 순위 큐(최소합) first : 거리값 / second : 정점 번호 => 이거 순서 바뀌면 시간 초과 남
    *정렬이 first 값이 큰 순, 같으면 second 값이 큰순 우선 순위 큐 정렬됨
    */
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> pq;
    int a,b,c;
    cin>>V>>E>>K;
    for (int i = 0; i < E; i++) {
        cin>>a>>b>>c;
        vertex[a].emplace_back(b,c);
    }

    //각 정점의 거리값 최대로 초기화
    for(int i=1; i<=V; i++){
        minValue[i] = numeric_limits<int>::max();
    }

    //시작 정점은 거리값 0으로
    minValue[K]=0;  

    //모든 거리 값을 최소 힙에 추가
    pq.push({0,K});
    while(!pq.empty()){
        int distValue = pq.top().first;
        int nodeNumber = pq.top().second;

        pq.pop();

        //이미 해당 노드의 가중 값이 이미 작으면 루프 돌 필요X
        if(minValue[nodeNumber]<distValue)
            continue;

        //노드와 연결된 노드들 조회
        for (int i = 0; i < vertex[nodeNumber].size(); i++) {
            int nextNodeNumber = vertex[nodeNumber][i].first;
            int nextNodeWeight = vertex[nodeNumber][i].second;

            if(minValue[nextNodeNumber] > distValue+nextNodeWeight){
                minValue[nextNodeNumber] = distValue+nextNodeWeight;
                pq.push({minValue[nextNodeNumber],nextNodeNumber});
            }
        }
    }

    for (int i = 1; i <= V; i++) {
        if(minValue[i]==numeric_limits<int>::max()){
            cout<<"INF"<<"\n";
        }else{
            cout<<minValue[i]<<"\n";
        }
    }
    return 0;
}