63 lines
1.7 KiB
Plaintext
63 lines
1.7 KiB
Plaintext
' 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
|