#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();
     }
}