CMSC 451 Shortest Paths in a Graph Slides By Carl Kingsford Department of Computer Science University of Maryland College Park Based on Chapter 4 5 of Algorithm Design by Kleinberg Tardos Shortest Paths in a Weighted Directed Graph Given a directed graph G with lengths e on each edge e u 1 1 x 4 s 2 1 2 1 3 v w z 3 y Goal Find the shortest path from a given node s to every other node in the graph Shortest Paths Shortest Paths Given directed graph G with n nodes and non negative lengths on each edge find the n shortest paths from a given node s to each vi Dijkstra s algorithm 1959 solves this problem If we have an undirected graph we can replace each undirected edge by 2 directed edges k k k If all the edge lengths are 1 how can we solve this Shortest Paths Shortest Paths Given directed graph G with n nodes and non negative lengths on each edge find the n shortest paths from a given node s to each vi Dijkstra s algorithm 1959 solves this problem If we have an undirected graph we can replace each undirected edge by 2 directed edges k k k If all the edge lengths are 1 how can we solve this BFS Shortest Paths Tree There is some optimal set of shortest paths such that their union forms a tree General Tree Growing Dijkstra s algorithm is just a special case of tree growing Let T be the current tree T and Maintain a list of frontier edges the set of edges of G that have one endpoint in T and one endpoint not in T v Repeatedly choose a frontier edge somehow and add it to T Tree Growing TreeGrowing graph G vertex v func nextEdge T v S set of edges incident to v While S is not empty e nextEdge G S T T e add edge e to T S updateFrontier G S e return T The function nextEdge G S returns a frontier edge from S updateFrontier G S e returns the new frontier after we add edge e to T nextEdge for Shortest Path Let u be some node that we ve already visited it will be in S Let d u be the length of the path found for node u S nextEdge return the frontier edge u v for which d u length u v is minimized Example x u 1 1 d s 0 d u 1 green gives frontier s 3 4 3 w 2 v 2 4 y x u 1 1 d w 2 s 3 4 3 w 2 v 2 4 y Analysis Theorem Let T be the set of nodes explored at some point during the algorithm For each u T the path to u found by Dijkstra s algorithm is the shortest Proof By induction on the size of T Base case When T 1 the only node in T is s for which we ve obviously found the shortest path Induction Hypothesis Assume theorem is true when T k Let v be the k 1 node added using edge u v Let Pv be the path chosen by Dijkstra s to v and let P be any other path from s to v Then we have the situation on the next slide Proof cont x y s T Blue alternative path to v y v path must have length 0 u v k 1 node added v The path to v chosen by Dijkstra s is of length the alternative blue path