최단 경로 알고리즘 - algorithm for shortest path problem

개인적인 정리를 위한 포스트로, 학습용으로는 적합하지 않을 수 있습니다.
참조에 적힌 블로그 포스트를 읽으시는 것을 추천드립니다. :)

최단 경로를 구하는 문제에서 적용할만한 알고리즘을 알아보자.

---

0) 모델링

그래프에 대한 정보는 인접 행렬이나 인접 리스트를 이용해 모델링할 수 있다.

1. Adjacency Matrix (인접 행렬) 노드 개수 $V$개가 있다면 $V^2$개의 배열에 간선의 정보를 저장하는 것이다.
   구현이 쉽고 간편해 보이지만, 간선의 유무와 관계없이 전체를 탐색해 보아야 하기 때문에 전체 탐색시 $O(V^2)$이 걸린다.
   그러나 배열의 특성상 특정 간선만 알고 싶을 때는 $O(1)$ 밖에 소요되지 않는다는 장점이 있다.
   ex) i → j : edge[i][j] = true;
2. Adjacency List (인접 리스트) 간선의 정보를 배열에 저장하는 인접 행렬과 달리 벡터에 저장한다.
   간선의 개수만큼의 메모리가 필요하므로 효율적이고, Complete graph가 아닌 이상 전체 탐색에 $O(V^2)$보다 적게 걸린다.
   그러나 배열이 아니므로 특정 간선만 알기 위해서는 시작 노드의 모든 간선 정보를 탐색해보아야한다는 단점이 있다.
   ex) i → j : edge[i].push_back(j);

아래의 테이블에 각각 operation의 시간 복잡도와 중요점이 잘 정리되어 있다.

---

1) Floyd-Warshall Algorithm

한번의 시행으로 모든 쌍의 최단 거리를 구할 수 있는, 즉 All-pairs shortest paths를 구할 수 있는 알고리즘이다.
가중치의 부호에 관계없이 음의 사이클(negative cycle)만 존재하지 않으면 항상 사용할 수 있다는 장점이 있다.

루프가 순서대로 경유지 → 시작점 → 끝점임에 유의해야 한다. pseudocode 상 주의해야하는 점은 complete graph가 아닐 수 있으므로 INF로 초기화해줘야 한다는 점과, 자기 자신의 가중치는 0으로 설정한다는 점이다. 사실 모든 그래프 모델링이 비슷하긴 하다. 이러한 가정들도 물론 문제의 상황에 따라 수정하여 사용할 수 있다. 대표적으로 운동@1956이 그렇다.

음의 사이클(negative cycle)은 왜 존재하지 않을때라고 가정했을까? 음의 사이클은 가중치의 합이 음수가 되는 사이클을 말하는데, 음의 사이클을 계속해서 돈 후 다음 노드에 도달하면 계속해서 최단거리가 줄어드는 일이 발생한다. 즉, 이론적으로는 최단거리가 $-$INF에 해당할 수 있기에 배제하는 것이다.

시간 복잡도는 보는 것과 같이 $V$번 for문의 3중 loop이므로 $O(V^3)$에 해당한다. 사실 한번에 All-pairs shortest paths를 구하는 것은 Single-source shortest paths 알고리즘들을 $V$번 한 것과 똑같긴 하다. 즉, 특별한 것은 아니라는 것. 음의 가중치도 가능하다는 점은 더 빠른 Bellman-Ford도 마찬가지이다.

---

2) Bellman-Ford Algorithm

지금부터는 시작점이 주어졌을 때 각각의 노드에 도달하는 데에 최단거리를 구하는 알고리즘들이다. 이를 Single-source shortest paths algorithms라고 ,,, 하더라. 잘은 모르겠다.

보아야할 부분은 Step 2이다. 첫 번째 루프는 $V-1$번 돌고, 두 번째 루프는 모든 간선들을 탐색하며 최단경로의 거리를 갱신한다. 살짝 버블소트 느낌으로 보면 이해가 빠를 것 같은데, 간선들의 전체적인 연결을 알 수 없기 때문에 (즉, 간선이 연결된 순서대로 갱신, 갱신, 갱신 할 수 없기 때문이다.) 모든 간선을 한번씩 돌아보는 것으로는 최단 거리를 알 수가 없다. 따라서 이 작업을 $V-1$번 해주는 것이다.

구현은 두 번째 for문을 이중 for문으로 바꾸어서 구현하면 된다. for(int j=0; j<V; j++) + for(auto edge: E[j]); 와 같이 하면 모든 간선들을 조사하는 것이 되니까 ,, 참고로 구사과님이 거리가 갱신될 때 flag 변수를 사용해서 while을 사용하는 방식으로 구현한 코드도 있다. 보면 좋을듯.

시간 복잡도는 $O_{\text{best}}(E)$ (→ 두번째 loop에서 갱신되는 게 없으면 끝내도록 하면 됨), $O_{\text{worst}}(VE)$ 이다.

Step 3는 Bellman-Ford algorithm에서 negative cycle을 검출하는 과정이다. 만약 $V-1$ 번째 loop를 돈 이후 한번 더 loop를 돌았을 때 값이 갱신되면 음의 사이클이 존재한다는 것으로, 즉 loop를 한 번 더 돔으로써 검출 가능하다. 이 과정을 Step 2의 첫 번째 loop를 $V-1$ 까지가 아닌 $V$까지 하고, $V$번째 loop일때 flag를 이용함으로써 코드 간결화도 꾀해볼 수 있다.

---

3) Dijkstra Algorithm

이름부터 이쁘다; 혹시 알고 있는지는 모르겠지만 원래 알고리즘은 min-priority queue를 사용하지 않았다고 한다.

Line 13의 vertex in Q with min dist[u]는 노드의 집합인 Q에서 가장 작은 dist를 가진 노드를 꺼내라는 것이다.
즉, 첫 번째 try에서는 Line 10에 의해 source 노드가 pop되므로 자연스럽게 source부터 시작하게 되고, 인접노드들의 dist[v]를 갱신한 후, 다음 try에서는 dist가 0인 source 노드는 Q 내에 없으므로 나머지 중 최소를 찾게 된다. 이런 식으로 반복하면 dist[u] 최소가 되는 값을 찾기 위해서만 $O(V)$, 노드 개수 $V-1$만큼 loop를 도므로 $O(V^2)$를 갖게 된다.

그러나 heap을 이용한 min-priority queue를 사용하면 $O_{\text{worst}}(E\log_2V)$까지 줄일 수 있다.

Line 6 for문에서 source가 아닐 때 dist를 INF해주는 것은 첫 번째 의사코드의 Line 5에서의 전처리와 동일하다.
priority queue를 이용해서 갱신될 때마다 push 해주면 된다.

Dijkstra algorithm은 Wikipedia에 검색을 하거나, 여러 블로그를 둘러보면 각각 시간복잡도가 다른 걸 알 수있다.
잘 모르지만,, 아마 자료구조의 종류나 그래프의 특성 + Big-O notation 때문에 바뀌는 것 같다.

나도 헷갈릴 것 같아서 조금 적어 두자면,
Dijkstra algorithm의 실행 시간은 $O(E * T_{\text{decrease-key}} + V * T_{\text{extract-minimum}})$으로 표현될 수 있다.

만약 priority queue를 사용하지 않는다면, $T_{\text{extract-minimum}}$이 노드들을 모두 탐색하는 것과 같으므로 $O(V)$, $T_{\text{decrease-key}}$ 부분은 모든 간선들에 대해서 한번씩 수행되므로 합쳐서 $O(E + V^2) = O(V^2)$이 된다.

→ 간선의 개수 $E$는 상한이 $V^2$이므로, $O(E = V^2 + V^2) = O(2V^2) = O(V^2)$

Self-balancing binary search tree나 binary heap을 쓰면, $T_{\text{decrease-key}} = O(\log_2 n)$, $T_{\text{extract-minimum}} = O(\log_2 n)$이므로, 시간 복잡도의 합은 $O((E+V) \log_2 V)$가 된다.

fibonacci heap을 쓰면, $T_{\text{decrease-key}}= O(1)$, $T_{\text{extract-minimum}} = O(\log_2 n)$이므로, 시간 복잡도의 합은 $O(E + V\log_2V)$가 된다.

그러면 $O(E\log_2V)$는 어떻게 도출될 수 있을까? 일단 C++ STL의 priority queue는 binary heap을 기초로 하고 있고, $O((E + V)\log_2V)$에서 $E$의 상한은 $V^2$이므로 $O((V^2 + V)\log_2V) = O(V^2 * \log_2V) = O(E\log_2V)$가 되는 것이다. 모든 시간 복잡도에서 $E$의 상한을 $V^2$로 상정하고 마무리하지 않는 것은, 문제의 조건에 따라 E의 상한이 바뀔 수 있기 때문이다.라고 위키백과가 그러더라.

---

4) Shortest Path Faster Algorithm (SPFA)

마지막으로 소개할 알고리즘은 SPFA가 있겠다.

SPFA는 Bellman-Ford 알고리즘을 개선한 것으로, BFS를 이용하여 구현할 수 있다.

Bellman-Ford 알고리즘처럼 노드들의 인접 노드들, 즉 간선들을 살펴본다는 점은 동일하나,
Line 8 if문 안에 있는 Line 10 if문에서 볼 수 있듯이 갱신이 일어나는 인접 노드가 큐에 없을 경우,
큐에 추가하여 다음 탐색의 후보로 둔다는 점이 모든 간선을 살펴보아야 하는 Bellman-Ford algorithm과 다르다.

그래서 $O_{\text{worst}}$는 $O(VE)$로 동일하지만, $O_{\text{avg}}$를 $O(E)$까지 줄일 수 있다는 점에서 실제로는 효율적이라는 의의가 있다.

---

# Reference

https://en.wikipedia.org/wiki/Shortest_path_problem 최단 경로 문제 @ 위키백과
https://blog.naver.com/kks227/220797649276 Floyd-Warshall Algorithm @ 라이님 블로그
https://blog.naver.com/kks227/220796963742 Bellman-Ford Algorithm @ 라이님 블로그
https://blog.naver.com/kks227/220796029558 Dijkstra Algorithm @ 라이님 블로그
https://koosaga.com/2 Floyd-Warshall, Bellman-Ford, Dijkstra Algorithm @ 구사과님 블로그
https://hongjun7.tistory.com/134 Shortest Path Faster Algorithm(SPFA) @ hongju7님 블로그