I've translated a C source by Yusuf Shakeel
The vertexes are linked in both orthogonal and diagonal way.
As soon as possible I wish make it interactive
Code: Select all
'file: dijkstra.c
'author: yusuf shakeel - 'date: 2014-03-03
'source from:
'https://www.dyclassroom.com/graph/dijkstra-algorithm-finding-shortest-path
'translated to FreeBasic by Pitto
'description: find shortest path between two vertices
'vertices are represented using numbers.
'in this example the algorithm will search shortest path from vertex 0 to 15
'in this example each vertex is connected to adjacent vertex in an orthogonal grid,
'and also in diagonal; the orthogonal edge have weight 10, diagonal have weight 14
'*---*---*
'|\ | /|
'| \ | / |
'| \|/ |
'*--[V]--*
'| /|\ |
'| / | \ |
'|/ | \|
'*---*---*
' the vertex n. 10 isn't connected with other vertex
'0---1---2---3
'| X | X | X |
'4- -5---6---7
'| X | / \ |
'8---9 10 11
'| X | \ / |
'12--13--14--15
'constant to represent infinity
'it is assumed that no edge in the vertex will have weight equal
'to this value.
#define INF 9999
'total number of vertices in the graph
#define V 16
'this function will return the minimum value
function findMin(x as integer, y as integer) as integer
if (x < y) then
return x
end if
return y
end function
'this function will check if the vertex is marked
function isMarked(x as integer, markedVertices() as integer, markedVerticesIdx as integer) as integer
dim i as integer = 0
for i = 0 to markedVerticesIdx-1
if x = markedVertices(i) then return 1
next i
return 0
end function
'this sub will find shortest path between source and destination vertex
sub dijkstra(graph() as integer, src as integer, dest as integer)
'variables
dim as integer i, r, c, tmpC, min, currVertex, edgeWt = 0, destValue = 0
dim as integer markedValue = 0, wtTableR = 0, markedVerticesIdx = 0
'array containing vertices in the shortest path
dim shortestPathVertices(0 to V-1) as integer
for r = 0 to Ubound (shortestPathVertices)
shortestPathVertices(r) = -1
next r
dim shortestPathVerticesIdx as integer = 0
'this table will hold the weight
dim weightTable(0 to V-1, 0 to V-1) as integer
for r = 0 to V -1
for c = 0 to V-1
weightTable(r,c) = INF
next c
next r
weightTable(wtTableR,src) = 0
wtTableR+=1
'vertices that are marked
dim markedVertices(0 to V-1) as integer
for r = 0 to Ubound (markedVertices)
markedVertices(r) = -1
next r
markedVertices(markedVerticesIdx) = src
markedVerticesIdx +=1
currVertex = src
'find shortest path
while(currVertex <> dest)
'copy marked values to the next row of weightTable
for i = 0 to markedVerticesIdx -1
c = markedVertices(i)
weightTable(wtTableR,c) = weightTable(wtTableR - 1,c)
next i
'find the weight from the current vertex to all the other
'vertices that are directly connected and not yet marked
for c = 0 to V-1
if (c <> currVertex and isMarked(c, markedVertices(), markedVerticesIdx) = 0) then
edgeWt = graph(currVertex,c)
destValue = weightTable(wtTableR - 1,c)
markedValue = weightTable(wtTableR,currVertex)
min = findMin(destValue, markedValue + edgeWt)
weightTable(wtTableR,c) = min
end if
next c
'find minimum unmarked vertices in current row
min = INF
for c = 0 to V-1
if (isMarked(c, markedVertices(), markedVerticesIdx) = 0) then
if (weightTable(wtTableR,c) < min) then
min = weightTable(wtTableR,c)
tmpC = c
end if
end if
next c
'found a new vertex for marking
markedVertices(markedVerticesIdx) = tmpC
markedVerticesIdx+=1
currVertex = tmpC
'variables update
wtTableR+=1
wend
'compute shortest path vertices
c = dest
shortestPathVertices(shortestPathVerticesIdx)= c
shortestPathVerticesIdx +=1
markedValue = weightTable(wtTableR - 1,dest)
for r = wtTableR - 2 to 0 step -1
'for r = wtTableR - 2 to r >= 0 step -1
if (weightTable(r,c) <> markedValue) then
c = markedVertices(r)
markedValue = weightTable(r,c)
shortestPathVertices(shortestPathVerticesIdx) = c
shortestPathVerticesIdx +=1
end if
next r
'display the weight and shortest path
print "Shortest Path between " + str(src) + " and " + str(dest)
for i = shortestPathVerticesIdx-1 to 0 step -1
'for i = shortestPathVerticesIdx-1 to i >= 0 step -1
print shortestPathVertices(i)
if (i > 0) then
print " --> "
end if
next i
print ""
print "Weight of the path: " + str(weightTable(wtTableR-1,dest))
end sub
'2d array which holds the weight of the edges
' 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
dim graph (0 to V-1, 0 to V-1) as integer = _
{_
{ 0, 10, INF, INF, 10, 14, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF} ,_ '0
{ 10, 0, 10, INF, 14, 10, 14, INF, INF, INF, INF, INF, INF, INF, INF, INF} ,_ '1
{INF, 10, 0, 10, INF, 14, 10, 14, INF, INF, INF, INF, INF, INF, INF, INF} ,_ '2
{INF, INF, 10, 0, INF, INF, 14, 10, INF, INF, INF, INF, INF, INF, INF, INF} ,_ '3
{ 10, 14, INF, INF, 0, 10, INF, INF, 10, 14, INF, INF, INF, INF, INF, INF} ,_ '4
{ 14, 10, 14, INF, 10, 0, 10, INF, 14, 10, INF, INF, INF, INF, INF, INF} ,_ '5
{INF, 14, 10, 14, INF, 10, 0, 10, INF, 14, INF, 14, INF, INF, INF, INF} ,_ '6
{INF, INF, 14, 10, INF, INF, 10, 0, INF, INF, INF, 11, INF, INF, INF, INF} ,_ '7
{INF, INF, INF, INF, 10, 14, INF, INF, 0, 10, INF, INF, 10, 14, INF, INF} ,_ '8
{INF, INF, INF, INF, 14, 10, 14, INF, 10, 0, INF, INF, 14, 10, 14, INF} ,_ '9
{INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 0, INF, INF, INF, INF, INF} ,_ '10
{INF, INF, INF, INF, INF, INF, 14, 10, INF, INF, INF, 0, INF, INF, 14, 10} ,_ '11
{INF, INF, INF, INF, INF, INF, INF, INF, 10, 14, INF, INF, 0, 10, INF, INF} ,_ '12
{INF, INF, INF, INF, INF, INF, INF, INF, 14, 10, INF, INF, 10, 0, 10, INF} ,_ '13
{INF, INF, INF, INF, INF, INF, INF, INF, INF, 14, INF, 14, INF, 10, 0, INF} ,_ '14
{INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 10, INF, INF, 10, 0}} '15
'source and destination vertices
dim as integer src = 0
dim as integer dest = 15
'find shortest path
dijkstra(graph(), src, dest)
sleep