Const Infinity = 1E+308
Private m_Edges As Edges
'Need an NxN of the vertices not just the real edges
'------------ Procedures ----------------------------------------------
Public Sub InitializeFloyd_Marshall(TheEdges As Edges)
Dim I As Long
Dim j As Long
Dim startKeys() As Variant
Dim endKeys() As Variant
Set Me.Edges = TheEdges
startKeys = Me.Edges.startKeys
For I = 0 To UBound(startKeys)
endKeys = Me.Edges.endKeys(CStr(startKeys(I)))
For j = 0 To UBound(endKeys)
Me.Edges.Item(CStr(startKeys(I)), CStr(endKeys(j))).ShortestPathDistance = Me.Edges.Item(CStr(startKeys(I)), CStr(endKeys(j))).EdgeDistance
Next j
Next I
Me.Edges.Item(CStr(startKeys(0)), CStr(endKeys(0))).ShortestPathDistance = 0
End Sub
Public Property Get Edges() As Edges
Set Edges = m_Edges
End Property
Public Property Set Edges(ByVal TheEdges As Edges)
Set m_Edges = TheEdges
End Property
Public Sub SolveAllPaths()
Dim colOut As Collection
Dim Neighbors() As Variant
Dim SpanningVertex As Vertex
Dim VisitedVertex As Vertex
Dim TempVertex As Vertex
Dim I_Key As String
Dim J_Key As String
Dim K_key As String
Dim I As Integer
Dim j As Integer
Dim k As Integer
Dim The_keys() As Variant
Dim distance_i_j As Double
Dim distance_i_k As Double
Dim distance_k_j As Double
Dim newDistance As Double
Dim n As Long
n = Me.Edges.count
The_keys = Me.Edges.startKeys
For k = 0 To n - 1
K_key = The_keys(k)
For I = 0 To n - 1
I_Key = The_keys(I)
For j = 0 To n - 1
J_Key = The_keys(j)
distance_i_j = Me.Edges.Item(I_Key, J_Key).ShortestPathDistance
distance_i_k = Me.Edges.Item(I_Key, K_key).ShortestPathDistance
distance_k_j = Me.Edges.Item(K_key, J_Key).ShortestPathDistance
If distance_i_k = Infinity Or distance_k_j = Infinity Then
newDistance = Infinity
Else
newDistance = distance_i_k + distance_k_j
End If
If newDistance < distance_i_j Then
'Debug.Print "i,j,k " & I_Key & " " & J_Key & " " & K_key & " dist " & newDistance
Me.Edges.Item(I_Key, J_Key).ShortestPathDistance = newDistance
Me.Edges.Item(I_Key, J_Key).NextVertexKey = K_key
End If
Next j
Next I
Next k
End Sub
Public Function GetPath(startKey As String, endkey As String) As String
Dim Path As String
If startKey = endkey Then
Path = ""
Else
Path = Trim(RecursePath(startKey, endkey))
End If
If Path <> "" Then
Path = " " & Path & " "
Else
Path = " "
End If
If Path = "No path" Then
GetPath = Path
Else
GetPath = "Path: " & startKey & Path & endkey
End If
End Function
Public Function GetShortestPathDistance(startKey As String, endkey As String) As Double
If startKey = endkey Then
GetShortestPathDistance = 0
Else
GetShortestPathDistance = Me.Edges.Item(startKey, endkey).ShortestPathDistance
End If
End Function
Private Function RecursePath(startKey As String, endkey As String) As String
'recursively reconstruct shortest path from i to j using A and Nxt
Dim TmpStartKey As String
If Me.Edges.Exists(startKey, endkey) Then
If Me.Edges.Item(startKey, endkey).ShortestPathDistance = Infinity Then
RecursePath = "No path"
Else
TmpStartKey = Me.Edges.Item(startKey, endkey).NextVertexKey
If TmpStartKey = "" Then 'The path from i to j is shortest and exists
RecursePath = ""
Else
'Debug.Print startKey & " " & TmpStartKey
RecursePath = RecursePath(startKey, TmpStartKey) & " " & TmpStartKey & " " & RecursePath(TmpStartKey, endkey)
RecursePath = Trim(RecursePath)
End If
End If
Else
RecursePath = "No path"
End If
End Function
Public Function GetPathNames(startKey As String, endkey As String) As String
Dim PathNames As String
If startKey = endkey Then
PathNames = ""
Else
PathNames = Trim(RecursePathNames(startKey, endkey))
End If
If PathNames <> "" Then
PathNames = " " & PathNames & " "
Else
PathNames = " "
End If
If PathNames = "No path" Then
GetPathNames = PathNames
Else
GetPathNames = "PathNames: " & Me.Edges.Item(startKey, startKey).StartVertexName & PathNames & Me.Edges.Item(endkey, endkey).EndVertexName
End If
End Function
Private Function RecursePathNames(startKey As String, endkey As String) As String
'recursively reconstruct shortest path from i to j using A and Nxt
Dim TmpStartKey As String
If Me.Edges.Exists(startKey, endkey) Then
If Me.Edges.Item(startKey, endkey).ShortestPathDistance = Infinity Then
RecursePathNames = "No path"
Else
TmpStartKey = Me.Edges.Item(startKey, endkey).NextVertexKey
If TmpStartKey = "" Then 'The path from i to j is shortest and exists
RecursePathNames = ""
Else
'Debug.Print startKey & " " & TmpStartKey
RecursePathNames = RecursePathNames(startKey, TmpStartKey) & " " & Me.Edges.Item(TmpStartKey, TmpStartKey).StartVertexName & " " & RecursePathNames(TmpStartKey, endkey)
RecursePathNames = Trim(RecursePathNames)
End If
End If
Else
RecursePathNames = "No path"
End If
End Function