How to resolve the algorithm Dijkstra's algorithm step by step in the Ring programming language
How to resolve the algorithm Dijkstra's algorithm step by step in the Ring 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 Ring programming language
Source code in the ring programming language
# Project : Dijkstra's algorithm
graph = [["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]]
dbegin = "a"
dend = "e"
powlen = pow(2,len(graph)) - 1
dgraph = list(powlen)
dtemp = list(powlen)
lenold = 10
lennew = 0
sumold = 30
sumnew = 0
powerset(graph)
for n = 1 to len(dgraph)
dtemp[n] = str2list(substr(dgraph[n], " ", nl))
next
for n = 1 to len(dtemp)
if len(dtemp[n]) > 3 and dtemp[n][1] = dbegin and dtemp[n][len(dtemp[n])-1] = dend
flag = 1
for m = 1 to len(dtemp[n])/3-1
if dtemp[n][m*3-1] != dtemp[n][m*3+1]
flag = 0
ok
next
if flag = 1
lennew = len(dtemp[n])
if lennew <= lenold
lenold = lennew
sumnew = 0
for m = 1 to len(dtemp[n])/3
sumnew = sumnew + dtemp[n][m*3]
next
if sumnew < sumold
sumold = sumnew
gend = dtemp[n]
ok
ok
ok
ok
next
str = ""
see dbegin + " " + dend + " : "
for m = 1 to len(gend)/3
str = str + gend[(m-1)*3 + 1] + " " + gend[(m-1)*3 + 2] + " " + gend[(m-1)*3 + 3] + " -> "
next
str = left(str,len(str)-4)
str = str + " cost : " + sumold + nl
see str + nl
func powerset(list)
s = "{"
p = 0
for i = 2 to (2 << len(list)) - 1 step 2
s = ""
for j = 1 to len(list)
if i & (1 << j)
s = s + list[j][1] + " " + list[j][2] + " " + list[j][3] + " "
ok
next
if right(s,1) = " "
s = left(s,len(s)-1)
ok
p = p + 1
dgraph[p] = s
next
You may also check:How to resolve the algorithm Comments step by step in the PowerShell programming language
You may also check:How to resolve the algorithm Bitmap/Read an image through a pipe step by step in the Nim programming language
You may also check:How to resolve the algorithm Copy a string step by step in the Retro programming language
You may also check:How to resolve the algorithm A+B step by step in the PureBasic programming language
You may also check:How to resolve the algorithm Array concatenation step by step in the QB64 programming language