Floyd-Warshall algorithm: Difference between revisions
m →{{header|Sidef}}: code simplifications |
|||
Line 744: | Line 744: | ||
4 → 2 -1 4 → 2 |
4 → 2 -1 4 → 2 |
||
4 → 3 1 4 → 2 → 1 → 3 |
4 → 3 1 4 → 2 → 1 → 3 |
||
</pre> |
|||
=={{header|Phix}}== |
|||
Direct translation of the wikipedia pseudocode |
|||
<lang Phix>constant inf = 1e300*1e300 |
|||
function Path(integer u, integer v, sequence next) |
|||
if next[u,v]=null then |
|||
return "" |
|||
end if |
|||
sequence path = {sprintf("%d",u)} |
|||
while u!=v do |
|||
u = next[u,v] |
|||
path = append(path,sprintf("%d",u)) |
|||
end while |
|||
return join(path,"->") |
|||
end function |
|||
procedure FloydWarshall(integer V, sequence weights) |
|||
sequence dist = repeat(repeat(inf,V),V) |
|||
sequence next = repeat(repeat(null,V),V) |
|||
for k=1 to length(weights) do |
|||
integer {u,v,w} = weights[k] |
|||
dist[u,v] := w -- the weight of the edge (u,v) |
|||
next[u,v] := v |
|||
end for |
|||
-- standard Floyd-Warshall implementation |
|||
for k=1 to V do |
|||
for i=1 to V do |
|||
for j=1 to V do |
|||
atom d = dist[i,k] + dist[k,j] |
|||
if dist[i,j] > d then |
|||
dist[i,j] := d |
|||
next[i,j] := next[i,k] |
|||
end if |
|||
end for |
|||
end for |
|||
end for |
|||
printf(1,"pair dist path\n") |
|||
for u=1 to V do |
|||
for v=1 to V do |
|||
if u!=v then |
|||
printf(1,"%d->%d %2d %s\n",{u,v,dist[u,v],Path(u,v,next)}) |
|||
end if |
|||
end for |
|||
end for |
|||
end procedure |
|||
constant V = 4 |
|||
constant weights = {{1, 3, -2}, {2, 1, 4}, {2, 3, 3}, {3, 4, 2}, {4, 2, -1}} |
|||
FloydWarshall(V,weights)</lang> |
|||
{{out}} |
|||
<pre> |
|||
pair dist path |
|||
1->2 -1 1->3->4->2 |
|||
1->3 -2 1->3 |
|||
1->4 0 1->3->4 |
|||
2->1 4 2->1 |
|||
2->3 2 2->1->3 |
|||
2->4 4 2->1->3->4 |
|||
3->1 5 3->4->2->1 |
|||
3->2 1 3->4->2 |
|||
3->4 2 3->4 |
|||
4->1 3 4->2->1 |
|||
4->2 -1 4->2 |
|||
4->3 1 4->2->1->3 |
|||
</pre> |
</pre> |
||
Revision as of 12:36, 8 May 2017
You are encouraged to solve this task according to the task description, using any language you may know.
The Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights.
- Task
Find the lengths of the shortest paths between all pairs of vertices of the given directed graph. Your code may assume that the input has already been checked for loops, parallel edges and negative cycles.
Print the pair, the distance and (optionally) the path.
- Example
pair dist path 1 -> 2 -1 1 -> 3 -> 4 -> 2 1 -> 3 -2 1 -> 3 1 -> 4 0 1 -> 3 -> 4 2 -> 1 4 2 -> 1 2 -> 3 2 2 -> 1 -> 3 2 -> 4 4 2 -> 1 -> 3 -> 4 3 -> 1 5 3 -> 4 -> 2 -> 1 3 -> 2 1 3 -> 4 -> 2 3 -> 4 2 3 -> 4 4 -> 1 3 4 -> 2 -> 1 4 -> 2 -1 4 -> 2 4 -> 3 1 4 -> 2 -> 1 -> 3
- See also
EchoLisp
Transcription of the Floyd-Warshall algorithm, with best path computation. <lang scheme> (lib 'matrix)
- in
- initialized dist and next matrices
- out
- dist and next matrices
- O(n^3)
(define (floyd-with-path n dist next (d 0))
(for* ((k n) (i n) (j n))
#:break (< (array-ref dist j j) 0) => 'negative-cycle
(set! d (+ (array-ref dist i k) (array-ref dist k j)))
(when (< d (array-ref dist i j)) (array-set! dist i j d) (array-set! next i j (array-ref next i k)))))
- utilities
- init random edges costs, matrix 66% filled
(define (init-edges n dist next)
(for* ((i n) (j n))
(array-set! dist i i 0)
(array-set! next i j null) #:continue (= j i) (array-set! dist i j Infinity)
#:continue (< (random) 0.3) (array-set! dist i j (1+ (random 100)))
(array-set! next i j j)))
- show path from u to v
(define (path u v) (cond ((= u v) (list u)) ((null? (array-ref next u v)) null)
(else (cons u (path (array-ref next u v) v)))))
(define( mdist u v) ;; show computed distance (array-ref dist u v))
(define (task) (init-edges n dist next) (array-print dist) ;; show init distances (floyd-with-path n dist next)) </lang>
- Output:
(define n 8) (define next (make-array n n)) (define dist (make-array n n)) (task) 0 Infinity Infinity 13 98 Infinity 35 47 8 0 Infinity Infinity 83 77 16 3 73 3 0 3 76 84 91 Infinity 30 49 Infinity 0 41 Infinity 4 4 22 83 92 Infinity 0 30 27 98 6 Infinity Infinity 24 59 0 Infinity Infinity 60 Infinity 45 Infinity 67 100 0 Infinity 72 15 95 21 Infinity Infinity 27 0 (array-print dist) ;; computed distances 0 32 62 13 54 84 17 17 8 0 61 21 62 77 16 3 11 3 0 3 44 74 7 6 27 19 49 0 41 71 4 4 22 54 72 35 0 30 27 39 6 38 68 19 59 0 23 23 56 48 45 48 67 97 0 51 23 15 70 21 62 92 25 0 (path 1 3) → (1 0 3) (mdist 1 0) → 8 (mdist 0 3) → 13 (mdist 1 3) → 21 ;; = 8 + 13 (path 7 6) → (7 3 6) (path 6 7) → (6 2 1 7)
Elixir
<lang elixir>defmodule Floyd_Warshall do
def main(n, edge) do {dist, next} = setup(n, edge) {dist, next} = shortest_path(n, dist, next) print(n, dist, next) end defp setup(n, edge) do big = 1.0e300 dist = for i <- 1..n, j <- 1..n, into: %{}, do: {{i,j},(if i==j, do: 0, else: big)} next = for i <- 1..n, j <- 1..n, into: %{}, do: {{i,j}, nil} Enum.reduce(edge, {dist,next}, fn {u,v,w},{dst,nxt} -> { Map.put(dst, {u,v}, w), Map.put(nxt, {u,v}, v) } end) end defp shortest_path(n, dist, next) do (for k <- 1..n, i <- 1..n, j <- 1..n, do: {k,i,j}) |> Enum.reduce({dist,next}, fn {k,i,j},{dst,nxt} -> if dst[{i,j}] > dst[{i,k}] + dst[{k,j}] do {Map.put(dst, {i,j}, dst[{i,k}] + dst[{k,j}]), Map.put(nxt, {i,j}, nxt[{i,k}])} else {dst, nxt} end end) end defp print(n, dist, next) do IO.puts "pair dist path" for i <- 1..n, j <- 1..n, i != j, do: :io.format "~w -> ~w ~4w ~s~n", [i, j, dist[{i,j}], path(next, i, j)] end defp path(next, i, j), do: path(next, i, j, [i]) |> Enum.join(" -> ") defp path(_next, i, i, list), do: Enum.reverse(list) defp path(next, i, j, list) do u = next[{i,j}] path(next, u, j, [u | list]) end
end
edge = [{1, 3, -2}, {2, 1, 4}, {2, 3, 3}, {3, 4, 2}, {4, 2, -1}] Floyd_Warshall.main(4, edge)</lang>
- Output:
pair dist path 1 -> 2 -1 1 -> 3 -> 4 -> 2 1 -> 3 -2 1 -> 3 1 -> 4 0 1 -> 3 -> 4 2 -> 1 4 2 -> 1 2 -> 3 2 2 -> 1 -> 3 2 -> 4 4 2 -> 1 -> 3 -> 4 3 -> 1 5 3 -> 4 -> 2 -> 1 3 -> 2 1 3 -> 4 -> 2 3 -> 4 2 3 -> 4 4 -> 1 3 4 -> 2 -> 1 4 -> 2 -1 4 -> 2 4 -> 3 1 4 -> 2 -> 1 -> 3
FreeBASIC
<lang freebasic>' FB 1.05.0 Win64
Const POSITIVE_INFINITY As Double = 1.0/0.0
Sub printResult(dist(any, any) As Double, nxt(any, any) As Integer)
Dim As Integer u, v Print("pair dist path") For i As Integer = 0 To UBound(nxt, 1) For j As Integer = 0 To UBound(nxt, 1) If i <> j Then u = i + 1 v = j + 1 Print Str(u); " -> "; Str(v); " "; dist(i, j); " "; Str(u); Do u = nxt(u - 1, v - 1) Print " -> "; Str(u); Loop While u <> v Print End If Next j Next i
End Sub
Sub floydWarshall(weights(Any, Any) As Integer, numVertices As Integer)
Dim dist(0 To numVertices - 1, 0 To numVertices - 1) As Double For i As Integer = 0 To numVertices - 1 For j As Integer = 0 To numVertices - 1 dist(i, j) = POSITIVE_INFINITY Next j Next i
For x As Integer = 0 To UBound(weights, 1) dist(weights(x, 0) - 1, weights(x, 1) - 1) = weights(x, 2) Next x
Dim nxt(0 To numVertices - 1, 0 To numVertices - 1) As Integer For i As Integer = 0 To numVertices - 1 For j As Integer = 0 To numVertices - 1 If i <> j Then nxt(i, j) = j + 1 Next j Next i
For k As Integer = 0 To numVertices - 1 For i As Integer = 0 To numVertices - 1 For j As Integer = 0 To numVertices - 1 If (dist(i, k) + dist(k, j)) < dist(i, j) Then dist(i, j) = dist(i, k) + dist(k, j) nxt(i, j) = nxt(i, k) End If Next j Next i Next k
printResult(dist(), nxt())
End Sub
Dim weights(4, 2) As Integer = {{1, 3, -2}, {2, 1, 4}, {2, 3, 3}, {3, 4, 2}, {4, 2, -1}} Dim numVertices As Integer = 4 floydWarshall(weights(), numVertices) Print Print "Press any key to quit" Sleep</lang>
- Output:
pair dist path 1 -> 2 -1 1 -> 3 -> 4 -> 2 1 -> 3 -2 1 -> 3 1 -> 4 0 1 -> 3 -> 4 2 -> 1 4 2 -> 1 2 -> 3 2 2 -> 1 -> 3 2 -> 4 4 2 -> 1 -> 3 -> 4 3 -> 1 5 3 -> 4 -> 2 -> 1 3 -> 2 1 3 -> 4 -> 2 3 -> 4 2 3 -> 4 4 -> 1 3 4 -> 2 -> 1 4 -> 2 -1 4 -> 2 4 -> 3 1 4 -> 2 -> 1 -> 3
Go
<lang go>package main
import (
"fmt" "math"
)
type arc struct {
to int wt float64
}
func fw(g [][]arc) [][]float64 {
dist := make([][]float64, len(g)) for i := range dist { di := make([]float64, len(g)) for j := range di { di[j] = math.Inf(1) } di[i] = 0 dist[i] = di } for u, arcs := range g { for _, v := range arcs { dist[u][v.to] = v.wt } } for k, dk := range dist { for _, di := range dist { for j, dij := range di { if d := di[k] + dk[j]; dij > d { di[j] = d } } } } return dist
}
func main() {
g := [][]arc{ 1: Template:3, -2, 2: {{1, 4}, {3, 3}}, 3: Template:4, 2, 4: Template:2, -1, } dist := fw(g) for _, d := range dist { fmt.Printf("%4g\n", d) }
}</lang>
- Output:
[ 0 +Inf +Inf +Inf +Inf] [+Inf 0 -1 -2 0] [+Inf 4 0 2 4] [+Inf 5 1 0 2] [+Inf 3 -1 1 0]
Haskell
Necessary imports <lang haskell>import Control.Monad (join) import Data.List (union) import Data.Map hiding (foldr, union) import Data.Maybe (fromJust, isJust) import Data.Semigroup import Prelude hiding (lookup, filter)</lang>
First we define a general datatype to represent the shortest path. Type a
represents a distance. It could be a number, in case of weighted graph or boolean value for just a directed graph. Type b
goes for vertice labels (integers, chars, strings...)
<lang haskell>data Shortest b a = Shortest { distance :: a, path :: [b] }
deriving Show</lang>
Next we note that shortest paths form a semigroup with following "addition" rule:
<lang haskell>instance (Ord a, Eq b) => Semigroup (Shortest b a) where
a <> b = case distance a `compare` distance b of GT -> b LT -> a EQ -> a { path = path a `union` path b }</lang>
It finds minimal path by distance
, and in case of equal distances joins both paths. We will lift this semigroup to monoid using Maybe
wrapper.
Graph is represented as a Map
, containing pairs of vertices and corresponding weigts. The distance table is a Map
, containing pairs of joint vertices and corresponding shortest paths.
Now we are ready to define the main part of the Floyd-Warshall algorithm, which processes properly prepared distance table dist
for given list of vertices v
:
<lang haskell>floydWarshall v dist = foldr innerCycle (Just <$> dist) v
where innerCycle k dist = (newDist <$> v <*> v) `setTo` dist where newDist i j = ((i,j), do a <- join $ lookup (i, k) dist b <- join $ lookup (k, j) dist return $ Shortest (distance a <> distance b) (path a))
setTo = unionWith (<>) . fromList</lang>
The floydWarshall
produces only first steps of shortest paths. Whole paths are build by following function:
<lang haskell>buildPaths d = mapWithKey (\pair s -> s { path = buildPath pair}) d
where buildPath (i,j) | i == j = j | otherwise = do k <- path $ fromJust $ lookup (i,j) d p <- buildPath (k,j) [i : p]</lang>
All pre- and postprocessing is done by the main function findMinDistances
:
<lang haskell>findMinDistances v g =
let weights = mapWithKey (\(_,j) w -> Shortest w [j]) g trivial = fromList [ ((i,i), Shortest mempty []) | i <- v ] clean d = fromJust <$> filter isJust (d \\ trivial) in buildPaths $ clean $ floydWarshall v (weights <> trivial)</lang>
Examples:
The sample graph: <lang haskell>g = fromList [((2,1), 4)
,((2,3), 3) ,((1,3), -2) ,((3,4), 2) ,((4,2), -1)]</lang>
the helper function <lang haskell>showShortestPaths v g = mapM_ print $ toList $ findMinDistances v g</lang>
- Output:
Weights as distances:
λ> showShortestPaths [1..4] (Sum <$> g) ((1,2),Shortest {distance = Sum {getSum = -1}, path = [[1,3,4,2]]}) ((1,3),Shortest {distance = Sum {getSum = -2}, path = [[1,3]]}) ((1,4),Shortest {distance = Sum {getSum = 0}, path = [[1,3,4]]}) ((2,1),Shortest {distance = Sum {getSum = 4}, path = [[2,1]]}) ((2,3),Shortest {distance = Sum {getSum = 2}, path = [[2,1,3]]}) ((2,4),Shortest {distance = Sum {getSum = 4}, path = [[2,1,3,4]]}) ((3,1),Shortest {distance = Sum {getSum = 5}, path = [[3,4,2,1]]}) ((3,2),Shortest {distance = Sum {getSum = 1}, path = [[3,4,2]]}) ((3,4),Shortest {distance = Sum {getSum = 2}, path = [[3,4]]}) ((4,1),Shortest {distance = Sum {getSum = 3}, path = [[4,2,1]]}) ((4,2),Shortest {distance = Sum {getSum = -1}, path = [[4,2]]}) ((4,3),Shortest {distance = Sum {getSum = 1}, path = [[4,2,1,3]]})
Unweighted directed graph
λ> showShortestPaths [1..4] (Any . (/= 0) <$> g) ((1,2),Shortest {distance = Any {getAny = True}, path = [[1,3,4,2]]}) ((1,3),Shortest {distance = Any {getAny = True}, path = [[1,3]]}) ((1,4),Shortest {distance = Any {getAny = True}, path = [[1,3,4]]}) ((2,1),Shortest {distance = Any {getAny = True}, path = [[2,1]]}) ((2,3),Shortest {distance = Any {getAny = True}, path = [[2,1,3],[2,3]]}) ((2,4),Shortest {distance = Any {getAny = True}, path = [[2,1,3,4],[2,3,4]]}) ((3,1),Shortest {distance = Any {getAny = True}, path = [[3,4,2,1]]}) ((3,2),Shortest {distance = Any {getAny = True}, path = [[3,4,2]]}) ((3,4),Shortest {distance = Any {getAny = True}, path = [[3,4]]}) ((4,1),Shortest {distance = Any {getAny = True}, path = [[4,2,1]]}) ((4,2),Shortest {distance = Any {getAny = True}, path = [[4,2]]}) ((4,3),Shortest {distance = Any {getAny = True}, path = [[4,2,1,3],[4,2,3]]})
For some pairs several possible paths are found.
Uniformly weighted graph:
λ> showShortestPaths [1..4] (const (Sum 1) <$> g) ((1,2),Shortest {distance = Sum {getSum = 3}, path = [[1,3,4,2]]}) ((1,3),Shortest {distance = Sum {getSum = 1}, path = [[1,3]]}) ((1,4),Shortest {distance = Sum {getSum = 2}, path = [[1,3,4]]}) ((2,1),Shortest {distance = Sum {getSum = 1}, path = [[2,1]]}) ((2,3),Shortest {distance = Sum {getSum = 1}, path = [[2,3]]}) ((2,4),Shortest {distance = Sum {getSum = 2}, path = [[2,3,4]]}) ((3,1),Shortest {distance = Sum {getSum = 3}, path = [[3,4,2,1]]}) ((3,2),Shortest {distance = Sum {getSum = 2}, path = [[3,4,2]]}) ((3,4),Shortest {distance = Sum {getSum = 1}, path = [[3,4]]}) ((4,1),Shortest {distance = Sum {getSum = 2}, path = [[4,2,1]]}) ((4,2),Shortest {distance = Sum {getSum = 1}, path = [[4,2]]}) ((4,3),Shortest {distance = Sum {getSum = 2}, path = [[4,2,3]]})
Graph labeled by chars:
<lang haskell>g2 = fromList [(('A','S'), 1)
,(('A','D'), -1) ,(('S','E'), 2) ,(('D','E'), 4)]</lang>
λ> showShortestPaths "ASDE" (Sum <$> g2) (('A','D'),Shortest {distance = Sum {getSum = -1}, path = ["AD"]}) (('A','E'),Shortest {distance = Sum {getSum = 3}, path = ["ASE","ADE"]}) (('A','S'),Shortest {distance = Sum {getSum = 1}, path = ["AS"]}) (('D','E'),Shortest {distance = Sum {getSum = 4}, path = ["DE"]}) (('S','E'),Shortest {distance = Sum {getSum = 2}, path = ["SE"]})
J
<lang J>floyd=: verb define
for_j. i.#y do. y=. y <. j ({"1 +/ {) y end.
)</lang>
Example use:
<lang J>graph=: ".;._2]0 :0
0 _ _2 _ NB. 1->3 costs _2 4 0 3 _ NB. 2->1 costs 4; 2->3 costs 3 _ _ 0 2 NB. 3->4 costs 2 _ _1 _ 0 NB. 4->2 costs _1
)
floyd graph
0 _1 _2 0 4 0 2 4 5 1 0 2 3 _1 1 0</lang>
The graph matrix holds the costs of each directed node. Row index corresponds to starting node. Column index corresponds to ending node. Unconnected nodes have infinite cost.
This approach turns out to be faster than the more concise <./ .+~^:_ for many relatively small graphs (though floyd
happens to be slightly slower for the task example).
Path Reconstruction
This draft task currently asks for path reconstruction, which is a different (related) algorithm:
<lang J>floydrecon=: verb define
n=. ((|i.@,~)#y)*1>.y->./(,y)-._ for_j. i.#y do. d=. y <. j ({"1 +/ {) y b=. y~:d y=. d n=. (n*-.b)+b * j{"1 n end.
)
task=: verb define
dist=. floyd y next=. floydrecon y echo 'pair dist path' for_i. i.#y do. for_k. i.#y do. ndx=. <i,k if. (i~:k)*_>ndx{next do. txt=. (":1+i),'->',(":1+k) txt=. txt,_5{.":ndx{dist txt=. txt,' ',":1+i j=. i while. j~:k do. assert. j~:(<j,k){next j=. (<j,k){next txt=. txt,'->',":1+j end. echo txt end. end. end. i.0 0
)</lang>
Draft output:
<lang J> task graph pair dist path 1->2 _1 1->3->4->2 1->3 _2 1->3 1->4 0 1->3->4 2->1 4 2->1 2->3 2 2->1->3 2->4 4 2->1->3->4 3->1 5 3->4->2->1 3->2 1 3->4->2 3->4 2 3->4 4->1 3 4->2->1 4->2 _1 4->2 4->3 1 4->2->1->3</lang>
Java
<lang java>import static java.lang.String.format; import java.util.Arrays;
public class FloydWarshall {
public static void main(String[] args) { int[][] weights = {{1, 3, -2}, {2, 1, 4}, {2, 3, 3}, {3, 4, 2}, {4, 2, -1}}; int numVertices = 4;
floydWarshall(weights, numVertices); }
static void floydWarshall(int[][] weights, int numVertices) {
double[][] dist = new double[numVertices][numVertices]; for (double[] row : dist) Arrays.fill(row, Double.POSITIVE_INFINITY);
for (int[] w : weights) dist[w[0] - 1][w[1] - 1] = w[2];
int[][] next = new int[numVertices][numVertices]; for (int i = 0; i < next.length; i++) { for (int j = 0; j < next.length; j++) if (i != j) next[i][j] = j + 1; }
for (int k = 0; k < numVertices; k++) for (int i = 0; i < numVertices; i++) for (int j = 0; j < numVertices; j++) if (dist[i][k] + dist[k][j] < dist[i][j]) { dist[i][j] = dist[i][k] + dist[k][j]; next[i][j] = next[i][k]; }
printResult(dist, next); }
static void printResult(double[][] dist, int[][] next) { System.out.println("pair dist path"); for (int i = 0; i < next.length; i++) { for (int j = 0; j < next.length; j++) { if (i != j) { int u = i + 1; int v = j + 1; String path = format("%d -> %d %2d %s", u, v, (int) dist[i][j], u); do { u = next[u - 1][v - 1]; path += " -> " + u; } while (u != v); System.out.println(path); } } } }
}</lang>
pair dist path 1 -> 2 -1 1 -> 3 -> 4 -> 2 1 -> 3 -2 1 -> 3 1 -> 4 0 1 -> 3 -> 4 2 -> 1 4 2 -> 1 2 -> 3 2 2 -> 1 -> 3 2 -> 4 4 2 -> 1 -> 3 -> 4 3 -> 1 5 3 -> 4 -> 2 -> 1 3 -> 2 1 3 -> 4 -> 2 3 -> 4 2 3 -> 4 4 -> 1 3 4 -> 2 -> 1 4 -> 2 -1 4 -> 2 4 -> 3 1 4 -> 2 -> 1 -> 3
JavaScript
<lang javascript>var graph = []; for (i = 0; i < 10; ++i) {
graph.push([]); for (j = 0; j < 10; ++j) graph[i].push(i == j ? 0 : 9999999);
}
for (i = 1; i < 10; ++i) {
graph[0][i] = graph[i][0] = parseInt(Math.random() * 9 + 1);
}
for (k = 0; k < 10; ++k) {
for (i = 0; i < 10; ++i) { for (j = 0; j < 10; ++j) { if (graph[i][j] > graph[i][k] + graph[k][j]) graph[i][j] = graph[i][k] + graph[k][j] } }
}
console.log(graph);</lang>
Kotlin
<lang scala>// version 1.1
object FloydWarshall {
fun doCalcs(weights: Array<IntArray>, nVertices: Int) { val dist = Array(nVertices) { DoubleArray(nVertices) { Double.POSITIVE_INFINITY } } for (w in weights) dist[w[0] - 1][w[1] - 1] = w[2].toDouble() val next = Array(nVertices) { IntArray(nVertices) } for (i in 0 until next.size) { for (j in 0 until next.size) { if (i != j) next[i][j] = j + 1 } } for (k in 0 until nVertices) { for (i in 0 until nVertices) { for (j in 0 until nVertices) { if (dist[i][k] + dist[k][j] < dist[i][j]) { dist[i][j] = dist[i][k] + dist[k][j] next[i][j] = next[i][k] } } } } printResult(dist, next) }
private fun printResult(dist: Array<DoubleArray>, next: Array<IntArray>) { var u: Int var v: Int var path: String println("pair dist path") for (i in 0 until next.size) { for (j in 0 until next.size) { if (i != j) { u = i + 1 v = j + 1 path = ("%d -> %d %2d %s").format(u, v, dist[i][j].toInt(), u) do { u = next[u - 1][v - 1] path += " -> " + u } while (u != v) println(path) } } } }
}
fun main(args: Array<String>) {
val weights = arrayOf( intArrayOf(1, 3, -2), intArrayOf(2, 1, 4), intArrayOf(2, 3, 3), intArrayOf(3, 4, 2), intArrayOf(4, 2, -1) ) val nVertices = 4 FloydWarshall.doCalcs(weights, nVertices)
}</lang>
- Output:
pair dist path 1 -> 2 -1 1 -> 3 -> 4 -> 2 1 -> 3 -2 1 -> 3 1 -> 4 0 1 -> 3 -> 4 2 -> 1 4 2 -> 1 2 -> 3 2 2 -> 1 -> 3 2 -> 4 4 2 -> 1 -> 3 -> 4 3 -> 1 5 3 -> 4 -> 2 -> 1 3 -> 2 1 3 -> 4 -> 2 3 -> 4 2 3 -> 4 4 -> 1 3 4 -> 2 -> 1 4 -> 2 -1 4 -> 2 4 -> 3 1 4 -> 2 -> 1 -> 3
Perl 6
<lang perl6>sub Floyd-Warshall (Int $n, @edge) {
my @dist = [0, |(Inf xx $n-1)], *.Array.rotate(-1) … !*[*-1]; my @next = [0 xx $n] xx $n;
for @edge -> ($u, $v, $w) { @dist[$u-1;$v-1] = $w; @next[$u-1;$v-1] = $v-1; }
for [X] ^$n xx 3 -> ($k, $i, $j) { if @dist[$i;$j] > my $sum = @dist[$i;$k] + @dist[$k;$j] { @dist[$i;$j] = $sum; @next[$i;$j] = @next[$i;$k]; } }
say ' Pair Distance Path'; for [X] ^$n xx 2 -> ($i, $j){ next if $i == $j; my @path = $i; @path.push: @next[@path[*-1];$j] until @path[*-1] == $j; printf("%d → %d %4d %s\n", $i+1, $j+1, @dist[$i;$j], @path.map( *+1 ).join(' → ')); }
}
Floyd-Warshall(4, [[1, 3, -2], [2, 1, 4], [2, 3, 3], [3, 4, 2], [4, 2, -1]]);</lang>
- Output:
Pair Distance Path 1 → 2 -1 1 → 3 → 4 → 2 1 → 3 -2 1 → 3 1 → 4 0 1 → 3 → 4 2 → 1 4 2 → 1 2 → 3 2 2 → 1 → 3 2 → 4 4 2 → 1 → 3 → 4 3 → 1 5 3 → 4 → 2 → 1 3 → 2 1 3 → 4 → 2 3 → 4 2 3 → 4 4 → 1 3 4 → 2 → 1 4 → 2 -1 4 → 2 4 → 3 1 4 → 2 → 1 → 3
Phix
Direct translation of the wikipedia pseudocode <lang Phix>constant inf = 1e300*1e300
function Path(integer u, integer v, sequence next)
if next[u,v]=null then return "" end if sequence path = {sprintf("%d",u)} while u!=v do u = next[u,v] path = append(path,sprintf("%d",u)) end while return join(path,"->")
end function
procedure FloydWarshall(integer V, sequence weights)
sequence dist = repeat(repeat(inf,V),V) sequence next = repeat(repeat(null,V),V) for k=1 to length(weights) do integer {u,v,w} = weights[k] dist[u,v] := w -- the weight of the edge (u,v) next[u,v] := v end for -- standard Floyd-Warshall implementation for k=1 to V do for i=1 to V do for j=1 to V do atom d = dist[i,k] + dist[k,j] if dist[i,j] > d then dist[i,j] := d next[i,j] := next[i,k] end if end for end for end for printf(1,"pair dist path\n") for u=1 to V do for v=1 to V do if u!=v then printf(1,"%d->%d %2d %s\n",{u,v,dist[u,v],Path(u,v,next)}) end if end for end for
end procedure
constant V = 4 constant weights = {{1, 3, -2}, {2, 1, 4}, {2, 3, 3}, {3, 4, 2}, {4, 2, -1}} FloydWarshall(V,weights)</lang>
- Output:
pair dist path 1->2 -1 1->3->4->2 1->3 -2 1->3 1->4 0 1->3->4 2->1 4 2->1 2->3 2 2->1->3 2->4 4 2->1->3->4 3->1 5 3->4->2->1 3->2 1 3->4->2 3->4 2 3->4 4->1 3 4->2->1 4->2 -1 4->2 4->3 1 4->2->1->3
PHP
<lang php><?php $graph = array(); for ($i = 0; $i < 10; ++$i) {
$graph[] = array(); for ($j = 0; $j < 10; ++$j) $graph[$i][] = $i == $j ? 0 : 9999999;
}
for ($i = 1; $i < 10; ++$i) {
$graph[0][$i] = $graph[$i][0] = rand(1, 9);
}
for ($k = 0; $k < 10; ++$k) {
for ($i = 0; $i < 10; ++$i) { for ($j = 0; $j < 10; ++$j) { if ($graph[$i][$j] > $graph[$i][$k] + $graph[$k][$j]) $graph[$i][$j] = $graph[$i][$k] + $graph[$k][$j]; } }
}
print_r($graph); ?></lang>
Racket
<lang racket>#lang typed/racket (require math/array)
- in
- initialized dist and next matrices
- out
- dist and next matrices
- O(n^3)
(define-type Next-T (Option Index)) (define-type Dist-T Real) (define-type Dists (Array Dist-T)) (define-type Nexts (Array Next-T)) (define-type Settable-Dists (Settable-Array Dist-T)) (define-type Settable-Nexts (Settable-Array Next-T))
(: floyd-with-path (-> Index Dists Nexts (Values Dists Nexts))) (: init-edges (-> Index (Values Settable-Dists Settable-Nexts)))
(define (floyd-with-path n dist-in next-in)
(define dist : Settable-Dists (array->mutable-array dist-in)) (define next : Settable-Nexts (array->mutable-array next-in)) (for* ((k n) (i n) (j n)) (when (negative? (array-ref dist (vector j j))) (raise 'negative-cycle)) (define i.k (vector i k)) (define i.j (vector i j)) (define d (+ (array-ref dist i.k) (array-ref dist (vector k j)))) (when (< d (array-ref dist i.j)) (array-set! dist i.j d) (array-set! next i.j (array-ref next i.k)))) (values dist next))
- utilities
- init random edges costs, matrix 66% filled
(define (init-edges n)
(define dist : Settable-Dists (array->mutable-array (make-array (vector n n) 0))) (define next : Settable-Nexts (array->mutable-array (make-array (vector n n) #f))) (for* ((i n) (j n) #:unless (= i j)) (define i.j (vector i j)) (array-set! dist i.j +Inf.0) (unless (< (random) 0.3) (array-set! dist i.j (add1 (random 100))) (array-set! next i.j j))) (values dist next))
- show path from u to v
(: path (-> Nexts Index Index (Listof Index))) (define (path next u v)
(let loop : (Listof Index) ((u : Index u) (rv : (Listof Index) null)) (if (= u v) (reverse (cons u rv)) (let ((nxt (array-ref next (vector u v)))) (if nxt (loop nxt (cons u rv)) null)))))
- show computed distance
(: mdist (-> Dists Index Index Dist-T)) (define (mdist dist u v)
(array-ref dist (vector u v)))
(module+ main
(define n 8) (define-values (dist next) (init-edges n)) (define-values (dist+ next+) (floyd-with-path n dist next)) (displayln "original dist") dist (displayln "new dist and next") dist+ next+ ;; note, these path and dist calls are not as carefully crafted as ;; the echolisp ones (in fact they're verbatim copied) (displayln "paths and distances") (path next+ 1 3) (mdist dist+ 1 0) (mdist dist+ 0 3) (mdist dist+ 1 3) (path next+ 7 6) (path next+ 6 7))</lang>
- Output:
original dist (mutable-array #[#[0 51 +inf.0 11 44 13 +inf.0 86] #[48 0 70 +inf.0 65 78 77 54] #[29 +inf.0 0 +inf.0 78 14 +inf.0 24] #[40 79 52 0 +inf.0 99 37 88] #[71 62 +inf.0 7 0 +inf.0 +inf.0 +inf.0] #[89 65 83 +inf.0 91 0 41 70] #[69 34 +inf.0 49 +inf.0 89 0 20] #[2 56 +inf.0 60 +inf.0 75 +inf.0 0]]) new dist and next (mutable-array #[#[0 51 63 11 44 13 48 68] #[48 0 70 59 65 61 77 54] #[26 77 0 37 70 14 55 24] #[40 71 52 0 84 53 37 57] #[47 62 59 7 0 60 44 64] #[63 65 83 74 91 0 41 61] #[22 34 85 33 66 35 0 20] #[2 53 65 13 46 15 50 0]]) (mutable-array #[#[#f 1 3 3 4 5 3 3] #[0 #f 2 0 4 0 6 7] #[7 7 #f 7 7 5 5 7] #[0 6 2 #f 0 0 6 6] #[3 1 3 3 #f 3 3 3] #[6 1 2 6 4 #f 6 6] #[7 1 7 7 7 7 #f 7] #[0 0 0 0 0 0 0 #f]]) paths and distances '(1 0 3) 48 11 59 '(7 0 3 6) '(6 7)
REXX
<lang rexx>/*REXX program uses Floyd-Warshall algorithm to find shortest distance between vertices.*/ v=4 /*███ {1} ███*/ /*number of vertices in weighted graph.*/ @.= 99999999 /*███ 4 / \ -2 ███*/ /*the default distance (edge weight). */ @.1.3=-2 /*███ / 3 \ ███*/ /*the distance (weight) for an edge. */ @.2.1= 4 /*███ {2} ────► {3} ███*/ /* " " " " " " */ @.2.3= 3 /*███ \ / ███*/ /* " " " " " " */ @.3.4= 2 /*███ -1 \ / 2 ███*/ /* " " " " " " */ @.4.2=-1 /*███ {4} ███*/ /* " " " " " " */
do k=1 for v do i=1 for v do j=1 for v; _=@.i.k + @.k.j if @.i.j>_ then @.i.j=_ /*use a new distance (weight) for edge.*/ end /*j*/ end /*i*/ end /*k*/
w=12 /*width of the columns for the output. */ say center('vertices', w) center('distance', w) /*display the 1st line of the title. */ say center('pair' , w) center('(weight)', w) /* " " 2nd " " " " */ say copies('═' , w) copies('═' , w) /* " " 3rd " " " " */
/* [↓] display edge distances (weight)*/ do f=1 for v /*process each of the "from" vertices. */ do t=1 for v; if f==t then iterate /* " " " " "to" " */ say center(f '─►' t, w) right(@.f.t, w%2) /*show the distance between 2 vertices.*/ end /*t*/ end /*f*/ /*stick a fork in it, we're all done. */</lang>
output when using the defaults:
vertices distance pair (weight) ════════════ ════════════ 1 ─► 2 -1 1 ─► 3 -2 1 ─► 4 0 2 ─► 1 4 2 ─► 3 2 2 ─► 4 4 3 ─► 1 5 3 ─► 2 1 3 ─► 4 2 4 ─► 1 3 4 ─► 2 -1 4 ─► 3 1
Ruby
<lang ruby>def floyd_warshall(n, edge)
dist = Array.new(n){|i| Array.new(n){|j| i==j ? 0 : Float::INFINITY}} nxt = Array.new(n){Array.new(n)} edge.each do |u,v,w| dist[u-1][v-1] = w nxt[u-1][v-1] = v-1 end n.times do |k| n.times do |i| n.times do |j| if dist[i][j] > dist[i][k] + dist[k][j] dist[i][j] = dist[i][k] + dist[k][j] nxt[i][j] = nxt[i][k] end end end end puts "pair dist path" n.times do |i| n.times do |j| next if i==j u = i path = [u] path << (u = nxt[u][j]) while u != j path = path.map{|u| u+1}.join(" -> ") puts "%d -> %d %4d %s" % [i+1, j+1, dist[i][j], path] end end
end
n = 4 edge = [[1, 3, -2], [2, 1, 4], [2, 3, 3], [3, 4, 2], [4, 2, -1]] floyd_warshall(n, edge)</lang>
- Output:
pair dist path 1 -> 2 -1 1 -> 3 -> 4 -> 2 1 -> 3 -2 1 -> 3 1 -> 4 0 1 -> 3 -> 4 2 -> 1 4 2 -> 1 2 -> 3 2 2 -> 1 -> 3 2 -> 4 4 2 -> 1 -> 3 -> 4 3 -> 1 5 3 -> 4 -> 2 -> 1 3 -> 2 1 3 -> 4 -> 2 3 -> 4 2 3 -> 4 4 -> 1 3 4 -> 2 -> 1 4 -> 2 -1 4 -> 2 4 -> 3 1 4 -> 2 -> 1 -> 3
SequenceL
<lang sequencel>import <Utilities/Sequence.sl>; import <Utilities/Math.sl>;
ARC ::= (To: int, Weight: float); arc(t,w) := (To: t, Weight: w); VERTEX ::= (Label: int, Arcs: ARC(1)); vertex(l,arcs(1)) := (Label: l, Arcs: arcs);
getArcsFrom(vertex, graph(1)) :=
let index := firstIndexOf(graph.Label, vertex); in [] when index = 0 else graph[index].Arcs;
getWeightTo(vertex, arcs(1)) :=
let index := firstIndexOf(arcs.To, vertex); in 0 when index = 0 else arcs[index].Weight;
throughK(k, dist(2)) :=
let newDist[i, j] := min(dist[i][k] + dist[k][j], dist[i][j]); in dist when k > size(dist) else throughK(k + 1, newDist);
floydWarshall(graph(1)) :=
let initialResult[i,j] := 1.79769e308 when i /= j else 0 foreach i within 1 ... size(graph), j within 1 ... size(graph); singleResult[i,j] := getWeightTo(j, getArcsFrom(i, graph)) foreach i within 1 ... size(graph), j within 1 ... size(graph); start[i,j] := initialResult[i,j] when singleResult[i,j] = 0 else singleResult[i,j]; in throughK(1, start);
main() :=
let graph := [vertex(1, [arc(3,-2)]), vertex(2, [arc(1,4), arc(3,3)]), vertex(3, [arc(4,2)]), vertex(4, [arc(2,-1)])]; in floydWarshall(graph);</lang>
- Output:
[[0,-1,-2,0],[4,0,2,4],[5,1,0,2],[3,-1,1,0]]
Sidef
<lang ruby>func floyd_warshall(n, edge) {
var dist = n.of {|i| n.of { |j| i == j ? 0 : Inf }} var nxt = n.of { n.of(nil) } for u,v,w in edge { dist[u-1][v-1] = w nxt[u-1][v-1] = v-1 }
[^n] * 3 -> cartesian { |k, i, j| if (dist[i][j] > dist[i][k]+dist[k][j]) { dist[i][j] = dist[i][k]+dist[k][j] nxt[i][j] = nxt[i][k] } }
var summary = "pair dist path\n" for i,j (^n ~X ^n) { i==j && next var u = i var path = [u] while (u != j) { path << (u = nxt[u][j]) } path.map!{|u| u+1 }.join!(" -> ") summary += ("%d -> %d %4d %s\n" % (i+1, j+1, dist[i][j], path)) }
return summary
}
var n = 4 var edge = [[1, 3, -2], [2, 1, 4], [2, 3, 3], [3, 4, 2], [4, 2, -1]] print floyd_warshall(n, edge)</lang>
- Output:
pair dist path 1 -> 2 -1 1 -> 3 -> 4 -> 2 1 -> 3 -2 1 -> 3 1 -> 4 0 1 -> 3 -> 4 2 -> 1 4 2 -> 1 2 -> 3 2 2 -> 1 -> 3 2 -> 4 4 2 -> 1 -> 3 -> 4 3 -> 1 5 3 -> 4 -> 2 -> 1 3 -> 2 1 3 -> 4 -> 2 3 -> 4 2 3 -> 4 4 -> 1 3 4 -> 2 -> 1 4 -> 2 -1 4 -> 2 4 -> 3 1 4 -> 2 -> 1 -> 3
Tcl
The implementation of Floyd-Warshall in tcllib is quite readable; this example merely initialises a graph from an adjacency list then calls the tcllib code:
<lang Tcl>package require Tcl 8.5 ;# for {*} and [dict] package require struct::graph package require struct::graph::op
struct::graph g
set arclist {
a b a p b m b c c d d e e f f q f g
}
g node insert {*}$arclist
foreach {from to} $arclist {
set a [g arc insert $from $to] g arc setweight $a 1.0
}
set paths [::struct::graph::op::FloydWarshall g]
set paths [dict filter $paths key {a *}] ;# filter for paths starting at "a" set paths [dict filter $paths value {[0-9]*}] ;# whose cost is not "Inf" set paths [lsort -stride 2 -index 1 -real -decreasing $paths] ;# and print the longest first puts $paths</lang>
- Output:
{a q} 6.0 {a g} 6.0 {a f} 5.0 {a e} 4.0 {a d} 3.0 {a m} 2.0 {a c} 2.0 {a p} 1.0 {a b} 1.0 {a a} 0
zkl
<lang zkl>fcn FloydWarshallWithPathReconstruction(dist){ // dist is munged
V:=dist[0].len(); next:=V.pump(List,V.pump(List,Void.copy).copy); // VxV matrix of Void foreach u,v in (V,V){ if(dist[u][v]!=Void and u!=v) next[u][v] = v } foreach k,i,j in (V,V,V){ a,b,c:=dist[i][j],dist[i][k],dist[k][j]; if( (a!=Void and b!=Void and c!=Void and a>b+c) or // Inf math
(a==Void and b!=Void and c!=Void) ){ dist[i][j] = b+c; next[i][j] = next[i][k];
} } return(dist,next)
} fcn path(next,u,v){
if(Void==next[u][v]) return(T); path:=List(u); while(u!=v){ path.append(u = next[u][v]) } path
} fcn printM(m){ m.pump(Console.println,rowFmt) } fcn rowFmt(row){ ("%5s "*row.len()).fmt(row.xplode()) }</lang> <lang zkl>const V=4; dist:=V.pump(List,V.pump(List,Void.copy).copy); // VxV matrix of Void foreach i in (V){ dist[i][i] = 0 } // zero vertexes
/* Graph from the Wikipedia:
1 2 3 4 d ----------
1| 0 X -2 X 2| 4 0 3 X 3| X X 0 2 4| X -1 X 0
- /
dist[0][2]=-2; dist[1][0]=4; dist[1][2]=3; dist[2][3]=2; dist[3][1]=-1;
dist,next:=FloydWarshallWithPathReconstruction(dist); println("Shortest distance array:"); printM(dist); println("\nPath array:"); printM(next); println("\nAll paths:"); foreach u,v in (V,V){
if(p:=path(next,u,v)) p.println();
}</lang>
- Output:
Shortest distance array: 0 -1 -2 0 4 0 2 4 5 1 0 2 3 -1 1 0 Path array: Void 2 2 2 0 Void 0 0 3 3 Void 3 1 1 1 Void All paths: L(0,2,3,1) L(0,2) L(0,2,3) L(1,0) L(1,0,2) L(1,0,2,3) L(2,3,1,0) L(2,3,1) L(2,3) L(3,1,0) L(3,1) L(3,1,0,2)