Hi,
I have built a program for Dijkstra's algorithm, but not sure why it does not display the shortest path thru the matrix. Would someone please point me in the right direction to get the code to work.
Thanks,
code follows, no errors, but no display of path vertices for shortest path.
#include<iostream> //cout, cin, cerr, ...
#include<cmath> //math
#include<queue> //queue
using namespace std;
class queue
{
private:
int q[21];
int front, rear;
protected:
queue()
{
front=rear=-1;
}
int isempty()
{
if((front==-1 && rear==-1) || (front>rear))
{
front=rear=-1;
return 1;
}
return 0;
}
int push(int a)
{
if(isempty())
front++;
q[++rear]=a;
}
int del()
{
return q[front++];
}
};
class dijkstra
{
private:
int ajMat[21][21];
int set[21],predecessor[21],mark[21],pathestimate[21];
int source;
int SIZE;
public:
int minimum();
void initialize();
void printpath(int);
void algorithm();
void output();
};
void dijkstra::initialize()
{
for(int i=1;i<=SIZE;i++)
{
mark[i]=0;
pathestimate[i]=999;
predecessor[i]=0;
}
pathestimate[source]=0;
}
void dijkstra::algorithm()
{
initialize();
int count=0;
int i;
int j;
while(count<SIZE)
{
j=minimum();
set[++count]=j;
mark[j]=1;
for(i=1;i<=SIZE;i++)
{
if(ajMat[i][j]>0)
{
if(mark[i]!=1)
{
if(pathestimate[i]>pathestimate[j]+ajMat[i][j])
{
pathestimate[i]=pathestimate[j]+ajMat[i][j];
predecessor[i]=j;
}
}
}
}
}
}
void dijkstra::printpath(int i)
{
if(i==source)
{
cout<<source;
}
else if(predecessor[i]==0)
cout<<"no path from "<<source<<" to "<<i<<endl;
else
{
printpath(predecessor[i]);
cout<<".."<<i<<endl;
}
}
void dijkstra::output()
{
for(int i=1;i<=SIZE;i++)
{
printpath(i);
if(pathestimate[i]!=999)
cout<<"->("<<pathestimate[i]<<")"<<endl;
}
}
int dijkstra::minimum()
{
int min=999;
int i,t;
for(i=1;i<=SIZE;i++)
{
if(mark[i]!=1)
{
if(min>=pathestimate[i])
{
min=pathestimate[i];
t=i;
}
}
}
return t;
};
void main()
{
const int SIZE = 21; //establish ajacency matrix int size
int ajMat[21][21]= {
{ 0,14, 0, 0, 9, 0, 0,14, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{14,-1,13, 0, 7, 3,13, 0,12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{ 0,13,-1,11, 0, 0, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{ 0, 0,11,-1, 0, 0,11, 0, 0, 0, 0,11, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{ 9, 7, 0, 0,-1, 0, 0, 2, 2, 0, 0, 0,11, 0, 0, 0, 0, 0, 0, 0, 0},
{ 0, 3, 0, 0, 0,-1, 6, 0, 4, 4, 5,11,12, 0, 0, 0, 0, 0, 0, 0, 0},
{ 0,13, 9,11, 0, 6,-1, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{14, 0, 0, 0, 2, 0, 0,-1, 0, 0, 0, 0, 6,12, 0, 0, 0, 0, 0, 0, 0},
{ 0,12, 0, 0, 2, 4, 0, 0,-1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0},
{ 0, 0, 0, 0, 0, 0, 4, 0, 0,-1, 6, 0,10, 0, 1, 0, 0, 0, 0, 0, 0},
{ 0, 0, 0, 0, 0, 5, 0, 0, 0, 6,-1, 3, 0, 8, 9, 7, 0, 0,11, 0, 0},
{ 0, 0, 0,11, 0,11, 6, 0, 0, 0, 3,-1, 0, 0, 0, 0,10, 0, 0, 0, 0},
{ 0, 0, 0, 0,11,12, 0, 6, 2,10, 0, 0,-1, 3, 7, 0, 0, 0, 0, 0, 0},
{ 0, 0, 0, 0, 0, 0, 0,12, 0, 0, 0, 0, 3,-1,12, 0, 0, 9, 0, 0, 0},
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 8, 0, 7,12,-1, 0, 0, 9, 1, 0, 0},
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 0, 0, 0, 0,-1, 3, 0, 7, 5, 8},
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7,10, 0, 0, 0, 3,-1, 0, 0, 0,13},
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 9, 0, 0,-1, 3, 0, 0},
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,11, 0, 0, 0, 1, 7, 0, 3,-1, 9, 0},
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 9,-1, 8},
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8,13, 0, 0, 8,-1}};
char nodeName ='&'; //establish char node
for(int i=0;i<SIZE;i++) //establish outer loop
{
nodeName = 'A'+i; //establish node name
cout<<" Node "<<static_cast<char>(nodeName)//display node name
<<" Neighbors are: "; //enter neighbors names
for(int j=0; j<SIZE; j++) //establish inner loop
{
if(ajMat[i][j]>0) //if number greater than 0
{
nodeName = 'A'+j; //node name plus neighbor
cout<<" Node "<<static_cast<char>(nodeName)//display node name
<<","; //place comma between neighbors
}
}
cout<<endl;
}
{
dijkstra s;
s.algorithm();
s.output();
}
}