Shortest Path Algorithm
Shortest Path Problem Definition Input: Directed graph G = (V, E) Weighted, directed graph G=(V, E) 에 대하여, 총 weight 가 최소화 되는 path 를 찾는 문제 Input: Directed graph G = (V, E) Weight function w : E → R Weight of path p = <v0, v1, . . . , vk> = = sum of edge weights on path p . Shortest-path weight u to v: δ(u, v) = min {w(p) : } if there exists a path , ∞ otherwise . Shortest path u to v is any path p such that w(p) = δ(u, v).
Shortest Path Problem Types 1) Single-source shortest paths problem 2) Single-destination shortest paths problem 3) Single-pair shortest paths problem 4) All-pairs shortest paths problem Solutions to single-source shortest paths problem (i) Negative-weight edge 가 있는 경우 - Bellman-Ford algorithm - O(V E) (ii) Negative-weight edge 가 없는 경우 - Dijkstra’s algorithm - O(V2)– O(V lg V + E) : 구현 방법에 따라 다름
Bellman-Ford Algorithm 목적 single-source shortest-paths problem 의 해를 구함 - negative weighted edge 대응 가능 source 에서 도달 가능한 negative-weight cycle 존재 여부 판별 => 존재하면 해 없음.
Bellman-Ford Algorithm 원리 Relaxation d[v]: s 부터 v 까지의 shortest-path estimate RELAX(u,v,w) Path-relaxation property p = <v0, v1, . . . , vk> 가 v0 에서 vk까지의 shortest path 이고 p 의 edge 들이 (v0, v1) ,(v1, v2), …, (vk-1, vk)의 순으로 relax 되었다면, d[vk] = δ(s, vk)
Bellman-Ford Algorithm BELLMAN-FORD(G,w,s) O (V E)
Bellman-Ford Algorithm Operations
Bellman-Ford Algorithm (Q)
Dijkstra’s Algorithm 특징 Data Single-source shortest problem Nonnegative-weighted edges Running time: lower than Bellman-Ford algorithm (if good implementation) Data Graph: V, E, w(u,v) adjacency-list adjacency-matrix d[u]: vertex u 의 shortest-path estimate π[u]: vertex u 의 predecessor S: source s 로 부터의 최단거리가 결정된 vertex 의 집합 Q: vertex 들의 minimum-priority queue, key = d (cf) breadth first search
Dijkstra’s Algorithm DIJKSTRA(G, w, s) Greedy strategy Optimal solution Running time : O (V lg V + E) line 4-8 : O(V) EXTRACT-MIN(q): O (lg V) Line 7-8: O(E)
Dijkstra’s Algorithm Operations
Dijkstra’s Algorithm (Q)