Graph AlgorithmsShortest Path ProblemShortest-Path AlgorithmSlide 4Slide 5Slide 6Slide 7Shortest-Path Algorithm ExampleSlide 9Slide 10Slide 11Slide 12Slide 13Shortest-Path Algorithm AnalysisMinimal Spanning Tree ProblemPrim’s AlgorithmGraph AlgorithmsMathematical Structures for Computer ScienceChapter 6Copyright © 2006 W.H. Freeman & Co. MSCS Slides Graph AlgorithmsSection 6.3 Shortest Path and Minimal Spanning Tree 2Shortest Path ProblemAssume that we have a simple, weighted, connected graph, where the weights are positive. Then a path exists between any two nodes x and y.How do we find a path with minimum weight?For example, cities connected by roads, with the weight being the distance between them.The shortest-path algorithm is known as Dijkstra’s algorithm.Section 6.3 Shortest Path and Minimal Spanning Tree 3Shortest-Path AlgorithmTo compute the shortest path from x to y using Dijkstra’s algorithm, we build a set (called IN ) that initially contains only x but grows as the algorithm proceeds.IN contains every node whose shortest path from x, using only nodes in IN, has so far been determined.For every node z outside IN, we keep track of the shortest distance d[z] from x to that node, using a path whose only non-IN node is z.We also keep track of the node adjacent to z on this path, s[z].Section 6.3 Shortest Path and Minimal Spanning Tree 4Shortest-Path AlgorithmPick the non-IN node p with the smallest distance d.Add p to IN, then recompute d for all the remaining non-IN nodes, because there may be a shorter path from x going through p than there was before p belonged to IN.If there is a shorter path, update s[z] so that p is now shown to be the node adjacent to z on the current shortest path.As soon as y is moved into IN, IN stops growing. The current value of d[y] is the distance for the shortest path, and its nodes are found by looking at y, s[y], s[s[y]], and so forth, until x is reached.Section 6.3 Shortest Path and Minimal Spanning Tree 5Shortest-Path AlgorithmALGORITHM ShortestPathShortestPath (n n matrix A; nodes x, y)//Dijkstra’s algorithm. A is a modified adjacency matrix for a//simple, connected graph with positive weights; x and y are//nodes in the graph; writes out nodes in the shortest path from x// to y, and the distance for that path Local variables: set of nodes IN //set of nodes whose shortest path from x //is known nodes z, p //temporary nodes array of integers d //for each node, the distance from x using //nodes in IN array of nodes s //for each node, the previous node in the //shortest path integer OldDistance //distance to compare against //initialize set IN and arrays d and s IN = {x} d[x] = 0Section 6.3 Shortest Path and Minimal Spanning Tree 6Shortest-Path Algorithmfor all nodes z not in IN do d[z] = A[x, z] s [z] = xend for//process nodes into INwhile y not in IN do //add minimum-distance node not in IN p = node z not in IN with minimum d[z] IN = IN {p} //recompute d for non-IN nodes, adjust s if necessary for all nodes z not in IN do OldDistance = d[z] d[z] = min(d[z], d[ p] + A[ p, z]) if d[z] != OldDistance then s [z] = p end if end forend whileSection 6.3 Shortest Path and Minimal Spanning Tree 7Shortest-Path Algorithm//write out path nodeswrite(“In reverse order, the path is”)write (y)z = yrepeat write (s [z]) z = s [z]until z = x// write out path distancewrite(“The path distance is,” d[y])end ShortestPathSection 6.3 Shortest Path and Minimal Spanning Tree 8Shortest-Path Algorithm ExampleTrace the algorithm using the following graph and adjacency matrix:At the end of the initialization phase:Section 6.3 Shortest Path and Minimal Spanning Tree 9Shortest-Path Algorithm ExampleThe circled nodes are those in set IN. heavy lines show the current shortest paths, and the d-value for each node is written along with the node label.Section 6.3 Shortest Path and Minimal Spanning Tree 10Shortest-Path Algorithm ExampleWe now enter the while loop and search through the d-values for the node of minimum distance that is not in IN. Node 1 is found, with d[1] = 3.Node 1 is added to IN. We recompute all the d-values for the remaining nodes, 2, 3, 4, and y.p = 1IN = {x,1}d[2] = min(8, 3 + A[1, 2]) = min(8, ) = 8d[3] = min(4, 3 + A[1, 3]) = min(4, 9) = 4d[4] = min(, 3 + A[1, 4]) = min(, ) = d[y] = min(10, 3 + A[1, y]) = min(10, ) = 10This process is repeated until y is added to IN.Section 6.3 Shortest Path and Minimal Spanning Tree 11Shortest-Path Algorithm ExampleThe second pass through the while loop:p = 3 (3 has the smallest d-value, namely 4, of 2, 3, 4, or y)IN = {x, 1, 3}d[2] = min(8, 4 + A[3, 2]) = min(8, 4 + ) = 8d[4] = min(, 4 + A[3, 4]) = min(, 4 + 1) = 5 (a change, so update s[4] to 3)d[y] = min(10, 4 + A[3, y]) = min(10, 4 + 3) = 7 (a change, so update s[y] to 3)Section 6.3 Shortest Path and Minimal Spanning Tree 12Shortest-Path Algorithm ExampleThe third pass through the while loop:p = 4 (d-value 5)IN = {x, 1, 3, 4}d[2] = min(8, 5 + 7) = 8d[y] = min(7, 5 + 1) = 6 (a change, update s[y])Section 6.3 Shortest Path and Minimal Spanning Tree 13Shortest-Path Algorithm ExampleThe third pass through the while loop:p = yIN = {x, 1, 3, 4, y}d[2] = min(8, 6 ) = 8y is now part of IN, so the while loop terminates. The (reversed) path goes through y, s[y]= 4, s[4]= 3, and s[3] = x.Section 6.3 Shortest Path and Minimal Spanning Tree 14Shortest-Path Algorithm AnalysisShortestPath is a greedy algorithm - it does what seems best based on its limited immediate knowledge.The for loop requires Θ(n) operations.The while loop takes Θ(n) operations.In the worst case, y is the last node brought into IN, and the while loop will be executed n - 1 times.The total number of operations involved in the while loop is Θ(n(n - 1)) = Θ(n2 ).Initialization and writing the output together take Θ(n) operations.So the algorithm requires Θ(n + n2) = Θ(n2 ) operations in the worst case.Section 6.3 Shortest Path and Minimal Spanning Tree 15Minimal Spanning Tree ProblemDEFINITION: SPANNING TREE A spanning tree for a connected graph is a nonrooted tree whose set of nodes coincides with the set of nodes for the graph and whose arcs are (some of) the arcs of the graph.A spanning tree connects all the nodes of a graph with no
View Full Document