1CMSC 132: Object-Oriented Programming IIGraph Implementations & Single Source Shortest Path AlgorithmDepartment of Computer ScienceUniversity of Maryland, College Park2Graph ImplementationHow do we represent edges?Adjacency matrix2D array of neighborsAdjacency listList of neighborsAdjacency set / mapSet / map of neighborsImportant for very large graphsAffects efficiency / storage3Adjacency MatrixRepresentation2D arrayPosition j, k ⇒⇒⇒⇒edge between nodes nj, nkExample4Adjacency MatrixRepresentation (cont.)Single array for entire graphUndirected graphOnly upper / lower triangle matrix needed Since nj, nkimplies nk, njUnweighted graph Matrix elements ⇒⇒⇒⇒booleanWeighted graph Matrix elements ⇒⇒⇒⇒weight5Adjacency ListRepresentationFor each node, storeList of neighbors / successorsLinked listArray listFor weighted graph Also store weight for each edgeUndirected graphFor every edge (a, b)Nodes a & b need to store each other as neighborDirected graphMay also need to store list of predecessors6Adjacency ListExampleUnweighted graph Weighted graph7Adjacency Set / MapRepresentationFor each node, store Set or map of neighbors / successorsFor unweighted graphUse set of neighborsFor weighted graphUse map of neighbors, w/ value = weight of edgeUndirected graphFor every edge (a, b)Nodes a & b need to store each other as neighborFor directed graphMay also need to store map of predecessors8Graph Space RequirementsAdjacency matrix ½ N2 entries (for graph with N nodes, E edges) Many empty entries for large, sparse graphsAdjacency list2×E entriesAdjacency set / map2×E entriesSpace overhead per entry Higher than for adjacency list9Graph Time RequirementsAdjacency matrix Can find individual edge (a,b) quicklyExamine entry in array Edge[a,b]Constant time operationAdjacency list / set / mapCan find all edges for node (a) quicklyIterate through collection of edges for aOn average E / N edges per node10Graph Time RequirementsAverage Complexity of operationsFor graph with N nodes, E edgesO(E/N)O(1)O(1)O(1)Adj Set/MapO(E/N)O(1)Find edgeO(E/N)O(N)Enumerate edges for nodeO(E/N)O(1)Delete edgeO(E/N)O(1)Insert edgeAdj ListAdj MatrixOperation11Choosing Graph ImplementationsGraph densityRatio edges to nodes (dense vs. sparse)Graph algorithmNeighbor basedFor each node X in graphFor each neighbor Y of X // adj list faster if sparsedoWork( )Connection basedFor each node X in …For each node Y in …if (X,Y) is an edge // adj matrix faster if densedoWork( )12Single Source Shortest PathCommon graph problem1.Find path from X to Y with lowest edge weight2.Find path from X to any Y with lowest edge weightUseful for many applicationsShortest route in mapLowest cost tripMost efficient internet routeDijkstra’s algorithm solves problem 2 Can also be used to solve problem 1Would use different algorithm if only interested in a single destination13Shortest Path – Dijkstra’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 cost14Shortest Path – Intuition for Dijkstra’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 S15Shortest Path – Intuition for Djikstra’sUpdate distance to J after adding node KPrevious shortest path to K already in C[ K ]Possibly shorter path to J by going through node KCompare C[ J ] with C[ K ] + weight of (K,J), update C[ J ] if needed16Shortest Path – Dijkstra’s AlgorithmS = ∅∅∅∅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 algorithm17Dijkstra’s Shortest Path ExampleInitial stateS = ∅∅∅∅none∞∞∞∞5none∞∞∞∞4none∞∞∞∞3none∞∞∞∞2none01PC18Dijkstra’s Shortest Path ExampleFind shortest paths starting from node 1S = 1none∞∞∞∞5none∞∞∞∞4none∞∞∞∞3none∞∞∞∞2none01PC19Djikstra’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) = 8none∞∞∞∞5none∞∞∞∞4183152none01PC20Djikstra’s Shortest Path ExampleFind node K with smallest C[K] and add to S S = { 1, 2 }none∞∞∞∞5none∞∞∞∞4183152none01PC21Dijkstra’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) = 15none∞∞∞∞52154263152none01PC22Dijkstra’s Shortest Path ExampleFind node K with smallest C[K] and add to SS = { 1, 2, 3 }none∞∞∞∞52154263152none01PC23Dijkstra’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) = 9none∞∞∞∞5394263152none01PC24Dijkstra’s Shortest Path ExampleFind node K with smallest C[K] and add to S{ S } = 1, 2, 3, 4none∞∞∞∞5394263152none01PC25Dijkstra’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) = 184185394263152none01PC26Dijkstra’s Shortest Path ExampleFind node K with smallest C[K] and add to SS = { 1, 2, 3, 4, 5 }4185394263152none01PC27Dijkstra’s Shortest Path ExampleAll nodes in S, algorithm is finishedS = { 1, 2, 3, 4, 5 }4185394263152none01PC28Dijkstra’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 →→→→
View Full Document
Unlocking...