// Dijkstra.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"


#include <iostream>
#include <fstream>
#include <stdlib.h>
using namespace std;

const int n=50; //the number of vertices

#define max 32767


class Graph	{
	public:
	int arcs[n+1][n+1]; //Adjacency matrix of the graph
	int dist[n+1];  //Store the shortest path from the source node to each other node
	int path[n+1];  //Store the previous node of the node on the shortest path
	int s[n+1];   //The mark of the node in shortest path
	void Dijkstra(Graph &t, const int V1,const int V2,int print);
};

void Graph::Dijkstra(Graph &t, const int V1,const int V2,int print)	{
	for(int i=1; i<=n; i++)	{
		t.dist[i]=t.arcs[V1][i];
		t.s[i]=0;
		if((i!=V1)&&(t.dist[i]<max))
			t.path[i]=V1;
		else t.path[i]=0;
	}
	
	t.s[V1]=1; t.dist[V1]=0;
	for(int i=1; i<n; i++)	{
		int min=max; int u=V1;
		for(int j=1; j<=n; j++)
		if(!t.s[j]&&t.dist[j]<min){u=j,min=t.dist[j];
		}
   
	t.s[u]=1;
	for(int w=1; w<=n;w++)
		if(!t.s[w]&&t.arcs[u][w]<max&&t.dist[u]+t.arcs[u][w]<t.dist[w]){t.dist[w]=t.dist[u]+t.arcs[u][w]; t.path[w]=u;}
 }
 
	
	if(print==1){
		for(int i=1; i<=n; i++)	{
			if(i!=V1)	{
			if(t.dist[i]!=max)	{
				cout<<t.dist[i]<<":";
				cout<<i;}
				int pre=t.path[i];
				while(pre!=0)	{ 
					cout<<"←"<<pre;
					pre=t.path[pre];
				}
   if(t.dist[i]!=max)
		cout<<endl;
			}
			
		}
	}

	if(print==0){
		if(t.dist[V2]!=max)	{
		cout<<t.dist[V2]<<":";
		cout<<V2;}
		int pre=t.path[V2];
		while(pre!=0)	{ 
			cout<<"←"<<pre;
			pre=t.path[pre];
				}
		if(t.dist[V2]!=max)
			cout<<endl;
			}
		
	}

int main(int argc, char* argv[]){
	Graph t;
	int i,j,s,d,max_node=0;

	for( i=1; i<=n;i++)
		for(j=1; j<=n; j++)
			if(i==j)t.arcs[i][j]=0;
			else t.arcs[i][j]=max;
 
	ifstream inPutFile("graph.txt");//Read the information of the files and store it into the matrix
	int k=0; i=0; j=0;
	if(inPutFile){
			do{
				inPutFile>>i>>j;
				t.arcs[i][j]=1;
				t.arcs[j][i]=1;
				if(i>=j){
					if(i>=max_node)
					max_node=i;
				}
				else if(j>=max_node)
					max_node=j;
					
				if(k<i) k=i;
				if(k<j) k=j;
			}
			while(!inPutFile.eof());
		}
		else{
			cerr<<"Open error\n";
		}
		
		//Print the graph in linked list
		for(int m=1;m<=max_node;m++){
			cout<<m<<"---";
			for(int n=1;n<=max_node;n++){
				if(t.arcs[m][n]==1)
					cout<<n<<",";
			}
			cout<<endl;
		}
		
		//Get the length of two nodes
		cout<<"Now we calculate the length of two given nodes.";
		cout<<"Please input the source node:";
		cin>>s;
		cout<<"Please input the destination node:";
		cin>>d;
		t.Dijkstra(t,s,d,0);

		
		
		
		
		//Dijkstra
		cout<<"Now display the shortest path"<<endl<<" using Dijkstra algorithm. ";
		cout<<"Please input the source node:";
		cin>>s;
	t.Dijkstra(t,s,d,1);
 
	return 0;
}