CMSC 132 Object Oriented Programming II Graph Implementations Single Source Shortest Path Algorithm Department of Computer Science University of Maryland College Park 1 Graph Implementation How do we represent edges Adjacency matrix 2D array of neighbors Adjacency list List of neighbors Adjacency set map Set map of neighbors Important for very large graphs Affects efficiency storage 2 Adjacency Matrix Representation 2D array Position j k edge between nodes nj nk Example 3 Adjacency Matrix Representation cont Single array for entire graph Undirected graph Only upper lower triangle matrix needed Since nj nk implies nk nj Unweighted graph Matrix elements boolean Weighted graph Matrix elements weight 4 Adjacency List Representation For each node store List of neighbors successors Linked list Array list For weighted graph Also store weight for each edge Undirected graph For every edge a b Nodes a b need to store each other as neighbor Directed graph May also need to store list of predecessors 5 Adjacency List Example Unweighted graph Weighted graph 6 Adjacency Set Map Representation For each node store Set or map of neighbors successors For unweighted graph Use set of neighbors For weighted graph Use map of neighbors w value weight of edge Undirected graph For every edge a b Nodes a b need to store each other as neighbor For directed graph May also need to store map of predecessors 7 Graph Space Requirements Adjacency matrix N2 entries for graph with N nodes E edges Many empty entries for large sparse graphs Adjacency list 2 E entries Adjacency set map 2 E entries Space overhead per entry Higher than for adjacency list 8 Graph Time Requirements Adjacency matrix Can find individual edge a b quickly Examine entry in array Edge a b Constant time operation Adjacency list set map Can find all edges for node a quickly Iterate through collection of edges for a On average E N edges per node 9 Graph Time Requirements Average Complexity of operations For graph with N nodes E edges Operation Adj Matrix Adj List Adj Set Map Find edge O 1 O E N O 1 Insert edge O 1 O E N O 1 Delete edge O 1 O E N O 1 Enumerate edges for node O N O E N O E N 10 Choosing Graph Implementations Graph density Ratio edges to nodes dense vs sparse Graph algorithm Neighbor based For each node X in graph For each neighbor Y of X adj list faster if sparse doWork Connection based For each node X in For each node Y in if X Y is an edge doWork adj matrix faster if dense 11 Single Source Shortest Path Common graph problem 1 Find path from X to Y with lowest edge weight 2 Find path from X to any Y with lowest edge weight Useful for many applications Shortest route in map Lowest cost trip Most efficient internet route Dijkstra s algorithm solves problem 2 Can also be used to solve problem 1 Would use different algorithm if only interested in a single destination 12 Shortest Path Dijkstra s Algorithm Maintain Nodes with known shortest path from start S Cost of shortest path to node K from start C K Only for paths through nodes in S Predecessor to K on shortest path P K Updated whenever new lower C K discovered Remembers actual path with lowest cost 13 Shortest Path Intuition for Dijkstra s At each step in the algorithm Shortest paths are known for nodes in S Store in C K length of shortest path to node K for all paths through nodes in S Add to S next closest node S 14 Shortest Path Intuition for Djikstra s Update distance to J after adding node K Previous shortest path to K already in C K Possibly shorter path to J by going through node K Compare C J with C K weight of K J update C J if needed 15 Shortest Path Dijkstra s Algorithm S P none for all nodes C start 0 C for all other nodes while 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 K Optimal solution computed with greedy algorithm 16 Dijkstra s Shortest Path Example Initial state S C P 1 0 none 2 none 3 none 4 none 5 none 17 Dijkstra s Shortest Path Example Find shortest paths starting from node 1 S 1 C P 1 0 none 2 none 3 none 4 none 5 none 18 Djikstra s Shortest Path Example Update C K for all neighbors of 1 not in S S 1 C P 1 0 none 2 5 1 3 8 1 4 none 5 none C 2 min C 1 1 2 min 0 5 5 C 3 min C 1 1 3 min 0 8 8 19 Djikstra s Shortest Path Example Find node K with smallest C K and add to S S 1 2 C P 1 0 none 2 5 1 3 8 1 4 none 5 none 20 Dijkstra s Shortest Path Example Update C K for all neighbors of 2 not in S S 1 2 C P 1 0 none 2 5 1 3 6 2 4 15 2 5 none C 3 min 8 C 2 2 3 min 8 5 1 6 C 4 min C 2 2 4 min 5 10 15 21 Dijkstra s Shortest Path Example Find node K with smallest C K and add to S S 1 2 3 C P 1 0 none 2 5 1 3 6 2 4 15 2 5 none 22 Dijkstra s Shortest Path Example Update C K for all neighbors of 3 not in S S 1 2 3 C P 1 0 none 2 5 1 3 6 2 4 9 3 5 none C 4 min 15 C 3 3 4 min 15 6 3 9 23 Dijkstra s Shortest Path Example Find node K with smallest C K and add to S S 1 2 3 4 C P 1 0 none 2 5 1 3 6 2 4 9 3 5 none 24 Dijkstra s Shortest Path Example Update C K for all neighbors of 4 not in S S 1 2 3 4 C P 1 0 none 2 5 1 3 6 2 4 9 3 5 18 4 C 5 min C 4 4 5 min 9 9 18 25 Dijkstra s Shortest Path Example Find node K with smallest C K and add to S S 1 2 3 4 5 C P 1 0 none 2 5 1 3 6 2 4 9 3 5 18 4 26 Dijkstra s Shortest Path Example All nodes in S algorithm is finished S 1 2 3 4 5 C P 1 0 none 2 5 1 3 6 2 4 9 3 5 18 4 27 Dijkstra s Shortest Path Example Find shortest path from start to K …
View Full Document
Unlocking...