User:Klever: Difference between revisions

Content added Content deleted
mNo edit summary
(updated version of Floyd algorithm)
Line 19: 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.
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 non-zero edge distances or costs in sub Floyd or in sub FloydWithPaths.
Usage: fill in the number of nodes (n) and the edge distances or costs in sub Floyd or in sub FloydWithPaths.
Then run "Floyd" or "FloydWithPaths".
Then run "Floyd" or "FloydWithPaths".


Line 26: Line 26:
FloydWithPaths: this sub prints the lengths and the nodes along the paths
FloydWithPaths: this sub prints the lengths and the nodes along the paths


<lang>
<lang vb>
Option Compare Database

'Floyd globals
'Floyd globals
Const MaxGraph As Integer = 100 'max. number of vertices in graph
Const MaxGraph As Integer = 100 'max. number of vertices in graph
Const Infinity = 1E+308 'very large number
Const Infinity = 1E+308
Dim E(1 To MaxGraph, 1 To MaxGraph) As Double
Dim E(1 To MaxGraph, 1 To MaxGraph) As Double
Dim A(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
Dim Nxt(1 To MaxGraph, 1 To MaxGraph) As Integer

Public Sub SolveFloyd(n)
Public Sub SolveFloyd(n)
'Floyd's algorithm: all-pairs shortest-paths cost
'Floyd's algorithm: all-pairs shortest-paths cost
Line 42: Line 44:
'inputs:
'inputs:
' n : number of vertices (maximum value is maxGraph)
' n : number of vertices (maximum value is maxGraph)
' E(i,j) : cost (length,...) of edge from i to j or <=0 if no edge between i and j
' E(i,j) : cost (length,...) of edge from i to j or "Infinity" if no edge between i and j
'output:
'output:
' A(i,j): minimal cost for path from i to j
' A(i,j): minimal cost for path from i to j
'constant:
'constant:
' Infinity : very large number (guaranteed to be larger than largest possible cost of any path)
' Infinity : very large number
For i = 1 To n
For i = 1 To n
For j = 1 To n
For j = 1 To n
If E(i, j) > 0 Then A(i, j) = E(i, j) Else A(i, j) = Infinity
If E(i, j) <> Infinity Then A(i, j) = E(i, j) Else A(i, j) = Infinity
Next j
Next j
A(i, i) = 0
A(i, i) = 0
Line 62: Line 64:
Next k
Next k
End Sub
End Sub

Public Sub SolveFloydWithPaths(n)
Public Sub SolveFloydWithPaths(n)
'cf. SolveFloyd, but here we
'cf. SolveFloyd, but here we
Line 68: Line 70:
For i = 1 To n
For i = 1 To n
For j = 1 To n
For j = 1 To n
If E(i, j) > 0 Then A(i, j) = E(i, j) Else A(i, j) = Infinity
If E(i, j) <> Infinity Then A(i, j) = E(i, j) Else A(i, j) = Infinity
Next j
Next j
A(i, i) = 0
A(i, i) = 0
Line 83: Line 85:
Next k
Next k
End Sub
End Sub

Public Function GetPath(i, j) As String
Public Function GetPath(i, j) As String
'recursively reconstruct shortest path from i to j using A and Nxt
'recursively reconstruct shortest path from i to j using A and Nxt
Line 97: Line 99:
End If
End If
End Function
End Function

Public Sub Floyd()
Public Sub Floyd()
'main function to apply Floyd's algorithm
'main function to apply Floyd's algorithm
'see description in wp:en:Floyd-Warshall algorithm
'see description in wp:en:Floyd-Warshall algorithm

' define problem:
' define problem:
' number of vertices?
' number of vertices?
Line 108: Line 110:
For i = 1 To n
For i = 1 To n
For j = 1 To n
For j = 1 To n
E(i, j) = 0
E(i, j) = Infinity
Next j
Next j
Next i
Next i
Line 119: Line 121:
E(3, 4) = 20
E(3, 4) = 20
E(3, 5) = 44
E(3, 5) = 44
E(4, 2) = 7
E(4, 2) = 70
E(4, 5) = 13
E(4, 5) = 23

'Solve it
'Solve it
SolveFloyd n
SolveFloyd n

'Print solution
'Print solution
'note: for large graphs the output may be too large for the Immediate panel
'note: for large graphs the output may be too large for the Immediate panel
Line 135: Line 137:
Next i
Next i
End Sub
End Sub

Public Sub FloydWithPaths()
Public Sub FloydWithPaths()
'main function to solve Floyd's algorithm and return shortest path between
'main function to solve Floyd's algorithm and return shortest path between
'any two vertices
'any two vertices

' define problem:
' define problem:
' number of vertices?
' number of vertices?
Line 146: Line 148:
For i = 1 To n
For i = 1 To n
For j = 1 To n
For j = 1 To n
E(i, j) = 0
E(i, j) = Infinity
Nxt(i, j) = 0
Nxt(i, j) = 0
Next j
Next j
Line 158: Line 160:
E(3, 4) = 20
E(3, 4) = 20
E(3, 5) = 44
E(3, 5) = 44
E(4, 2) = 7
E(4, 2) = 70
E(4, 5) = 13
E(4, 5) = 23

'Solve it
'Solve it
SolveFloydWithPaths n
SolveFloydWithPaths n

'Print solution
'Print solution
'note: for large graphs the output may be too large for the Immediate panel
'note: for large graphs the output may be too large for the Immediate panel
Line 174: Line 176:
Next i
Next i
End Sub
End Sub
</lang>
</lang>


Output:
Output:
Line 189: Line 191:
2 5 4
2 5 4
3 1 No path!
3 1 No path!
3 2 27
3 2 90
3 4 20
3 4 20
3 5 31
3 5 43
4 1 No path!
4 1 No path!
4 2 7
4 2 70
4 3 37
4 3 100
4 5 11
4 5 23
5 1 No path!
5 1 No path!
5 2 No path!
5 2 No path!
5 3 No path!
5 3 No path!
5 4 No path!
5 4 No path!



FloydWithPaths
FloydWithPaths
Line 213: Line 214:
2 5 4
2 5 4
3 1 --- No path!
3 1 --- No path!
3 2 27 4
3 2 90 4
3 4 20
3 4 20
3 5 31 4 2
3 5 43 4
4 1 --- No path!
4 1 --- No path!
4 2 7
4 2 70
4 3 37 2
4 3 100 2
4 5 11 2
4 5 23
5 1 --- No path!
5 1 --- No path!
5 2 --- No path!
5 2 --- No path!
5 3 --- No path!
5 3 --- No path!
5 4 --- No path!
5 4 --- No path!

</pre>
</pre>


Retrieved from "https://rosettacode.org/wiki/User:Klever"