How to resolve the algorithm Dijkstra's algorithm step by step in the AutoHotkey programming language

Published on 12 May 2024 09:40 PM

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