Shortest Paths and Dynamic Programming for Urban Traffic Analysis

Chapter 9 Shortest Paths and Discrete Dynamic Programming

Example 9.1 Littleville Suppose that you are the city traffic engineer for the town of Littleville. Figure 9.1(a) depicts the arrangement of one- and two-way streets in a proposed improvement plan for Littleville s downtown, including the estimated average time in seconds that a car will require to transit each block. From survey and other data we can estimate how many driver trips originate at various origin points in the town, and the destination for which each trip is bound. But such survey data cannot indicate what streets will be selected by motorists to move from origin to destination in a street network that does not yet exist.

Example 9.1 Littleville One of the tasks of a traffic engineer is to project the route that drivers will elect, so that city leaders can evaluate whether flows will concentrate where they hope. A good starting point is to assume that drivers will do the most rational thing-follow the shortest time path from their origin to their destination. We need to compute all such shortest paths.

Example 9.1 Littleville 20 18 12 18 36 32 18 28 30 13 38

Example 9.1 Littleville 20 18 8 1 5 12 18 36 32 2 6 18 9 28 30 3 7 13 38 4 10

9.1 Shortest Path Models Urban traffic, Satellite communications, or surface of a microchip. Mathematical graphs model travel, flow, and adjacency patterns in a network. [9.1] The nodes or vertices of a graph represent entities, intersections, and transfer points of the network. [9.2] The arcs of a graph model available directed (one-way) links between nodes. Edges represent undirected (two- way) links. [9.3]

9.1 Shortest Path Models A path is a sequence of arcs or edges connecting two specified nodes in a graph. Each arc or edge must have exactly one node in common with its predecessors in the sequence, any arcs must passed in the forward direction, and no node may be visited more than once. [9.4]

Shortest Path Problems Shortest path problems seek minimum total length paths between specified pairs of nodes in a graph. [9.5]

Example 9.1 Littleville 20 Name: Littleville Graph: arcs and edges Costs: nonnegative Output: shortest paths Pairs: all nodes to all others 18 8 1 5 12 18 36 2 6 18 9 28 3 7 13 38 4 10

Example 9.2 Texas Transfer Texas Transfer, a major trucker in the southwest, ships goods from its hub warehouse in Ft. Worth to all the cities shown. Trucks leave the hub and proceed directly to their destination city, with no intermediate dropoffs or pickups. Texas Transfer drivers are allowed to choose their own route from Ft. Worth to their destination. However, management s proposal in current labor negotiations calls for drivers to be paid on the basis of shortest standard mileage to the location. That is, they will be paid according to the length of the shortest path from Ft. Worth to their destination city in the network of Figure 9.3. To see the impact of this proposal, we need to compute such shortest path distances for all cities.

Example 9.2 Texas Transfer Notice that the character of this shortest path task differs significantly from the Littleville example. Here we need only optimal path lengths, not the paths themselves. Also, we need shortest path lengths for only one origin or source the Ft. Worth hub.

Example 9.2 Texas Transfer Name: Texas Transfer Graph: edges only Costs: nonnegative Output: shortest path lengths Pairs: one node to all others Amarillo 1 Ft. Worth 3 Lubbock 2 Abilene 5 Austin 8 6 Houston San Angelo 4 9 El Paso 7 San Antonio 10 Corpus Christi

Example 9.3 Two Ring Circus The Two Ring Circus is nearing the end of its season and planning a return to winter headquarters near Tallahassee, Florida. Present commitments will end in Lincoln, Nebraska, but there are still some opportunities for bookings in cities along the route home. Figure 9.4(a) shows the travel routes available and the estimated costs (in $1000) of moving the circus over those routes. It also designates the cities where bookings have been offered and the anticipated net receipts (in thousands of dollars). We want to compute the optimal path home for Two Ring. Notice that the cost of a path is the difference of travel costs and net receipts from performances along the way. But receipts occur at nodes of the network, not on edges as shortest path models require.

Example 9.3 Two Ring Circus Lincoln (0.0) 2 Davenport (1.6) 1 Springfield (1.5) 4 Wichita (3.2) 3 Chattanooga(3.0) 6 Little Rock(3.0) 5 2.6 Montgomery (1.5) Jackson(1.0) 7 8 9 Tallahassee(0.0)

Undirected and Directed Graph (Digraph) A shortest path problems including edges (i, j) of cost ci,j can be converted to an equivalent one on a digraph by replacing each edge with a pair of opposed arcs as [9.6] ci,j ci,j i i j j cj,i

Example 9.3 Two Ring Circus Lincoln (0.0) 2 Davenport (1.6) 1 Springfield (1.5) 4 Wichita (3.2) 3 Chattanooga (3.0) 6 Little Rock(3.0) 5 2.6 2.6 Montgomery (1.5) Jackson(1.0) 7 8 9 Tallahassee(0.0)

Two Ring Example Model Lincoln Davenport 2 1 Name: Two Ring Circus Graph: directed Costs: arbitrary Output: shortest path Pairs: one source to one destination Springfield 4 Wichita 3 Chattanooga 6 5 Little Rock 1.1 1.6 Montgomery 7 8 Jackson 9 Tallahassee

9.2 Dynamic Programming Approach to Shortest Paths Dynamic programming methods exploit the fact that it is sometimes easiest to solve one optimization problem by taking on an entire family. Shortest path algorithms exploit relationships among optimal paths (and path lengths) for different pairs on the nodes. [9.7]

Functional Notation for One Source to All Other Nodes [k] length of a shortest path from the source node to the node k (= + if no path exists) xi,j[k] 1 if arc/edge (i, j) is part of the optimal path from the source node to node k 0 otherwise

Functional Notation for All Nodes to All Other Nodes [k, l] length of a shortest path from node k to the node l (= + if no path exists) xi,j[k, l] 1 if arc/edge (i,j) is part of the optimal path from the node k to node l 0 otherwise

Optimal Paths and Subpaths If the highlighted path (through Austin and San Antonio) is the shortest from Ft. Worth to Corpus Christi, the subpath from Ft. Worth to San Antonio must also be the shortest. (No negative dicycle) Amarillo 1 Ft. Worth 3 Lubbock 2 Abilene 5 Austin 8 Houston 6 San Angelo 4 9 El Paso 7 San Antonio 10 Corpus Christi

Negative Dicycles Exception A dicycle is a path that begins and ends at the same node, and a negative dicycle is a dicycle of negative total length. [9.8] Shortest path models with negative dicycles are much less tractable than other cases because dynamic programming methods usually do not apply. [9.9] [1]=0 [2]=-3 2 2 1 -25 10 12 3 4 [3]=5 [4]=17

Principle of Optimality In a graph with no negative dicycles, optimal paths must have optimal subpaths. [9.10] Functional equations of a dynamic program encode the recursive connections among optimal solution values that are implied by a principle of optimality. [9.11]

Functional Equations for One Node to All Others The functional equations for shortest path problems from a single source s in a graph with no negative dicycles are [9.12] [s] = 0 [k] = min { [i] + ci,k : (i, k) exists} all k s

Sufficiency of Functional Equations in One to All Case Node value [k] in a graph with no negative dicycles are lengths of shortest paths from a given source s if and only if they satisfy functional equations in [9.12]. [9.13]

Sufficiency of Functional Equations in One to All Case [4]= [5]+ c5,4 [5]= [3]+ c3,5 [4]+ [5] = [5]+ c5,4+ [3]+ c3,5 [4]=cs,5+ c5,4 Amarillo [1]=359 1 Ft. Worth [3]=0 3 Lubbock [2]=347 2 Abilene [5]=180 5 Austin [8]=195 8 6 [4] cs,1+ c1,2+c2,4 Houston [9]=246 San Angelo [6]=272 4 9 El Paso [4]=623 7 San Antonio [7]=274 10 Corpus Christi [10]=427

Functional Equations for All Nodes to All Others The functional equations for shortest path problems from a single source s in a graph with no negative dicycles are [9.14] [k,k] = 0 all k [k,l] = min {ck,l, { [k,i] + [i,l] : i k, l}} all k l Node pair values [k,l] in a graph with no negative dicycles are lengths of shortest paths from k to l if and only if they satisfy functional equations in [9.14]. [9.15]

Solving Shortest Path Problems by Linear Programming Although shortest path problems over graphs with no negative dicycles can be solved by linear programming, dynamic programming methods based on the principle of optimality are far more efficient. [9.16]

9.3 Shortest Paths from One Node to All Others: Bellman-Ford Solving the functional equations can be carried out by calculating the single value [k] (one-pass evaluation). Dicycles introduce circular dependencies in functional equations that preclude their solution by one-pass evaluation, even if the length of all dicycles is non- negative. [9.17]

Repeated Evaluation Algorithm: Bellman-Ford (t)[k] value of [k] obtained on the tth iteration d[k] node preceding k in the best known path from s to k.

Algorithm 9A: One to All (no Negative Dicycles) Bellman-Ford Step 0: Initiation. With s the source node, initialize optimal path lengths (0)[k] = 0 if k=s = + otherwise and set iteration counter t 1 Step 1: Evaluation. For each k evaluate if (t)[k] < (t-1)[k], also set d[k] the number of a neighboring node i achieving the minimum (t)[k]. (t)[k] min { (t-1) [i] + ci,k : (i, k) exists}

Algorithm 9A: One to All (no Negative Dicycles) Bellman-Ford Step 2: Stopping. Terminate if (t)[k] < (t-1)[k] for every k, or if t= the number of nodes in the graph. Value (t)[k] then equal the required shortest path lengths unless some (t)[k] changed at the last t, in which case the graph contains a negative dicycle. Step 3: Advance. If some [k] changed and t < the number of nodes, increment t t+1 and return to Step 1.

Two Ring Example Model Lincoln Davenport 2 1 Springfield 4 Wichita 3 Chattanooga 6 5 Little Rock 1.1 1.6 Montgomery 7 8 Jackson 9 Tallahassee

Bellman-Ford Solution of the Two Ring Circus Example (t)[1] (t)[2] + 3.6 (t)[3] + 2.8 (t)[5] + (t)[6] + (t)[7] + (t)[8] + (t)[9] + (t)[4] + 4.6 3.7 t 0 1 2 3 4 5 t 1 2 3 4 5 0 4.1 5.7 3.2 4.8 6.7 5.5 d[9] d[1] d[2] 1 d[3] 1 d[5] d[6] d[7] d[8] d[4] 1 2 3 5 5 7 7 8

Bellman-Ford Algorithm At the completion of Bellman-Ford Algorithm, a shortest path from source s to any other node k can be recovered by starting at k, backtracking to neighboring node d[k], and continuing with an optimal path from s to the neighbor until source s is encountered. [9.18] If Bellman-Ford Algorithm encounters negative dicycles, it will demonstrate their presence by continuing to change (t)[k] on iteration t = the number of nodes. Any node k with such changing (t)[k] belongs to a negative dicycle. [9.19]

Two Ring Example Model Lincoln Davenport 2 1 Springfield 4 Wichita 3 Chattanooga 6 5 Little Rock 1.1 1.6 Montgomery 7 8 Jackson 9 Tallahassee

9.4 Shortest Paths from All Nodes to All Others: Floyd-Warshall (t)[k, l] length of a shortest path for k to l using only intermediate nodes numbered less than or equal to t. d[k, l] node just before l on the current path from k to l.

Algorithm 9B: All to All (no Negative Dicycles) Floyd-Warshall Step 0: Initiation. All nodes should have consecutive positive numbers starting with 1. For all arcs and edges (k, l) in the graph, initialize (0)[k, l] ck,l For k, l pairs with no arc/edge (k, l), assign (0)[k, l] = 0 if k=l also set iteration counter t 1 Step 1: Evaluation. For all k, l t update (t)[k, l] min { (t-1) [k, l], (t-1) [k, t]+ (t-1) [t, l]} if (t)[k, l] < (t-1)[k, l], also set d[k, l] d[t, l] d[k, l] k =+ otherwise

Algorithm 9B: All to All (no Negative Dicycles) Floyd-Warshall Step 2: Stopping. Terminate if t = the number of nodes in the graph, or if (t)[k, k] < 0 for any node k. Value (t)[k, l] then equal the required shortest path lengths unless some (t)[k, k] is negative, in which case the graph contains a negative dicycle through k. Step 3: Advance. If t < the number of nodes and (t)[k,k] 0, increment t t+1 and return to Step 1.

Example 9.1 Littleville 20 18 8 1 5 12 18 36 32 2 6 18 9 28 30 3 7 13 38 4 10

Floyd-Warshall Solution of the Littleville Example l=1 0 20 l=2 12 0 32 l=3 18 0 30 l=4 13 0 l=5 0 18 18 l=6 32 18 0 28 25 l=7 30 0 21 49 l=8 0 36 28 l=9 25 21 36 0 40 l=10 38 49 40 0 Nu k=1 k=2 k=3 k=4 k=5 k=6 k=7 k=8 k=9 k=10 d k=1 k=2 k=3 k=4 k=5 k=6 k=7 k=8 k=9 k=10 1 2 2 3 3 4 5 5 6 6 6 7 8 7 7 7 8 9 9 10 9 10 9 10

Floyd-Warshall Solution of the Littleville Example l=1 0 20 l=2 12 0 32 32 l=3 18 0 30 l=4 13 0 l=5 0 18 18 l=6 32 18 0 28 25 l=7 30 0 21 49 l=8 0 36 28 l=9 25 21 36 0 40 l=10 38 49 40 0 Nu k=1 k=2 k=3 k=4 k=5 k=6 k=7 k=8 k=9 k=10 d k=1 k=2 k=3 k=4 k=5 k=6 k=7 k=8 k=9 k=10 1 2 2 3 3 4 5 1 6 5 6 6 7 8 7 7 7 8 9 9 10 9 10 9 10

Floyd-Warshall Solution of the Littleville Example l=1 0 20 l=2 12 0 32 32 l=3 30 18 0 50 50 30 l=4 13 0 l=5 0 18 18 l=6 44 32 18 0 28 25 l=7 30 0 21 49 l=8 0 36 28 l=9 25 21 36 0 40 l=10 38 49 40 0 Nu k=1 k=2 k=3 k=4 k=5 k=6 k=7 k=8 k=9 k=10 d k=1 k=2 k=3 k=4 k=5 k=6 k=7 k=8 k=9 k=10 1 2 2 2 2 3 3 4 5 1 6 2 2 7 5 6 6 7 8 7 7 8 9 9 9 9 10 10 10

Floyd-Warshall Solution of the Littleville Example l=1 0 20 l=2 12 0 32 32 l=3 30 18 0 50 50 30 l=4 43 31 13 0 63 63 43 l=5 0 18 18 l=6 44 32 18 0 28 25 l=7 60 48 30 80 80 0 21 49 l=8 0 36 28 l=9 25 21 36 0 40 l=10 38 49 40 0 Nu k=1 k=2 k=3 k=4 k=5 k=6 k=7 k=8 k=9 k=10 d k=1 k=2 k=3 k=4 k=5 k=6 k=7 k=8 k=9 k=10 1 2 2 3 3 3 2 2 3 3 3 4 5 1 6 2 2 7 3 3 3 5 3 3 6 6 7 8 7 7 8 9 9 9 9 10 10 10

Floyd-Warshall Solution of the Littleville Example l=1 0 70 96 104 20 38 66 38 63 66 l=2 12 0 90 116 32 32 60 50 57 78 l=3 30 18 0 117 50 50 30 68 51 79 l=4 43 31 13 0 63 63 43 81 64 92 l=5 62 50 76 84 0 18 46 18 43 46 l=6 44 32 58 102 18 0 28 36 25 64 l=7 60 48 30 87 80 80 0 96 21 49 l=8 105 93 79 66 79 61 57 0 36 28 l=9 69 57 51 78 43 25 21 36 0 40 l=10 81 69 51 38 83 65 49 76 40 0 Nu k=1 k=2 k=3 k=4 k=5 k=6 k=7 k=8 k=9 k=10 d k=1 k=2 k=3 k=4 k=5 k=6 k=7 k=8 k=9 k=10 1 2 2 3 3 3 6 6 7 10 2 2 7 10 5 3 3 3 10 3 3 9 9 10 10 9 9 9 6 6 7 10 6 6 7 8 4 4 4 4 9 9 7 9 9 6 7 10 5 5 6 5 6 8 7 10 1 6 6 5 6 8 10 2 2 7 5 7 7 3 3 3 5 7 7 6 6 8 6 8 7 5 9 8 5 9 10 9 10 10

Floyd-Warshall Algorithm At the completion of Floyd-Warshall Algorithm, a shortest path from any node k to any other node l can be recovered by starting at l, backtracking to neighboring node d[k, l], and continuing with an optimal path from k to the neighbor until source k itself is encountered. [9.20] If Floyd-Warshall Algorithm is applied to a graph with negative dicycles, it will demonstrate their presence by making some (t)[k,k] < 0 and terminating. Under those circumstances, the implied negative dicycle includes node k. [9.21]

9.5 Shortest Path from One Node to All Others with Cost Non-negative: Dijkstra The bellman-Ford and Floyd-Warshall algorithms can solve any of the shortest path models without negative dicycles. With further assumptions, other algorithms may be more efficient.

Algorithm 9C: One to All (Non-Negative Costs): Dijkstra Step 0: Initiation. With s the source node, initialize optimal path lengths [i] = 0 if i=s = + otherwise Then mark all nodes temporary, and choose p s as the next permanently labeled node. Step 1: Processing. Mark node p permanent, and for every arc/edge (p, i) leading from p to a temporarynode, update if [i] changed in value, also set d[k] p. [i] min { [i], [p] + cp,i}

Algorithm 9C: One to All (Non-Negative Costs): Dijkstra Step 2: Stopping. If no temporary nodes remain, stop; values [i] now reflect the required shortest path lengths. Step 3: Next Permanent. Choose as next permanently labeled node p a temporary node with least current value [i], that is, [p] = min { [i] : i temporary } Then return to Step 1.

Permanently and Temporary Labeled Nodes Once a node is classified permanent by Dijkstra Algorithm, its [p] and d[p] labels never change again. Nodes that are not yet permanently labeled are classified temporary. [9.22] Dijkstra Algorithm is the most efficient method available for computing shortest paths from one node to all others in (general) graphs and digraphs having all are/edge costs non-negative. [9.23] Each iteration of Dijkstra s Algorithm selects as the new permanently labeled node p a temporary node of minimum [i]. [9.24]