Floyd-Warshall algorithm: Difference between revisions

{{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>

=={{header|FreeBASIC}}==

{{trans|Java}}

<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>