floyd.txt

VB实现Floyd算法

Option Explicit

Private Sub Command1_Click()

Dim a() As Double, bigN As Double, s As String, items As Variant, items1 As Variant
Dim maxNode As Long, i As Long, j As Long

'assume all the data are much smaller than 1E+20
bigN = 1E+20

'following s is the input data for the matrix a(), m will be the above big number
'for bigger problem, the data in matrix a() should be read from a text file
s = "0,3,8,m;2,0,4,7;m,m,0,5;6,m,9,0"

items = Split(s, ";")
maxNode = UBound(items)
ReDim a(maxNode, maxNode)

For i = 0 To maxNode
items1 = Split(items(i), ",")
For j = 0 To maxNode
If items1(j) = "m" Then
a(i, j) = bigN
Else
a(i, j) = items1(j)
End If
Next j
Next i

Print "The adjacency matrix:"
PrintOut a()

Floyd a()

End Sub

Private Sub Floyd(a() As Double)
    'All-Pairs Shortest Paths (Floyd's algorithm), coded by www.dayi.net btef (please let this line remain)
Dim maxNode As Long, b() As String
Dim ii As Long, i As Long, j As Long

maxNode = UBound(a)
ReDim b(maxNode, maxNode)

For i = 0 To maxNode
For j = 0 To maxNode
If a(i, j) < 1E+20 Then
b(i, j) = i & "-" & j
End If
Next j
Next i

'PrintOut b()

For ii = 0 To maxNode
For i = 0 To maxNode
If i <> ii Then
For j = 0 To maxNode
If j <> ii And j <> i Then
If a(i, ii) + a(ii, j) < a(i, j) Then
a(i, j) = a(i, ii) + a(ii, j)
b(i, j) = b(i, ii) & Mid(b(ii, j), InStr(b(ii, j), "-"))
End If
End If
Next j
End If
Next i

'PrintOut a()
'PrintOut b()

Next ii

Print "The Shortest distances:"
PrintOut a()

Print "The Shortest Paths:"
PrintOut b()

End Sub

Private Sub PrintOut(a As Variant)

Dim i As Long, j As Long, maxNode As Long

maxNode = UBound(a)
For i = 0 To maxNode
For j = 0 To maxNode
Print a(i, j),
Next j
Print
Next i
Print String(88, "-")

End Sub