Anonymous user
User:Klever: Difference between revisions
m
→KWIC index
m (→KWIC index) |
|||
| (3 intermediate revisions by the same user not shown) | |||
Line 15:
In MS Office program (Word, Excel, Access...): open the Visual Basic window. Paste the code in a module. Execute it by typing a suitable command in the Immediate Window. Output will be directed to the Immediate Window unless stated otherwise...
==[[Dijkstra algorithm]]==
<lang vb>
'Dijkstra globals
Const MaxGraph As Integer = 100 'max. number of nodes in graph
Const Infinity = 1E+308
Dim E(1 To MaxGraph, 1 To MaxGraph) As Double 'the edge costs (Infinity if no edge)
Dim A(1 To MaxGraph) As Double 'the distances calculated
Dim P(1 To MaxGraph) As Integer 'the previous/path array
Dim Q(1 To MaxGraph) As Boolean 'the queue
Public Sub Dijkstra(n, start)
'simple implementation of Dijkstra's algorithm
'n = number of nodes in graph
'start = index of start node
'init distances A
For j = 1 To n
A(j) = Infinity
Next j
A(start) = 0
'init P (path) to "no paths" and Q = set of all nodes
For j = 1 To n
Q(j) = True
P(j) = 0
Next j
Do While True 'loop will exit! (see below)
'find node u in Q with smallest distance to start
dist = Infinity
For i = 1 To n
If Q(i) Then
If A(i) < dist Then
dist = A(i)
u = i
End If
End If
Next i
If dist = Infinity Then Exit Do 'no more nodes available - done!
'remove u from Q
Q(u) = False
'loop over neighbors of u that are in Q
For j = 1 To n
If Q(j) And E(u, j) <> Infinity Then
'check if path to neighbor j via u is shorter than current estimated distance to j
alt = A(u) + E(u, j)
If alt < A(j) Then
'yes, replace with new distance and remember "previous" hop on the path
A(j) = alt
P(j) = u
End If
End If
Next j
Loop
End Sub
Public Function GetPath(source, target) As String
'reconstruct shortest path from source to target
'by working backwards from target using the P(revious) array
Dim path As String
If P(target) = 0 Then
GetPath = "No path"
Else
path = ""
u = target
Do While P(u) > 0
path = Format$(u) & " " & path
u = P(u)
Loop
GetPath = Format$(source) & " " & path
End If
End Function
Public Sub DijkstraTest()
'main function to solve Dijkstra's algorithm and return shortest path between
'a node and every other node in a digraph
' define problem:
' number of nodes
n = 5
' reset connection/cost per edge
For i = 1 To n
For j = 1 To n
E(i, j) = Infinity
Next j
P(i) = 0
Next i
' fill in the edge costs
E(1, 2) = 10
E(1, 3) = 50
E(1, 4) = 65
E(2, 3) = 30
E(2, 5) = 4
E(3, 4) = 20
E(3, 5) = 44
E(4, 2) = 70
E(4, 5) = 23
E(5, 1) = 6
'Solve it for every node
For v = 1 To n
Dijkstra n, v
'Print solution
Debug.Print "From", "To", "Cost", "Path"
For j = 1 To n
If v <> j Then Debug.Print v, j, IIf(A(j) = Infinity, "---", A(j)), GetPath(v, j)
Next j
Debug.Print
Next v
End Sub
</lang>
Output (using the same graph as in the Floyd-Warshall algorithm below):
<pre>
DijkstraTest
From To Cost Path
1 2 10 1 2
1 3 40 1 2 3
1 4 60 1 2 3 4
1 5 14 1 2 5
From To Cost Path
2 1 10 2 5 1
2 3 30 2 3
2 4 50 2 3 4
2 5 4 2 5
From To Cost Path
3 1 49 3 4 5 1
3 2 59 3 4 5 1 2
3 4 20 3 4
3 5 43 3 4 5
From To Cost Path
4 1 29 4 5 1
4 2 39 4 5 1 2
4 3 69 4 5 1 2 3
4 5 23 4 5
From To Cost Path
5 1 6 5 1
5 2 16 5 1 2
5 3 46 5 1 2 3
5 4 66 5 1 2 3 4
</pre>
==[[Floyd-Warshall algorithm]]==
[[File:FloydGraph.png|thumb|250px|Graph used in this and Dijkstra's algorithm]]
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.
Line 373 ⟶ 520:
</lang>
Output (note that some titles are truncated at the start or the end. An improvement could be to wrap these titles around if there is room on the other end):
<pre>
kwic
| |||