Graphs & Graph Algorithms 2OverviewSingle Source Shortest PathShortest Path – Djikstra’s AlgorithmShortest Path – Intuition for Djikstra’sSlide 6Slide 7Slide 8Djikstra’s Shortest Path ExampleSlide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Algorithm animationsSpanning TreeSpanning Tree ConstructionBreadth & Depth First Spanning TreesDepth-First Spanning Tree ExampleBreadth-First Spanning Tree ExampleSlide 27Minimum Spanning Tree (MST)MST – Kruskal’s AlgorithmMST – Kruskal’s Algorithm ExampleSlide 31MST – Connected Subgraph ExampleSlide 33Graph ImplementationAdjacency MatrixSlide 36Slide 37Adjacency ListSlide 39Graph Space RequirementsGraph Time RequirementsGraphs & Graph Algorithms 2 Nelson Padua-PerezBill PughDepartment of Computer ScienceUniversity of Maryland, College ParkOverviewShortest pathDjikstra’s algorithmSpanning treesMinimum spanning treeKruskal’s algorithmGraph implementationAdjacency list / matrixSingle Source Shortest PathCommon graph problemFind path from X to Y with lowest edge weightFind path from X to any Y with lowest edge weightUseful for many applicationsShortest route in mapLowest cost tripMost efficient internet routeCan solve both problems with same algorithmwould actually do something slightly different if we only wanted shortest path from X to Ydon’t need to find shortest path from College Park to Seattle in order to find shortest path from College Park to MiamiShortest Path – Djikstra’s AlgorithmMaintainNodes with known shortest path from start SCost of shortest path to node K from start C[K]Only for paths through nodes in SPredecessor to K on shortest path P[K]Updated whenever new (lower) C[K] discoveredRemembers actual path with lowest costShortest Path – Intuition for Djikstra’sAt each step in the algorithmShortest paths are known for nodes in SStore in C[K] length of shortest path to node K (for all paths through nodes in { S } )Add to { S } next closest node SShortest Path – Intuition for Djikstra’sUpdate distance to J after adding node KPrevious shortest paths already in C[ K ]Possibly shorter path by going through node KCompare C[ J ] with C[K ] + weight of (K,J)Shortest Path – Djikstra’s AlgorithmAlgorithmAdd starting node to SRepeat until all nodes in SFind node K not in S with smallest C[ K ]Add K to SExamine C[J] for all neighbors J of K not in SIf ( C[K] + weight for edge (K,J) ) < C[J]New shortest path by first going to K, then JUpdate C[J] C[K] + weight for edge (K,J) Update P[J] KShortest Path – Djikstra’s AlgorithmS = {start}, P[ ] = none for all nodesC[start] = 0, C[ ] = for all other nodeswhile ( not all nodes in S )find node K not in S with smallest C[K]add K to S for each node J not in S adjacent to K if ( C[K] + cost of (K,J) < C[J] ) C[J] = C[K] + cost of (K,J) P[J] = KOptimal solution computed with greedy algorithmDjikstra’s Shortest Path ExampleInitial stateS = C P1 0none2none3none4none5noneDjikstra’s Shortest Path ExampleFind shortest paths starting from node 1S = 1C P1 0none2none3none4none5noneDjikstra’s Shortest Path ExampleUpdate C[K] for all neighbors of 1 not in { S }S = { 1 }C[2] = min ( , C[1] + (1,2) ) = min ( , 0 + 5) = 5C[3] = min ( , C[1] + (1,3) ) = min ( , 0 + 8) = 8C P1 0none2 513 814none5noneDjikstra’s Shortest Path ExampleFind node K with smallest C[K] and add to S S = { 1, 2 }C P1 0none2 513 814none5noneDjikstra’s Shortest Path ExampleUpdate C[K] for all neighbors of 2 not in SS = { 1, 2 }C[3] = min (8 , C[2] + (2,3) ) = min (8 , 5 + 1) = 6C[4] = min ( , C[2] + (2,4) ) = min ( , 5 + 10) = 15C P1 0none2 513 624 1525noneDjikstra’s Shortest Path ExampleFind node K with smallest C[K] and add to SS = { 1, 2, 3 }C P1 0none2 513 624 1525noneDjikstra’s Shortest Path ExampleUpdate C[K] for all neighbors of 3 not in S{ S } = 1, 2, 3C[4] = min (15 , C[3] + (3,4) ) = min (15 , 6 + 3) = 9C P1 0none2 513 624 935noneDjikstra’s Shortest Path ExampleFind node K with smallest C[K] and add to S{ S } = 1, 2, 3, 4C P1 0none2 513 624 935noneDjikstra’s Shortest Path ExampleUpdate C[K] for all neighbors of 4 not in SS = { 1, 2, 3, 4 }C[5] = min ( , C[4] + (4,5) ) = min ( , 9 + 9) = 18C P1 0none2 513 624 935 184Djikstra’s Shortest Path ExampleFind node K with smallest C[K] and add to SS = { 1, 2, 3, 4, 5 }C P1 0none2 513 624 935 184Djikstra’s Shortest Path ExampleAll nodes in S, algorithm is finishedS = { 1, 2, 3, 4, 5 }C P1 0none2 513 624 935 184Djikstra’s Shortest Path ExampleFind shortest path from start to KStart at KTrace back predecessors in P[ ]Example paths (in reverse)2 13 2 14 3 2 15 4 3 2 1 C P1 0none2 513 624 935 184Algorithm animationsGood animation of Dijkstra’s algorithm athttp://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtmlAlso has animations of Prim’s and Kruskal’s algorithms for minimal spanning treesSpanning TreeSet of edges connecting all nodes in graphneed N-1 edges for N nodesno cycles, can be thought of as a treeCan build tree during traversalSpanning Tree Constructionfor all nodes Xset X.tag = False set X.parent = Null{ Discovered } = { 1st node }while ( { Discovered } )take node X out of { Discovered }if (X.tag = False)set X.tag = True for each successor Y of Xif (Y.tag = False)set Y.parent = X // add (X,Y) to treeadd Y to { Discovered }Breadth & Depth First Spanning TreesBreadth-first Depth-firstDepth-First Spanning Tree ExampleBreadth-First Spanning Tree ExampleSpanning Tree ConstructionMultiple spanning trees possibleDifferent breadth-first traversalsNodes same distance visited in different orderDifferent depth-first traversalsNeighbors of node visited in different orderDifferent traversals yield different spanning treesMinimum Spanning Tree (MST)Spanning tree with minimum total edge weight Multiple MSTs possible (with same weight)MST – Kruskal’s Algorithmsort edges by weight (from least to most)tree = for each edge (X,Y) in orderif it does not create a cycleadd (X,Y) to treestop when tree has N–1 edgesOptimal solution computed with greedy algorithmMST – Kruskal’s Algorithm ExampleMST – Kruskal’s AlgorithmWhen does adding (X,Y) to tree create cycle?Traversal approachTraverse tree starting at XIf we can reach Y, adding (X,Y) would create cycleConnected subgraph approachMaintain set of nodes for
View Full Document
Unlocking...