Another Dijkstra's shortest path Algorithm implementation

Post your FreeBASIC source, examples, tips and tricks here. Please don’t post code without including an explanation.
Post Reply
Pitto
Posts: 122
Joined: Nov 19, 2012 19:58

Another Dijkstra's shortest path Algorithm implementation

Post by Pitto »

Hi all,

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

Tourist Trap
Posts: 2958
Joined: Jun 02, 2015 16:24

Re: Another Dijkstra's shortest path Algorithm implementation

Post by Tourist Trap »

It seems that a well known soccer game will have a great shortest path implementation very soon ;)
Post Reply