6.006 Intro to Algorithms Recitation 14 March 30, 2011Shortest PathsIn the past, we were able to use breadth-first search to find the shortest paths between a sourcevertex to all other vertices in some graph G. We weighed each edges equally so the shortest pathbetween two vertices was the one that contained the fewest edges. Now, we introduce edge weightsso the cost of traveling through edges can differ from edge to edge. The shortest path between twovertices is defined to be the path whose sum of edge weights is the least. BFS will not work onweighted graphs since the path with the fewest edges may not be the shortest if the edges it containsare expensive.There are several variants on the shortest paths problem and the algorithms that we will go overthat correspond to solving each problem are in parentheses:• Single-source shortest-paths problem: Find a shortest path from a source vertex to eachother vertex in the graph (Bellman-Ford, Dijkstra)• Single-destination shortest-paths problem: Find a shortest path to a destination vertexfrom each other vertex in the graph (Bellman-Ford/Dijkstra on reversed graph)• Single-pair shortest-path problem: Find a shortest path between a vertex u and a vertexv in a graph (Bellman-Ford, Dijkstra)• All-pairs shortest-paths problem: Find a shortest path between every two vertices in agraph (Bellman-Ford/Dijkstra V times, Floyd-Warshall)Before getting into Bellman-Ford and Dijkstra, we will go over the principles the algorithmsare built upon.NotationBellman-Ford and Dijkstra both solve the problem of finding a shortest path from a source vertexto each other vertex in the graph. We will designate the source vertex as s. Every vertex v in thegraph is augmented with the following parameters:• v.d - The weight of the current shortest path from s to v. This is initialized to be ∞ forall vertices besides the source vertex but decreases as paths are found and shorter paths arediscovered. At the end of the algorithms, this will be the weight of the shortest path. s.d isinitialized to be 0.• v.π - The parent vertex of v in the current shortest path. This is initialized to be NIL but getsset to a vertex once a path is discovered from s to v. As shorter paths to v are discovered,the parent updates to reflect the change. At the end of the algorithms, this will be the parentof v in the shortest path to v. s.π will always be NIL.Also,6.006 Intro to Algorithms Recitation 14 March 30, 2011• w(u, v) is the weight of the edge from vertex u to vertex v• δ(u, v) is the weight of the shortest path from vertex u to vertex vRelaxationInitializing the algorithms involves setting v.d to ∞ and v.π to NIL. Throughout the course of thealgorithms, we will need to update these values to find shortest paths.The idea is that if we found a path costing u.d from s to u and there is an edge from u to v,then the upper bound on the weight of a shortest path from s to v is u.d plus the weight of the edgebetween u and v. We can thus compare u.d + w(u, v) to v.d and update v.d if u.d + w(u, v) issmaller than the current v.d. In pseudocode, relaxing the edge (u, v) is:RELAX(u, v):if v.d > u.d + w(u, v) ## if we find a shorter path to v through uv.d = u.d + w(u, v) ## update current shortest path weight to vv.pi = u ## update parent of v in current shortest path to vBoth Bellman-Ford and Dijkstra use relaxation to discover shortest paths. The difference be-tween the two is the order in which edges are relaxed.Properties of Shortest PathsUsing our definitions of shortest paths and relaxations, we can come up with several properties.These can all be found in CLRS in chapter 24Triangle inequality: For any edge (u, v), we have δ(s, v) ≤ δ(s, u) + w(u, v). In english, theweight of the shortest path from s to v is no greater than the weight of the shortest path from s tou plus the weight of the edge from u to v.Optimal substructure: Let {v1, v2, v3, ..., vk} be a shortest path that goes from v1to vkthrough the vertices v2through vk−1. Any subpath {vi, vi+1, ..., vj−1, vj} must be a shortest pathfrom vito vj. That is, a shortest path is constructed of shortest paths between any two vertices inthe path.Upper-bound property: We always have v.d ≥ δ(s, v) for all vertices v. Once v.d = δ(s, v),it never changes.No-path property: If there exists no path from s to v, v.d will always be ∞.Convergence property: If a shortest path from s to v contains the edge (u, v) and u.d =δ(s, u) before relaxing edge (u, v), then v.d = δ(s, v) at all times after relaxing edge (u, v).6.006 Intro to Algorithms Recitation 14 March 30, 2011Path-relaxation property: Let {v1, v2, v3, ..., vk} be a shortest path that goes from v1to vk.If the edges are relaxed in the order (v1, v2), (v2, v3), etc., then vk.d = δ(s, vk) once the whole pathis relaxed.Predecessor-subgraph property: Once v.d = δ(s, v) for all vertices v, the predecessor sub-graph is a shortest-paths tree rooted at s. The predecessor subgraph is the subgraph of G thatcontains all the vertices with a finite distance from s (i.e. reachable from s) and only the edges thatconnect v to
View Full Document
Unlocking...