#include<iostream.h>
#include<conio.h>

class dijkstra
{
        private:
                int graph[15][15];
                int path[15],p[15],distances[15];
                int source;
                char c;
                int num_of_vertices;
        public:
                int minimum();
                void read();
                void initialize();
                void printpath(int);
                void algorithm();
                void output();
};

//***************read data***************
void dijkstra::read()
{
        cout<<"enter the number of vertices :";
        cin>>num_of_vertices;
        while(num_of_vertices<=0)
        {
                cout<<"\nthis is meaningless,enter the number carefully\n";
                cout<<"enter the number of vertices :";
                cin>>num_of_vertices;
        }
        cout<<"\nenter the matrix:\n";
        for(int i=1;i<=num_of_vertices;i++)
        {
                cout<<"\nenter the weights for the row "<<i<<":\n";
                for(int j=1;j<=num_of_vertices;j++)
			if (i!=j)
                	{
                        	cout<<"L["<<char(i+96)<<"]["<<char(j+96)<<"]= ";
                        	cin>>graph[i][j];
                        	while(graph[i][j]<0)
                        	{
                                	cout<<"\nu should enter the positive valued weights only";
					cout<<"\nenter the value again :";
                                	cin>>graph[i][j];
                       		}
                	}
			else
                                graph[i][j]=0;
        }
        cout<<"\nenter the source vertex letter: ";
        cin>>c;
        source=int(c)-96;
        while(source<1 || source>num_of_vertices)
        {
                 cout<<"\nu should enter the positive valued weights only\nenter the value again :";
                 cin>>c;
                 source=int(c)-96;
        }
}

//***************initialize***************
void dijkstra::initialize()
{
        for(int i=1;i<=num_of_vertices;i++)
        {
                p[i]=0;
                distances[i]=999;
                path[i]=0;
        }
        distances[source]=0;
}

//***************algorithm***************
void dijkstra::algorithm()
{
        initialize();
        int count=0;
        int i;
        int u;
        for(int j=0;j<num_of_vertices;j++)
        {
                u=minimum();
                p[u]=1;
                for(i=1;i<=num_of_vertices;i++)
                {
                        if(graph[u][i]>0)
                        {
                                if(p[i]!=1)
                                {
                                        if(distances[i]>distances[u]+graph[u][i])
                                        {
                                                distances[i]=distances[u]+graph[u][i];
                                                path[i]=u;
                                        }
                                }
                        }
                }
        }

}

//***************printpath***************
void dijkstra::printpath(int i)
{
        cout<<endl;
        if(i==source)
        {
                cout<<char(source+96);
        }
        else if(path[i]==0)
                cout<<"no path from "<<char(source+96)<<" to "<<char(i+96);
        else
        {
                printpath(path[i]);
                cout<<".."<<char(i+96);
        }
}

//***************output***************
void dijkstra::output()
{
        for(int i=1;i<=num_of_vertices;i++)
        {
                printpath(i);
                if(distances[i]!=999)
                        cout<<"->("<<distances[i]<<")\n";
        }
        cout<<endl;
}

//***************minimum***************
int dijkstra::minimum()
{
        int min=999;
        int i,t;
        for(i=1;i<=num_of_vertices;i++)
        {
                if(p[i]!=1)
                {
                        if(min>=distances[i])
                        {
                                min=distances[i];
                                t=i;
                        }
                }
        }
        return t;
}

//***************main***************
void main()
{
        dijkstra s;
        s.read();
        s.algorithm();
        s.output();
        getch();
}