티스토리 뷰
최단 경로 알고리즘 - algorithm for shortest path problem
hyp3rflow 2019. 10. 2. 03:26최단 경로를 구하는 문제에서 적용할만한 알고리즘을 알아보자.
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(var edge: E[j]) 와 같이 하면 모든 간선들을 조사하는 것이 되니까 ,,
참고로 구사과님이 거리가 갱신될 때 flag 변수를 사용해서 while을 사용하는 방식으로 구현한 코드도 있다. 보면 좋을듯.
시간 복잡도는 Obest(E) (→ 두번째 loop에서 갱신되는 게 없으면 끝내도록 하면 됨), Oworst(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를 사용하면 Oworst(ElogV)까지 줄일 수 있다.
Line 6 for문에서 source가 아닐 때 dist를 INF해주는 것은 첫 번째 의사코드의 Line 5에서의 전처리와 동일하다.
priority queue를 이용해서 갱신될 때마다 push 해주면 된다.
Dijkstra algorithm은 Wikipedia에 검색을 하거나, 여러 블로그를 둘러보면 각각 시간복잡도가 다른 걸 알 수있다.
잘 모르지만,, 아마 자료구조의 종류나 그래프의 특성 + Big-O notation 때문에 바뀌는 것 같다.
나도 헷갈릴 것 같아서 조금 적어 두자면,
Dijkstra algorithm의 실행 시간은 O(E * Tdecrese-key + V * Textract-minimum)으로 표현될 수 있다.
만약 priority queue를 사용하지 않는다면,
Textract-minimum이 노드들을 모두 탐색하는 것과 같으므로 O(V),
Tdecrese-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을 쓰면,
Tdecrease-key = O(log n), Textract-minimum = O(log n)이므로,
시간 복잡도의 합은 O((E+V) log V)가 된다.
fibonacci heap을 쓰면,
Tdecrease-key = O(1), Textract-minimum = O(log n)이므로,
시간 복잡도의 합은 O(E + VlogV)가 된다.
그러면 O(ElogV)는 어떻게 도출될 수 있을까?
일단 C++ STL의 priority queue는 binary heap을 기초로 하고 있고,
O((E + V)logV)에서 E의 상한은 V^2이므로 O((V^2 + V)logV) = O(V^2 * logV) = O(ElogV)가 되는 것이다.
모든 시간 복잡도에서 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과 다르다.
그래서 Oworst는 O(VE)로 동일하지만, Oavg를 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님 블로그
'Problem Solving > Algorithm' 카테고리의 다른 글
| 서로소 집합, 유니온 파인드 - Disjoint set, Union-Find (0) | 2019.10.03 |
|---|