How to resolve the algorithm Dijkstra's algorithm step by step in the AutoHotkey programming language
How to resolve the algorithm Dijkstra's algorithm step by step in the AutoHotkey programming language
Table of Contents
Problem Statement
Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge path costs, producing a shortest path tree.
This algorithm is often used in routing and as a subroutine in other graph algorithms.
For a given source vertex (node) in the graph, the algorithm finds the path with lowest cost (i.e. the shortest path) between that vertex and every other vertex.
If the vertices of the graph represent cities and edge path costs represent driving distances between pairs of cities connected by a direct road, Dijkstra's algorithm can be used to find the shortest route between one city and all other cities.
As a result, the shortest path first is widely used in network routing protocols, most notably:
The inputs to Dijkstra's algorithm are a directed and weighted graph consisting of 2 or more nodes, generally represented by:
A destination node is not specified. The output is a set of edges depicting the shortest path to each destination node.
You can use numbers or names to identify vertices in your program.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Dijkstra's algorithm step by step in the AutoHotkey programming language
Source code in the autohotkey programming language
Dijkstra(data, start){
nodes := [], dist := [], Distance := [], dist := [], prev := [], Q := [], min := "x"
for each, line in StrSplit(data, "`n" , "`r")
field := StrSplit(line,"`t"), nodes[field.1] := 1, nodes[field.2] := 1
, Distance[field.1,field.2] := field.3, Distance[field.2,field.1] := field.3
dist[start] := 0, prev[start] := ""
for node in nodes {
if (node <> start)
dist[node] := "x"
, prev[node] := ""
Q[node] := 1
}
while % ObjCount(Q) {
u := MinDist(Q, dist).2
for node, val in Q
if (node = u) {
q.Remove(node)
break
}
for v, length in Distance[u] {
alt := dist[u] + length
if (alt < dist[v])
dist[v] := alt
, prev[v] := u
}
}
return [dist, prev]
}
;-----------------------------------------------
MinDist(Q, dist){
for node , val in Q
if A_Index=1
min := dist[node], minNode := node
else
min := min < dist[node] ? min : dist[node] , minNode := min < dist[node] ? minNode : node
return [min,minNode]
}
ObjCount(Obj){
for key, val in Obj
count := A_Index
return count
}
data =
(
A B 7
A C 9
A F 14
B C 10
B D 15
C D 11
C F 2
D E 6
E F 9
)
nodes:=[], Distance := []
for each, line in StrSplit(data, "`n" , "`r")
field := StrSplit(line,"`t"), nodes[field.1] := 1, nodes[field.2] := 1
, Distance[field.1,field.2] := field.3 , Distance[field.2,field.1] := field.3
for node, v in nodes
nodeList .= (nodeList?"|":"") node (A_Index=1?"|":"")
Gui, add, Text,, From:
Gui, add, Text, x200 yp, To:
Gui, add, DDL, xs vFrom gSubmit, % nodeList
Gui, add, DDL, x200 yp vTo gSubmit, % nodeList
Gui, add, ListView, xs w340 r6, From|>|To|Distance
Gui, add, Text, vT1 xs w340 r1
Gui, +AlwaysOnTop
Gui, show
Loop 4
LV_ModifyCol(A_Index, "80 Center")
Submit:
Gui, Submit, NoHide
GuiControl, , T1, % ""
LV_Delete()
if !(From && To) || (From = To)
return
res := Dijkstra(data, From) , xTo := xFrom := DirectFlight := "" , origin := to
GuiControl, , T1, no routing found
if !res[1, To] ; no possible route
return
Routing:
Loop % objCount(nodes)
for xTo , xFrom in res.2
if (xTo = To)
{
LV_Insert(1,"", xFrom, ">" , xTo, Distance[xFrom , xTo]), To := xFrom
if (xFrom = From)
break, Routing
}
GuiControl, , T1, % "Total distance = " res.1[origin] . DirectFlight
return
esc::
GuiClose:
ExitApp
return
You may also check:How to resolve the algorithm Program termination step by step in the AArch64 Assembly programming language
You may also check:How to resolve the algorithm Menu step by step in the FutureBasic programming language
You may also check:How to resolve the algorithm Day of the week step by step in the Seed7 programming language
You may also check:How to resolve the algorithm Find the missing permutation step by step in the Quackery programming language
You may also check:How to resolve the algorithm User input/Graphical step by step in the C++ programming language