The A-Pairs Shortest Path Problem Let G=(,E)be a directed graph in which each edge (has a non-negative length i.If there is no edge from vertex /ito vertex j,then i=o. The problem is to find the distance from each vertex to all other vertices,where the distance from vertex x to vertex yis the length of a shortest path from xto y ■ For simplicity,we will assume that V1,2,...,n. Let iand j be two different vertices in V.Define dto be the length of a shortest path from /to /that does not pass through any vertex in {k+1,k+2,...,n
The All-Pairs Shortest Path Problem ◼ Let G=(V, E) be a directed graph in which each edge (i, j) has a non-negative length l[i, j]. If there is no edge from vertex i to vertex j, then l[i, j]=. ◼ The problem is to find the distance from each vertex to all other vertices, where the distance from vertex x to vertex y is the length of a shortest path from x to y. ◼ For simplicity, we will assume that V={1, 2, …, n}. Let i and j be two different vertices in V. Define to be the length of a shortest path from i to j that does not pass through any vertex in {k+1, k+2, …, n}. , k i j d
The A-Pairs Shortest Path Problem d,=li,] d is the length of a shortest path from /to /that does not pass through any vertex except possibly vertex 1 dis the length of a shortest path from /to jthat does not pass through any vertex except possibly vertex 1 or vertex 2 or both ● d is the length of a shortest path from /to,i.e.the distance from ito
◼ ◼ is the length of a shortest path from i to j that does not pass through any vertex except possibly vertex 1 ◼ is the length of a shortest path from i to j that does not pass through any vertex except possibly vertex 1 or vertex 2 or both ◼ is the length of a shortest path from i to j, i.e. the distance from i to j The All-Pairs Shortest Path Problem 0 , [ , ] i j d l i j = 1 i j , d 2 i j , d , n i j d
The A-Pairs Shortest Path Problem We can compute drecursively as follows: i,] ifk=0 4-{mna,d城+a ifl≤k≤n
◼ We can compute recursively as follows: The All-Pairs Shortest Path Problem , k i j d , 1 1 1 , , , [ , ] if 0 min , if 1 k i j k k k i j i k k j l i j k d d d d k n − − − = = +
The A-Pairs Shortest Path Problem Floyd Algorithm:use n+1 matrices Do,Di,D2,..., D,of dimension nxn to compute the lengths of the shortest constrained paths. Initially,we set D[i=0,Do[i=[i刀if≠jand(G) is an edge in G otherwise Doli,=o. We then make m iterations such that after the kth iteration,Di,]contains the value of a shortest length path from vertex /to vertex /that does not pass through any vertex numbered higher than k
The All-Pairs Shortest Path Problem ◼ Floyd Algorithm: use n+1 matrices D0 , D1 , D2 , …, Dn of dimension nn to compute the lengths of the shortest constrained paths. ◼ Initially, we set D0 [i, i]=0, D0 [i, j]=l[i, j] if ij and (i, j) is an edge in G; otherwise D0 [i, j]=. ◼ We then make n iterations such that after the kth iteration, Dk [i, j] contains the value of a shortest length path from vertex i to vertex j that does not pass through any vertex numbered higher than k
The Al-Pairs Shortest Path Problem Thus,in the kth iteration,we compute Dai using the formula Dii =mintDeili i,Deili k+Dilk i
The All-Pairs Shortest Path Problem ◼ Thus, in the kth iteration, we compute Dk [i, j] using the formula Dk [i, j]=min{Dk-1 [i, j], Dk-1 [i, k]+Dk-1 [k, j]}