## Another Dijkstra's shortest path Algorithm implementation

Pitto
Posts: 119
Joined: Nov 19, 2012 19:58

### Another Dijkstra's shortest path Algorithm implementation

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 valuefunction findMin(x as integer, y as integer) as integer   if (x < y) then      return x   end if   return yend function'this function will check if the vertex is markedfunction 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 0end function'this sub will find shortest path between source and destination vertexsub 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

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