kpillsb39 0 Newbie Poster

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();
     }
}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.