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