DOC PREVIEW
GSU CSC 2510 - ch06s3

This preview shows page 1-2-3-4-5 out of 16 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 ProblemAssume 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 AlgorithmTo 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 AlgorithmPick 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 AlgorithmALGORITHM 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 ExampleTrace 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 ExampleThe 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 ExampleWe 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, ) = 10This process is repeated until y is added to IN.Section 6.3 Shortest Path and Minimal Spanning Tree 11Shortest-Path Algorithm ExampleThe 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 + ) = 8d[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 ExampleThe third pass through the while loop:p = 4 (d-value 5)IN = {x, 1, 3, 4}d[2] = min(8, 5 + 7) = 8d[y] = min(7, 5 + 1) = 6 (a change, update s[y])Section 6.3 Shortest Path and Minimal Spanning Tree 13Shortest-Path Algorithm ExampleThe third pass through the while loop:p = yIN = {x, 1, 3, 4, y}d[2] = min(8, 6 ) = 8y 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 AnalysisShortestPath 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 ProblemDEFINITION: 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

GSU CSC 2510 - ch06s3

Documents in this Course
ch02s2

ch02s2

5 pages

ch04s2

ch04s2

8 pages

ch01s6

ch01s6

10 pages

ch01s1

ch01s1

21 pages

ch02s4

ch02s4

10 pages

ch08s2

ch08s2

21 pages

ch08s3

ch08s3

15 pages

ch07s3

ch07s3

21 pages

ch04s3

ch04s3

23 pages

ch01s3

ch01s3

15 pages

ch03s4

ch03s4

11 pages

ch03s6

ch03s6

6 pages

ch03s5

ch03s5

9 pages

ch06s2

ch06s2

9 pages

ch03s1

ch03s1

19 pages

ch07s1

ch07s1

11 pages

ch02s1

ch02s1

14 pages

ch08s1

ch08s1

15 pages

ch02s5

ch02s5

9 pages

ch01s4

ch01s4

13 pages

Load more
Download ch06s3
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view ch06s3 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view ch06s3 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?