13. Graph Algorithms - the Shortest Path

Single-Destination Shortest Path

그래프가 주어졌을 때, source에서 destination까지 shortest path를 찾는 문제이다.

 

Optimal substructure

어떤 문제의 최적의 해결책이 그 부분 문제의 최적의 해결책으로부터 효율적으로 구해질 수 있는 경우를 말한다. 이 구조를 만족하는 경우 문제를 Greedy algorithm이나 Dynamic programming을 이용해 해결할 수 있데 된다.

Optimal substructure

s→d까지의 path가 shortest라면, s→t 역시 shortest임을 의미하게 된다.

 

문제가 이 구조를 만족하는지 확인하는 것은 중요한 문제이다. 다음의 그래프에 대해서 Prim 알고리즘을 적용해보면 무슨 말인지 알 수 있다.

Prim result

Prim은 greedy하게 edge를 선택하는 알고리즘이었다. 그 결과 global weight 5의 path를 찾아낸다. Global shortest path의 weight는 4라는 점을 생각해보았을 때, greedy 알고리즘이 올바른 결과를 가지지 못한다는 점을 알 수 있다. 만약 이 그래프가 Optimal structure를 만족한다면, Prim은 total weight 4의 path를 찾을 수 있었을 것이다.

 

Single-pair Shortest Path

Dijkstra's algorithm

Prim's algorithm을 여러번 수행하는 것과 같은 알고리즘이다. 구체적인 과정은 다음과 같다.

Dijkstra

모든 vertex의 거리, d를 무한대로 설정하고

source에서 갈 수 있는 vertex의 d를 업데이트한 후

최소 d를 가지는 vertex로 path를 확장하는 알고리즘이다.

Example

 

Prim처럼 heap을 사용해 구현할 경우, 시간 복잡도는 $O(elogn)$이다. Fibonacci heap을 사용하는 경우 $O(e+nlogn)$의 시간 복잡도가 소모된다.

 

Correctness 증명과정은 다음과 같다.

Correctness of Dijkstra

Dijkstra의 단점으로는 negative weight에 대해서 동작하지 않는다는 것이다. d가 계속해서 업데이트가 되기 때문에 negative cycle이 생기게 된다. 또한 forest 구조(disconnected)에 사용할 수 없다.

 

Bellman-Ford algorithm

Dijkstra의 단점은 해결하지만, 성능이 떨어지게 된 알고리즘이다. n-1번에 갈 수 있는 모든 경로의 distance를 계산한 후 best path를 선택한다. 그리고 마지막으로 n번째 탐색을 수행하여, d 값이 줄어드는 것을 보고 negative cycle이 있음을 확인할 수 있다.

 

알고리즘은 다음과 같다.

Bellman-Ford

Example

모든 vertex에서 distance를 업데이트하고 best path를 선택한다. 시간 복잡도는 $O(VE)$가 소모된다.

 

Correctness는 다음과 같이 2 경우로 나누어서 증명한다. Loop invariant를 이용한다.

Correctness of Bellman-Ford

DAG에서 Bellman-Ford는 더 좋은 성능을 보여준다.

Bellman-Ford on DAG

시간 복잡도는 $O(E)$가 소모되게 된다. 각 edge는 1번만 사용되며 acyclic이기 때문에 돌아갈 일이 없기 때문이다. Linear time에 해결할 수 있게 된다.

 

All-pairs Shortest Path

Floyd-Warshall algorithm

Dijkstra와 Bellman ford 알고리즘이 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘이었다면, Bellman ford는 노드 간의 최단거리를 구하는 알고리즘이다.

Recursive formulation

Optimal substructure를 이용해 d를 업데이트한다. 기존의 path에서 k vertex를 거쳐서 가는 것이 shortest라면, k vertex를 shortest path에 포함시키는 방식이다.

Optimal substructure

 

알고리즘은 다음과 같다.

Floyd-Warshall

예제를 한번 풀어본다.

Example

이런 그래프에 대해서 $D^0$ distance matrix를 생성한다. 갈 수 없으면 weight를 무한대로 설정한다.

$D^1$은 $V_1$을 거쳐서 갈 경우의 distance를 보고 업데이트하면 된다. $D^2$의 경우 $V_2$를 중간노드로 이용해 갈 수 있을 때의 distance를 보고 업데이트하면 된다.

 

시간 복잡도는 총 $O(V)×O(V)×O(V)$이므로 $O(V^3)$이 걸리게 된다. Dijkstra를 n번 수행하면 더 줄일 수 있지만, negative weight가 있으면 사용하지 못한다는 단점이 있다.