Solving SPP with Non-Negative Arc Lengths

When there are cycles, the situation is a bit more complex. Dijkstra's Algorithm generalizes the algorithm from Lecture 7 for the acyclic case. The difference is the order in which the nodes are examined. As before, nodes are divided into two groups { temporarily labeled { permanently labeled In order to produce the shortest paths tree, we keep track of the predecessor node each time a label is updated. Basic Idea: Fan out from source and permanently label nodes in order of distance from the source. 2 ISE 411 Lecture 9 3 Dijkstra's Algorithm Input: An network G = (N;A) and a vector of arc lengths c 2 ZA+ Output: d(i) is the length of a shortest path from node s to node i and pred(i) is the immediate predecessor of i in an associated shortest paths tree. S: = ∅ S: =