Dijkstra's algorithm Find the shortest path from a given source node to all other nodes Requires non-negative arc weights Algorithm works in stages Stage k: the k closest nodes to the source have been found Stage k+1: Given k closest nodes to the source node, find k+1st Key observation: the path to the k+ 1st closest nodes includes only nodes from among the k closest nodes Let M be the set of nodes already incorporated by the algorithm Start with Dn dsn for all n(Dn shortest path distance from node n to the source node Repeat until MEN Find node weM which has the next least cost distance to the source node Add w to m Update distances: Dn= min Dn, Dw+ dwn](for all nodes n EM) Notice that the update of Dn need only be done for nodes not already in M and that the update only requires the computation of a new distance by going through the newly added node wEytan Modiano Slide 12 Dijkstra's algorithm • Find the shortest path from a given source node to all other nodes – Requires non-negative arc weights • Algorithm works in stages: – Stage k: the k closest nodes to the source have been found – Stage k+1: Given k closest nodes to the source node, find k+1st. • Key observation: the path to the k+1st closest nodes includes only nodes from among the k closest nodes • Let M be the set of nodes already incorporated by the algorithm – Start with Dn = dsn for all n (Dn = shortest path distance from node n to the source node – Repeat until M=N Find node w∉M which has the next least cost distance to the source node Add w to M Update distances: Dn = min [ Dn, Dw + dwn] (for all nodes n ∉M) – Notice that the update of Dn need only be done for nodes not already in M and that the update only requires the computation of a new distance by going through the newly added node w