University:
Fresno Pacific University
Course:
MATH 210 | Calculus I
Academic year:

2024
Views:

218

Pages:

6
Author:

Ridwan Amin

Lecture 23 All-pairs Shortest Path Problem: Input: G = (V, E) ... directed w: E -> R Nodes are labeled as 1, 2, ..., n Output: A n x n matrix D = (d_ij) of shortest path distances s.t. d_ij = delta(i, j) Remarks: Reuse single-source shortest path algorithms: Dijkstra: O(|V| . |E| . log|V|) using binary heaps Bellman-Ford: O(|V|^2 . |E|) Goal: Design a new algorithm that doesn't rely on fancy data structures and other algorithms Floyd-Warshall Algorithm Runs in O(|V|^3) time A bottom-up DP algorithm. Let p = be a path. |p| = l - 1 p = intermediate nodes on p Let d_ij^(k) = the weight of the shortest path from i to j with all intermediate nodes from the set {1, 2, ..., k} i.e. (i) ~> o ... o ~> (j) d_ij^(k) ∈ {1, 2, ..., k} Want: d_ij^(n) for all i, j ∈ V. Consider a path (i) ~> (j) and the set {1, 2, ..., k} Case 1: Node k is not an intermediate node. => d_ij^(k) = d_ij^(k-1) Case 2: Node k is an intermediate node. i.e. (i) ~> (k) ~> (j) => d_ij^(k) = d_ik^(k-1) + d_kj^(k-1) Case 3: There is no intermediate node. (i) -> (j) d_ij^(0) = w(i, j) d_ij^(k) = { w(i, j) if k = 0 { min { d_ij^(k-1), d_ik^(k-1) + d_kj^(k-1) } if k >= 1 {1, 2} d_ij^(2) D^(2) = [ 0 3 15 8 ] [ α 0 12 5 ] [ 4 7 0 -1 ] [ 2 -4 8 0 ] d_13^(2) = min { d_13^(1), d_12^(1) + d_23^(1) } = min { 15, 3 + 12 } = 15 d_14^(2) = min { d_14^(1), d_12^(1) + d_24^(1) } = min { 8, 3 + 5 } = 8 d_43^(2) = min { d_43^(1), d_42^(1) + d_23^(1) } = min { 8, -4 + 12 } = 8 {1, 2, 3} d_ij^(3) D^(3) = [ 0 3 15 8 ] [ 16 0 12 5 ] [ 4 7 0 -1 ] [ 2 -4 8 0 ] d_21^(3) = min { d_21^(2), d_23^(2) + d_31^(2) } = min { α, 12 + 4 } = 16 {1, 2, 3, 4} d_ij^(4) D^(4) = [ 0 3 15 8 ] [ 7 0 12 5 ] [ 1 -5 0 -1 ] [ 2 -4 8 0 ] d_21^(4) = min { d_21^(3), d_24^(3) + d_41^(3) } = min { 16, 5 + 2 } = 7 d_31^(4) = min { d_31^(3), d_34^(3) + d_41^(3) } = min { 4, -1 + 2 } = 1