Another Dijkstra's shortest path Algorithm implementation

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

Another Dijkstra's shortest path Algorithm implementation

Postby Pitto » Aug 07, 2017 21:09

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

Postby Tourist Trap » Aug 08, 2017 20:18

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

Return to “Tips and Tricks”

Who is online

Users browsing this forum: Google [Bot] and 6 guests