Am i doing correctly?

[magnifz97]

Hello everyone. I'm trying to implement Dijkstra Algorithm for finding the shortest path inside my code. Is it correct? If not can someone help me?

This is the function's section of my code

const int Num = 20;

//The struct for storing node

struct vtx {
	int num;		//number of the node(s)
	//Coordinates
	GLfloat x;	
	GLfloat y;
	
	bool operator != (const vtx& right_hs)
	{
		return this->num != right_hs.num;
	}

};


int Sizee;
int len;
float **grph;		//The adjacency matrix

vtx paths[50];	//array to store the path
vtx tmp[50];
vtx node[Num];
vtx start;	
vtx end;
int m = 0;	

stack<vtx> bt;
        


void FindShortestPath()
{
    vtx previous, Next, curr = start;
    float distance, Best;
	bool *checker = new bool[Sizee];
	bool no_Option;
	
	
	for (int i = 0; i < Sizee; i++)
		checker[i] = true;
        checker[curr.num] = false;
	
	bt.push(start);
	
	while (curr != end) 
	{
		Best = 9999;
		no_Option = true;
		
		for (int i = 0; i < Sizee; i++) 
		{
			if (grph[curr.num][i] != -1 && checker[i] == true) 
			{
				no_Option = false;
				distance = pow((node[i].x - end.x), 2) + pow((node[i].y - end.y), 2);
				
				if (distance < Best) 
				{
					Best = distance;
					Next = node[i];
				}
			}
		}
		
		if (!no_Option) 
		{
			bt.push(Next);
			checker[Next.num] = false;
			curr = Next;
		}
		
		else 
		{
			curr = bt.top();
			bt.pop();
		}
	}
	
	len = bt.size();
	int s = len - 1;

	while (!bt.empty()) 
	{
		curr = bt.top();
		bt.pop();
		tmp[s] = curr;
		s--;
	}
	
	for (int i = 0; i < len - 1; i++) 
	{
		if (grph[tmp[i].num][tmp[i + 1].num] != -1) 
		{
			paths[m] = tmp[i];
			m++;
		}
		
		else 
		{
			for (int z = 0; z < Sizee; z++) 
			{
				if (grph[tmp[i].num][z] != -1) 
				{
					if (grph[z][tmp[i + 1].num] != -1) 
					{
						paths[m++] = tmp[i];
						paths[m] = node[z];
						m++;
					}
				}
			}

		}
	}
	
	paths[m] = tmp[len - 1];
	len = m + 1;
	
	for (int i = 0; i < len; i++) 
	{
		cout << paths[i].num << " - > ";
	}
	
	delete checker;
}

[SakurasouBusters]

Is it correct?

You should at least tell us if this code works.

[magnifz97]

@SakurasouBusters
It is working. But sometimes it doesn't give me the best path ._.

[SakurasouBusters]

Can you give us an example?

[lastchance]

I'm struggling to match this code up to my understanding of Dijkstra's algorithm (which was always done with pen and paper I'm afraid)! Could you put some comments in the code.

In line 55 I'm guessing that you are checking a connection between nodes i and curr.num.
However, the distance (squared) that you calculate in line 58 appears to be between node i and end. Did you mean 'curr' instead of 'end' here as you seem to be searching for the shortest link to 'curr'? I'm unclear what the role of 'end' is here in this fragment of the total code.

If this is completely naive then I apologise and please ignore.

[magnifz97]

@SakurasouBusters i don't know how to show the example because this code will auto generate to a map which is already provided.

@lastchance end indicates the end of the node... Start indicate the start of the node.. Curr is the current position.

Or can someone give me an example if a good Dijkstra algorithm which based on the global declaration variable? ._.

Your help is very appreciated.

[lastchance]

Code below to use with input files:
nodes.dat

A B C D E F G

and
weights.dat

A B  3   3
A C  8   8
A D  12  12
B E  2   2
B C  4   4
C D  3   3
C E  1   1
C F  9   9
C G  12  12
D F  5   5
E G  14  14
F G  3   3

Name your nodes and put them in nodes.dat.
Weights ("distances") between nodes are put in weights.dat

The only reason weights are put in twice is if you want to make a route one-directional - in which case set one of the two weights to something very large (so effectively ruling it out from the "shortest path").

It doesn't use an adjacency matrix like your coursework because Dijkstra's algorithm can be used for a lot of other minimising problems - cost, time, etc. as well as distance. Weights of connectors are therefore put in separately beforehand, not calculated in situ from distances like your first code example.

These particular nodes/weights come from a teaching example in a British A-level textbook. The code won't work (probably) with negative weights or disconnected graphs.

The main() routine should give you clues to steps in your own work.

#include <cstdlib>
#include <cmath>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;


const double LARGE = 1.0e30;
const double SMALL = 1.0e-10;


//======================================================================


class node
{
public:
   string name;
   float dist;
   bool final;
   vector<int> adj;
   vector<double> wt;
   vector<double> wtm;       // minus the weight for the reverse direction

   node() { name = "A";   dist = LARGE;   final = false; };
   node( string nm ) : name(nm) { dist = LARGE;   final = false; };
};


//======================================================================


int findNode( vector<node> v, string nm )
{
   int vsize = v.size();
   
   for ( int n = 0; n < vsize; n++ )
   {
      if ( v[n].name == nm ) return n;
   }

   cout << "Cannot find a node of name " + nm << endl;
   exit(1);
}


//======================================================================


void addWt( vector<node> &v, string name1, string name2, double wt12, double wt21 )
{
   int n1 = findNode( v, name1 );
   int n2 = findNode( v, name2 );

   v[n1].adj.push_back(  n2   );
   v[n1].wt .push_back(  wt12 );
   v[n1].wtm.push_back( -wt21 );

   v[n2].adj.push_back(  n1   );
   v[n2].wt .push_back(  wt21 );
   v[n2].wtm.push_back( -wt12 );
}


//======================================================================


void showDistances( vector<node> v )
{
   int num = v.size();
   
   cout << "Distances: " << endl;
   for ( int n = 0; n < num; n++ )
   {
      cout << "Node " + v[n].name + ": " << v[n].dist << endl;
   }
   cout << endl;
}


//======================================================================


void showPath( vector<node> v, vector<int> path )
{
   int numPath = path.size();
   
   cout << "Shortest path: " << endl;
   for ( int n = 0; n < numPath; n++ )
   {
      cout << v[path[n]].name;
   }
   cout << endl;
   cout << "Distance = " << v[path[numPath-1]].dist << endl;
}


//======================================================================


int main()
{
   vector<node> v;
   vector<int> path;
   ifstream in;
   int nstart, nend, ncur, nnext;
   int i, n;
   int numFinal;
   int numPath;
   int n1, n2;
   int nMin;
   double distMin;
   double curDist, tmpDist;
   double tmp;
   bool found;
   string name, name1, name2;
   double wt1, wt2;
   int numNodes = 0;


   // Read nodes
   in.open( "nodes.dat" );
   while ( in >> name )
   {
       v.push_back( node( name ) );
       numNodes++;
   }
   in.close();


   // Read Weights
   in.open( "weights.dat" );
   while ( in >> name1 >> name2 >> wt1 >> wt2 ) addWt( v, name1, name2, wt1, wt2 );
   in.close();


   // Get start node
   cout << "Input the start node: ";   cin >> name;
   nstart = findNode( v, name );


   // Initialise start node
   ncur = nstart;   v[ncur].dist = 0;   v[ncur].final = true;   numFinal = 1;


   // Get distances (to all nodes)
   cout << "Computing distances ..." << endl;
   while ( numFinal < numNodes )
   {
      // Update distances via current node
      curDist = v[ncur].dist;                                   
                                                                
      for ( i = 0; i < v[ncur].adj.size(); i++ )
      {                                                         
         n = v[ncur].adj[i];           // adjacent node         
         tmpDist = curDist + v[ncur].wt[i];                     
         if ( v[n].dist > tmpDist ) v[n].dist = tmpDist;        
      }
                                                                
      // Finalise the unfinalised node with the least distance
      distMin = LARGE;
      found = false;                                         
      for ( n = 0; n < numNodes; n++ )
      {                                                         
         if ( !v[n].final && v[n].dist < distMin )
         {
            nMin = n;
            distMin = v[n].dist;
            found = true;
         }
      }
      if ( !found )
      {
         cout << "Unable to reach all nodes" << endl;
         exit(1);
      }
      v[nMin].final = true;
      ncur = nMin;
      numFinal++;
   }
   cout << "... done" << endl;
   cout << endl;

   showDistances( v );


   // Get end node
   cout << "Input the end node: ";   cin >> name;
   cout << endl;
   nend = findNode( v, name );

   // Work back to start
   ncur = nend;
   curDist = v[ncur].dist;
   path.push_back(ncur);

   while( ncur != nstart )
   {
      found = false;
      for ( i = 0; i < v[ncur].adj.size(); i++ )
      {                                                         
         n = v[ncur].adj[i];           // adjacent node    
         tmpDist = curDist + v[ncur].wtm[i];               
                                                           
         if ( abs( v[n].dist - tmpDist ) < SMALL )
         {
            found = true;
            break;
         }
      }
      if ( !found )
      {
         cout << "Unable to reverse path" << endl;
         exit(1);
      }
      ncur = n;                    
      curDist = v[ncur].dist;
      path.push_back(ncur);
   }

   // Get the forward path by swapping
   numPath = path.size();
   for ( n1 = 0; n1 < numPath / 2; n1++ )
   {
       n2 = numPath - 1 - n1;
       tmp = path[n1];
       path[n1] = path[n2];
       path[n2] = tmp;
   }

   showPath( v, path );
}