5. Shortest Paths
Shortest path 문제는 edge-weighted digraph가 주어졌을 때, s에서 t로 가는 최단 경로를 찾는 문제이다.
네비게이션, 네트워크 라우팅 등 여러 응용에 쓰인다.
여기서는 하나의 출발지에 대한 모든 다른 지점까지의 shorest-path를 계산하는 single-source shorest paths에 대해 고려할 것이다.
1. APIs
Weighted directed edge의 API는 다음과 같다.
DirectedEdge(int v, int w , double weight)
int from()
int to()
double weight()
EdgeWeightedDigraph의 API는 다음과 같다.
EdgeWeightedDigraphp(int V)
void addEdge(DiredtedEdge e)
Iterable<DirectedEdge> adj(int v)
int V() //number of vertices
구현은 앞서 배운것들과 유사하게, Adjacency-lists를 사용한다.
Single-source shortest paths의 API는 다음과 같다.
SP(EdgeWeightedDigraph G int s) // s is source
double distTo(int v) //length of shorest path from s to v
Iterable<DirectedEdge> pathTo(int v) //shorest path from s to v
2. Shortest-paths properties
먼저 우리는 2개의 vertex-indexed array 를 유지시킨다.
distTo[v] // length of shotest path from s to v
edgeTo[v] //last edge on shorest path from s to v
1) Edge relaxation
만약, e = v -> w 인 edge를 추가했다고 해보자.
그러면 w까지 도달하는 최소경로는 distTo[w] > distTo[v] + e.weight() 라면 변경되어야 한다.
이것을 Edge relaxation이라고 하고, distTo = distTo[v] + e.weight(), edgeTo[w] = e 로 변경된다.
2) Shorest-path optimality conditions
distTo[v] 가 최단경로라면 다음의 optimality conditions을 만족해야 한다. 역으로 아래를 만족하면 distTo[v]는 최단경로이다. (필요충분조건)
distTo[s] = 0
For each vertex v, distTo[v] is the length of some path from s to v
For each edge e = v->w, distTo[w] <= distTo[v] + e.weight()
3) Generic shortest-paths algorithm
SPT(Shortest path tree)를 찾는 일반적인 방법은 distTo[s] = 0, 나머지는 distTo[v] = ∞ 로 놓고, optimality condition이 만족될 때까지 Edge를 relaxation한다.
3. Dijkstra's algorithm(양수가능)
규칙은 다음과 같다.
1) vertex-Indexed-MinPQ를 만든다(source를 제외한 모든 vertex의 값은 초기에 무한대)
2) delete-min연산을 하고, 꺼내진 vertex에 인접한 edge들에 대해서 relax연산 (MinPQ 업데이트)을 함을 MinPQ가 비워질 때까지 반복한다.
Dijkstra algorithm은, positive weight일 때 optimality condition을 만족하게 되므로 사용가능하다.
근복적으로는 가까운 vertex들을 선택하면서 성장하며 spanning tree를 만드는 Prim's algorithm과 동일하다.
Prim's algotirhm은 tree와 가장가까운 vertex를 선택하고, Dijkstra's algorithm은 source와 가장 가까운 vertex를 선택한다.
성능은 tree의 크기가 V이고, 정확하게 모든 Edge를 한번씩만 relaxation하므로, ElogV이다.
4. Edge-weighted DAGs(Cycle x, 음수가능)
Cycle이 없는 DAG(Directed Acyclic Graph)에서는 MinPQ에 의한 순서가 아닌 Topological sort에 의한 topological order로 vertex를 선택하고 인접Edge를 relax시킴으로서, 더 빠르게 최소경로를 찾을 수 있다.
topological sort가 E + V에 비례하고, 탐색은 Edge와 Vertex를 한번씩만 거치므로 E + V이다.
따라서, 최종성능은 E + V에 비례한다.
weight가 음수인 경우에도 사용할 수 있어, Longest paths를 구하는데도 사용할 수 있다.
Longest paths는 단순히 모든 Edge에 -1을 곱해준 뒤, 최소경로를 찾고, 마지막에 -1을 다시 곱해주면 된다.
content resizing, job scheduling 등에 활용될 수 있다.
5. Negative weights
weight가 음수이고, Cycle이 있는 경우는 위의 방법들을 사용할 수 없다.
Cycle의 weight 합이 음수이면, 최소경로는 실질적으로 -∞ 가 된다.
SPT가 존재한다면, negative cycle은 존재하지 않는다. 역도 성립한다(필요충분조건)
negative cycle이 존재하지 않으면, SPT는 존재한다.
따라서, negavie cycle이 아니라는 보장이 없을 때 어떻게 SPT를 구할까?
1) Bellman-Ford algorithm
Dijkstra's algorithm이 하나의 source에 대해서 모든 Edge를 relax했다면, Bellman-Ford algorithm은 이것을 모든 vertex에 대해 순서대로 반복수행한다. 모든 vertex에 대해 1번씩이므로 V, Edge는 1번씩 relax되므로 E이다.
즉, 성능은 EV 가 된다.
한가지 특징은, i번째 source vertex에 대해서 relax를 수행할 때 distTo[v]의 변화가 없다면, i+1번째 부터는 edge를 relax시킬 필요가 없다는 점이다. 따라서, queue를 유지시켜 distTo[]의 변화를 보게한다면, 실제로는 EV보다 훨씬 빠른 시간내로 알고리즘의 수행을 끝낼 수 있다. 실제로는 이 경우 평균 수행성능은 E + V 이다. 물론 여전히 worst case는 EV이다.
또한, negative cycle을 검출할 수도 있는데, 마지막 V번째 source vertex에 대해서 relax가 수행되는 것이 있다면, Cycle이 존재하는 것이다. edgeTo[]를 추적함으로서 어디서 negative cycle이 발생했는지 확인할 수 있다.
차익거래같은 것에서 응용할 수 있다.