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
 Floyd-Warshall Algorithm - step by step guide (youtube)


' 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