[그래프] 최단 경로 (다익스트라 / 플로이드-워셜)

정의 : 

최단 경로 문제란 두 노드를 잇는 가장 짧은 경로를 찾는 문제입니다.

가중치가 있는 그래프(Weighted Graph)에서 엣지 가중치의 합이 최소가 되도록 하는 경로를 찾으려는 것이 목적입니다.

https://ratsgo.github.io/data%20structure&algorithm/2017/11/25/shortestpath/

 

Q. Directed, Undirected 여부는 상관 없나?

→ ㅇㅇ Unweighted여도 상관 없음 (weight 1로 보고 BFS 돌리면 되니까)

⭐️ 참고) 위키 - Directed/Weighted 여부 별로 Single-pair, all-pair shortest path 알고리즘 정리해둠 (굿)

https://en.wikipedia.org/wiki/Shortest_path_problem#Undirected_graphs

 

 

다익스트라 (Dijkstra)

- 시작 노드에서 나머지 모든 노드까지의 최단거리 계산; 최단거리 1-D 리스트 반환

- 음의 간선이 없을 때 작동
(음의 간선 있을때도 작동하도록 만든 보완 버전 - Johnson's algorithm 링크)

- 매 사이클마다 방문하지 않은, 최단거리의 노드를 찾음 (Greedy)

- 최단거리 계산에 단순 리스트 사용 : $O(V^2)$

- 최단거리 저장에 Min heap 사용 : $O(E log V)$ (선호)

(Time complexity 참고 : https://stackoverflow.com/questions/26547816/understanding-time-complexity-calculation-for-dijkstra-algorithm)

 

- Heap 구현 

(🤔 Fibonacci heap 쓰면 시간복잡도 더 줄일 수 있다던데)

Python	PriorityQueue, heapq (선호)
C++	priority_queue

* 파이썬의 경우, 기본적으로 min heap이라 다익스트라에 적합

 

void dijkstra(int start) {
    priority_queue<pii, vector<pii>, greater<>> pq;
    pq.push({ 0, start }); // {노드까지의 최단 경로, 노드}
    d[start] = 0;
    while (!pq.empty()) {
        // 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
        auto [dist, now] = pq.top(); pq.pop(); // dist : 현재 노드까지의 비용, now : 현재 노드

        // visited check (if the shortest path is already found)
        if (d[now] < dist) continue;

        // 현재 노드와 연결된 다른 인접한 노드들을 확인
        for (int i = 0; i < graph[now].size(); i++) {
            auto [next_node, weight] = graph[now][i];
            int cost = dist + weight;
            // 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
            if (cost < d[next_node]) {
                d[next_node] = cost;
                pq.push({ cost, next_node});
            }
        }
    }
}

 

---

솔직히 근데 코드만 외울게 아니라, 왜 이게 잘 작동되는지 알아야 할거 아니야?

 

[수학적 귀납법을 이용한 증명]

 

1. 다익스트라 알고리즘을 사용하여, Source s로부터 최단거리 경로 (dist값)를 가지는 다음 정점 p를 찾을때마다 집합 G (원)에 넣는다고 하자.

그림으로 표현하면 이렇게 된다. 원 내부에 있는 '*' 표시된 점들은 s로부터 최단 경로를 찾아서 이미 방문한 점들. 

(귀납법을 위해, 찾아놓은 점들 v*, y*는 모두 s로부터 최단 경로를 가진다고 가정하자)

2. 아직 s로부터 최단 경로를 찾지 못한 점 w가 있다.
다익스트라 알고리즘에 의해, 다음번에 w가 선택되어 최단 경로를 찾게 된다고 하자.

(다익스트라 알고리즘이 그룹 G에 넣을 다음 미방문 정점을 선택할 땐, dist (s로부터의 거리)가 가장 짧은 미방문 정점을 선택한다.

따라서, 현재 선택한 w가 미방문 정점들 중엔 가장 짧은 dist값을 가진다)

3. 그러나, 이렇게 찾은 l(s,w)가 최단 경로가 아니라면? 다른 더 짧은 경로가 존재한다고 치자.

다익스트라 알고리즘에 따르면, w는 이미 미방문 정점 중 가장 짧은 dist를 가지는 정점이다.

★ 따라서, w로 가는 다른 최단 경로가 존재한다면, 다른 미방문 노드 'z' 를 거쳐서 올 수 밖에 없다.

(G내의 이미 방문한 노드들로부터 w까지 1 edge만에 오는 최단 경로는, 알고리즘이 선택한 대로 s - v* - w 뿐이니)
(z는 y*에서 거쳐서 온다고 하자. 어차피 y는 이미 방문한 노드 중 랜덤한 노드라고 볼 수 있으니)

 

그래서, s - y* - z - w 라는 경로가 있고, 이게 s - v* - w 보다 짧다고 '가정'하자.

과연, 진짜 짧을까?

4.  다익스트라가 선택한 w노드는 z보다 작은 (혹은 같은) dist 값을 가진다. 즉, l(s - v* - w) <= l(s - y* - z) 다.

근데, l(s - y* - z - w) = l(s - y* - z) + l(z,w)이고, 음의 간선이 없다고 가정하면 l(z,w) >= 0 이므로

l(s - v* - w) <= l(s - y* - z - w) 일 수밖에 없다 (같은 경우는 y* = v* 라서 z = w일때겠지).

 

결론 : 다익스트라 알고리즘이 찾은 다음 노드 w가, s로부터 최단 경로를 가진다.

귀납법에 의해, 다익스트라 알고리즘은 G={s} 일때부터 모든 다른 노드를 방문할 때 까지 잘 작동한다.

 

 

글로만 읽으면 이해가 잘 안돼서, 그림으로 정리해봤는데 훨씬 깔끔한 것 같다.

그리고, 다익스트라 알고리즘의 작동 방식 및 왜 음의 간선이 없을 때만 작동하는지도 이해했다.

---

주의) 참고로, Dijkstra로는 MST (Minimum Spanning Tree) 못찾음.

Source로부터 각 점의 최단 경로 찾는 알고리즘이지, 반드시 MST를 찾아주진 않음.

MST는 Kruskal, Prim 알고리즘 참고

stackoverflow.com/questions/1909281/use-dijkstras-to-find-a-minimum-spanning-tree

Use Dijkstra's to find a Minimum Spanning Tree?

 

 

플로이드-워셜 (Floyd-Warshall)

- 모든 노드에 대해, 시작 노드에서 나머지 모든 노드까지의 최단거리 계산; 최단거리 2-D matrix 반환 

- 점화식에 따라 최단거리 2-D matrix 채워넣음 (Bottom-up DP)

- 음의 간선있어도 작동 (알고리즘 논리 자체가 edge weight에 대한 아무 제약도 없음)

- 출발 노드 (a) ~ 도착 노드 (b), 이 사이에 들어갈 수 있는 다른 모든 노드 (k) 모두 탐색 : $O(N^3)$

// 점화식에 따라 플로이드 워셜 알고리즘을 수행
for (int k = 1; k <= n; k++) {
    for (int a = 1; a <= n; a++) {
        for (int b = 1; b <= n; b++) {
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b]);
        }
    }
}

모든 다른 노드를 경유점으로 고려해서 a~b간 최단거리를 갱신해나가는 알고리즘..으로 간단히 이해할 수도 있겠으나,

이게 작동하는 이론적 베이스는 사실

'알고리즘이 방문할 수 있는 정점의 집합을 점점 늘려가면서 최단 거리를 계산'

하는데에 있다 (종만북 p.954 Floyd DP 증명 참고 + 삼성 SWEA SW 문제해결 응용 - 07 DP-2 3차시 모든 쌍 최단 경로)

 

이 개념을 꿰뚫고 있어야 풀 수 있는 문제가 있다

(종만북 p.959 DRUNKEN)

 

 

+) Bellman-Ford의 특징이라고 여겨졌던 negative cycle detection : Floyd Warshall 알고리즘으로도 가능!

Negative cycle =  sum of cost in the cycle < 0 인걸 말함.

그렇다면, negative cycle에 속한 한 노드가 있으면, 그 노드에서 출발해서 negative cycle을 타고 다시 자기 자신으로 돌아오는 cost는 음수일 것!

 

Floy-Warshall 알고리즘은 원래 최단거리 행렬 dist_matrix 초기화 할 때, dist_matrix[a][a] = 0 으로 초기화 함.

근데, 알고리즘 돌린 결과, dist_matrix[a][a] < 0 가 된다면? 

=> Negative cycle exists!