Chapter 4 Shortest Path Label-Setting Algorithms. Introduction & Assumptions Applications Dijkstra’s Algorithm. Problem Definition & Assumptions.
Download Policy: Content on the Website is provided to you AS IS for your information and personal use and may not be sold / licensed / shared on other websites without getting consent from its author.While downloading, if for some reason you are not able to download a presentation, the publisher may have deleted the file from their server.
Introduction & Assumptions
Problem: Given a network G = (N, A) in which each arc (i, j) has an associated length or cost cij, let node s be the source. The length of a directed path is the sum of the lengths of the arcs in the path. For every node i s, find a shortest length directed path from s to i.
String model for shortest path from s to t:
Arcs = strings, knots = nodes; hold s and t and pull tight.
Shortest paths will be taut: for i and j on a shortest path connected by arc (i, j), distance s-i plus cij distance s-j
Associated “dual” maximization problem: pulling s and t as far apart as possible
Solution is a shortest-path tree rooted at s.
Property 4.1. If the path s = i1 – i2 – … – ih =k is a shortest path from s to k, then for every q = 2, 3, …, h-1, the subpath s = i1 – i2 – … – iq is a shortest path from the source node to iq.
Property 4.2. Let the vector d represent the shortest path distances. Then a directed path P from s to k is a shortest path if and only if for
Store the shortest path tree as a vector of n-1 predecessor nodes: pred(j) is the node i that satisfies above equality.
Examine the nodes in topological order; perform a breadth-first search to find a shortest-path tree.
0.d(s) 0, d(j) for j s, i s
1. If A(i) is empty, then stop. Otherwise, to examine node i, scan the arcs in A(i). If for any arc (i, j), d(j) d(i) + cij, then set d(j) = d(i) + cij.
2. Set i to the next node in topological order and return to 1.
Solves shortest path problem on acyclic networks in O(m) time.
Shortest paths from source node to all other nodes with nonnegative arc lengths (cycles permitted)
d(i) is the distance from s to i along a shortest path
pred(i) is the predecessor of i along a shortest path
S = set of permanently labeled nodes (L in GIDEN)
set of temporarily labeled nodes (P in GIDEN)
GIDEN also has set U for unlabeled nodes
At each iteration, one node moves to S from