Anonymous user
User:Klever: Difference between revisions
updated version of Floyd algorithm
mNo edit summary |
(updated version of Floyd algorithm) |
||
Line 19:
The [http://en.wikipedia.org/wiki/Floyd-Warshall_algorithm Floyd algorithm or Floyd-Warshall algorithm] finds the shortest path between all pairs of nodes in a weighted, directed graph. It is an example of dynamic programming.
Usage: fill in the number of nodes (n) and the
Then run "Floyd" or "FloydWithPaths".
Line 26:
FloydWithPaths: this sub prints the lengths and the nodes along the paths
<lang vb>
Option Compare Database
'Floyd globals
Const MaxGraph As Integer = 100 'max. number of vertices in graph
Const Infinity = 1E+308
Dim E(1 To MaxGraph, 1 To MaxGraph) As Double
Dim A(1 To MaxGraph, 1 To MaxGraph) As Double
Dim Nxt(1 To MaxGraph, 1 To MaxGraph) As Integer
Public Sub SolveFloyd(n)
'Floyd's algorithm: all-pairs shortest-paths cost
Line 42 ⟶ 44:
'inputs:
' n : number of vertices (maximum value is maxGraph)
' E(i,j) : cost (length,...) of edge from i to j or
'output:
' A(i,j): minimal cost for path from i to j
'constant:
' Infinity : very large number
For i = 1 To n
For j = 1 To n
If E(i, j) <>
Next j
A(i, i) = 0
Line 62 ⟶ 64:
Next k
End Sub
Public Sub SolveFloydWithPaths(n)
'cf. SolveFloyd, but here we
Line 68 ⟶ 70:
For i = 1 To n
For j = 1 To n
If E(i, j) <>
Next j
A(i, i) = 0
Line 83 ⟶ 85:
Next k
End Sub
Public Function GetPath(i, j) As String
'recursively reconstruct shortest path from i to j using A and Nxt
Line 97 ⟶ 99:
End If
End Function
Public Sub Floyd()
'main function to apply Floyd's algorithm
'see description in wp:en:Floyd-Warshall algorithm
' define problem:
' number of vertices?
Line 108 ⟶ 110:
For i = 1 To n
For j = 1 To n
E(i, j) =
Next j
Next i
Line 119 ⟶ 121:
E(3, 4) = 20
E(3, 5) = 44
E(4, 2) =
E(4, 5) =
'Solve it
SolveFloyd n
'Print solution
'note: for large graphs the output may be too large for the Immediate panel
Line 135 ⟶ 137:
Next i
End Sub
Public Sub FloydWithPaths()
'main function to solve Floyd's algorithm and return shortest path between
'any two vertices
' define problem:
' number of vertices?
Line 146 ⟶ 148:
For i = 1 To n
For j = 1 To n
E(i, j) =
Nxt(i, j) = 0
Next j
Line 158 ⟶ 160:
E(3, 4) = 20
E(3, 5) = 44
E(4, 2) =
E(4, 5) =
'Solve it
SolveFloydWithPaths n
'Print solution
'note: for large graphs the output may be too large for the Immediate panel
Line 174 ⟶ 176:
Next i
End Sub
</lang>
Output:
Line 189 ⟶ 191:
2 5 4
3 1 No path!
3 2
3 4 20
3 5
4 1 No path!
4 2
4 3
4 5
5 1 No path!
5 2 No path!
5 3 No path!
5 4 No path!
FloydWithPaths
Line 213 ⟶ 214:
2 5 4
3 1 --- No path!
3 2
3 4 20
3 5
4 1 --- No path!
4 2
4 3
4 5
5 1 --- No path!
5 2 --- No path!
5 3 --- No path!
5 4 --- No path!
</pre>
| |||