Here is another way to compute shortest paths. We compute
Initially
Note that the shortest path from s to t will never go through a loop, because we can remove the loop and get a shorter path. Thus, we only need to find paths of length at most N-1.
This is called the Floyd-Warshall algorithm.
We can compute this by storing the values in a 3 dimensional array SP. Assume the vertices are numbered [1,2,...,n]
We maintain the value shortestpath(s,t,i) as SP[s,t,i].
SP[s,t,0] = 0 if s = t, infinity otherwise for (i = 1; i < n; i++){ for (t = 1; t <= n; t++){ /* SP[s,t,i] = min (SP[s,t,i-1], min SP[s,u,i]+W[u,t]) u */ SP[s,t,i] = SP[s,t,i-1]; for (u = 1; u <= n; u++){ SP[s,t,i] = min(SP[s,t,i],SP[s,u,i-i]+W[u,t]); } } }
This algorithm takes time n^{3} to compute SP[s,t,n-1].
Note that to compute SP[s,t,i], we only need
SP[s,t,i-1],
so we can make do with just two 2-dimensional arrays of
size n×n that we use alternately, rather than a
3-dimensional array of size n×n×n.
Claim: Floyd-Warshall can compute shortest paths in situations that Dijkstra does not.
Suppose we can have negative edge weights. If we have cycles with a total negative weight, the notion of shortest path does not make sense because we can go around the negative cycle as many times as we want and reduce the overall weight. So, let us permit negative edge weights, provided they do not induce negative cycles.
Video lectures on shortest paths, NPTEL online course on Design and Analysis of Algorithms
©IARCS 2012–2016
PÄ›stujeme web | visit: Skluzavky