최단거리구하기_다익스트라(Dijkstra) 알고리즘

다익스트라 알고리즘에 대한 이해

- 하나의 정점으로 부터 다른 모든 정점까지의 최단거리를 구하는 문제이다.

- 음수 간선이 있는 그래프에서는 사용할 수 없다.

- 우선순위큐를 이용한다.

 

V = 6, E = 7인 다음 그래프에 대하여, 정점 1번으로 부터 다른 모든 정점까지의 거리를 구해보자.

1번으로부터의 거리를 저장하는 dist 배열을 구성하고,  우선순위 큐에 1번 노드의 (거리, 노드번호)를 추가한다.

 

 

 

 

우선순위 큐는 가장 작은 값을 먼저 뱉어내므로, 1번으로부터의 거리가 가장 가까운 노드를 뽑아내면 (0, 1)이 된다.

이 때, 큐에서 뽑아낸 (0, 1)의 정보와 배열의 정보 dist[1] = 0이 일치하므로 1번까지의 거리를 확정한다.

 

1번에서 이동할 수 있는 노드는 2번 노드 뿐이다.

거리가 확정된 노드 1번에서 2번노드로 이동했을 때의 거리가 dist[2] 에 저장된 거리보다 작으므로 해당 값을 갱신시켜준뒤, 우선순위큐에 2번 노드를 추가한다.

즉, dist[1]+3(1번에서 2번까지의 거리) < dist[2](무한대) 이므로 dist[2] = dist[1]+3 = 3 이 되고, 우선순위큐에는 (3, 2)가 추가된다.

 

 

 

다시, 우선순위큐에서 거리가 가장 작은 노드를 뽑으면, (3, 2)가 된다.

이 때, (3, 2)의 정보와 배열의 정보 dist[2] = 3이 일치하므로 2번까지의 거리를 3으로 확정한다.

 

2번 노드에서 이동할 수 있는 노드는 3번, 4번, 5번이다.

dist[2]+1(2번에서 3번) < dist[3](무한대)

dist[2]+4(2번에서 4번) < dist[4](무한대)

dist[2]+5(2번에서 5번) < dist[5](무한대) 

이므로 각각의 dist 배열 값을 갱신하고, 우선순위큐에 노드 정보를 추가한다.

 

 

 

반복해서, 우선순위 큐에서 거리가 가장 작은 노드 정보를 뽑으면, (4, 3)이 된다.

이 때, dist[3] = 4이므로 노드 3번까지의 거리를 4로 확정한다.

 

3번 노드에서 이동할 수 있는 노드는 4번과 6번이다.

dist[3]+2(3번에서 4번) < dist[4]

dist[3]+8(3번에서 6번) < dist[6] 

이므로 각각의 dist 배열 값을 갱신하고 우선순위큐에 노드 정보를 추가한다.

 

 

 

우선순위 큐에서 거리가 가장 짧은 노드를 뽑으면 (6, 4)가 된다.

이 때, dist[4] = 6 으로, (6, 4)와 정보가 일치하므로 노드 4번까지의 거리를 확정한다.

 

4번 노드에서 이동할 수 있는 노드는 2번과 3번이다.

하지만, dist[4]+4(4번에서 2번) > dist[2], dist[4]+2(4번에서 3번) > dist[3] 이므로 두 노드의 거리 정보는 변하지 않는다.

 

 

 

 

우선순위큐에서 가장 가까운 노드 정보를 빼면 (7, 4)인데, dist[4] = 6으로 정보가 일치하지 않으므로 넘어간다.

따라서, 우선순위큐에는 (8, 5) (12, 6) 만 남겨진다.

 

다음으로 가장 가까운 노드 정보를 빼면 (8, 5)가 된다.

dist[5] = 8 이므로 노드 5번까지의 거리를 확정한다.

 

6번노드에서 이동할 수 있는 노드는 6번이다.

dist[5]+1(5번에서 6번) < dist[6] 이므로 dist[6]의 값을 9로 갱신하고 우선순위큐에 (9, 6)을 추가시킨다.

 

 

 

우선순위큐에서 가장 가까운 거리의 노드를 뺴면 (9, 6)이 된다.

dist[6] = 9 이므로, 노드 6번까지의 거리를 확정한다.

 

6번에서 이동할 수 있는 노드는 3번과 5번이다.

하지만, dist[6]+8(6번에서 3번) > dist[3], dist[6]+1(6번에서 5번) > dist[5] 이므로 갱신할 수 있는 거리 정보는 없다.

 

 

 

마지막 원소 (12, 6)에서, dist[6] != 12 이므로 제거한다.

최종적으로 dist에 저장된 값들이 1번 노드에서의 최단 이동 거리가 된다.

코드 레벨에서의 구현은 다음과 같다.

 

 

코드

#include <vector>
#include <iostream>
#include <climits>
#include <queue>

using namespace std;
using ii = pair<int, int>;

#define X first
#define Y second

int V, E;
vector<int> dist(10, INT_MAX);
vector<vector<ii>> graph(10, vector<ii>(0));
priority_queue<ii, vector<ii>, greater<ii>> pq;

void setGraph() {

    for (int i=0; i<E; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        graph[u].push_back({v, c});
        graph[v].push_back({u, c}); 
    }
}

void Dijkstra() {

    dist[1] = 0;
    pq.push({0, 1});

    while (!pq.empty()) {

        ii cur = pq.top(); //(거리, 노드)
        pq.pop();

        if (dist[cur.Y] != cur.X) continue;
        //노드 cur.Y까지의 거리를 확정하고, cur.Y에서 이동할 수 있는 노드 탐색
        for (auto [next, c] : graph[cur.Y]) { 
            if (dist[cur.Y]+c < dist[next]) {
                dist[next] = dist[cur.Y]+c; //거리 갱신
                pq.push({dist[next], next}); //(거리, 노드) 추가
            }
        }
    }
}


int main() {

    cin >> V >> E;
    setGraph();
    Dijkstra();
    //1번 노드 부터 i번 노드까지의 최단 거리 출력
    for (int i=1; i<=V; i++) cout<<dist[i]<<" ";
    cout<<endl;
}

/*
input: 
6 7

output:
1 2 3
2 5 5
2 3 1
2 4 4
3 4 2
3 6 8
5 6 1
0 3 4 6 8 9 
*/