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

class RouteFinder	
{
private:													
	int graph[10][10],spoint,dpoint;
	int list1[10], list2[10], offset[10];
	int path[10];
	char start,destination;
	
public:														
	void openfile(void);
	void startend(void);
	void route(void);
	void displayRoute(void);
	RouteFinder(void);
	~RouteFinder(void);
};

void RouteFinder :: openfile(void)
{
	fstream graphfile;
	int dis;
	char in1, in2, comma;												
	graphfile.open("graph.dat",ios::in);					

	do														
	{
		graphfile>>in1;										
		graphfile>>comma;									
		graphfile>>in2;										
		graphfile>>comma;									
		graphfile>>dis;										

		graph[in1-65][in2-65]=dis;							
		graph[in2-65][in1-65]=dis;							
	}
	while (!graphfile.eof());								

	graphfile.close();										
}

void RouteFinder :: startend(void)
{
	cout<< "Please enter the node you would like to start at (A - J): ";
	cin>> start;											
	start =  toupper(start);
	do
	{
		if (start >= 'A' && start <= 'J')
			spoint= start - 65;								
		else
		{
			cout<< "Please enter the node you would like to start at (A - J): ";
			cin>> start;
		}
	}
	while (!(start >= 'A' && start <= 'J'));

	cout<< "And the node you would like to reach (A - J): ";
	cin>> destination;												
	destination =  toupper(destination);
	do
	{
		if (destination >= 'A' && destination <= 'J')
			dpoint= destination - 65;								
		else
		{
			cout<< "Please enter the node you would like to start at (A - J): ";
			cin>> start;
		}
	}
	while (!(destination >= 'A' && destination <= 'J'));	
}

void RouteFinder :: route(void)
{
	
	int loc, pos = 1;
	int i,j;
	for (i=0; i<10; i++)
	{
		path[i] = -1;
	}
	list1[0] = spoint;
	for (i=0; i<10; i++)
	{
		if (i != spoint)
		{
			list2[i] = i;
		}
		else
			list2[i] = 100;
	}
	offset[0] = 0;
	do
	{
		int min = 10000;
		for (j=0; j<pos; j++)
		{
			for (i=0; i<10; i++)
			{
				if (list2[i] < 100)
				{
					if (graph[list1[j]][i] >0 && (graph[list1[j]][i] + offset[j]) < min)
					{
						min = graph[list1[j]][i] + offset[j];
						loc = i;
					}
				}
			}
		}
		list1[pos] = loc;
		offset[pos] = min;
		list2[loc] = 100;
		pos++;
	}
	while( pos < 10);
}
void RouteFinder :: displayRoute(void)
{
	int pos;
	int flag;
	int count;
	int i;
	cout << "start node : " << start << endl;
	cout << "end node : " << destination << endl;
	i=0;
	pos = 0;
	do
	{
		pos++;
	}
	while ((destination-65) != list1[pos]);
	cout << "shortest distance between nodes : " << offset[pos] << endl;
	count = 0;
	do
	{
		flag = 0;
		for (i=pos; i>=0; i--)
		{
			if (offset[pos] - offset[i] == graph[list1[pos]][list1[i]] && graph[list1[pos]][list1[i]] != 0)
			{
				path[count] = list1[i];
				count++;
				pos = i;
				flag = 1;
			}
			if (flag == 1) break;
		}
	}
	while (pos > 0);
	cout << "Made up of  the following steps "<< endl;
	cout << "Starting at " << start;
	for (i=count-2; i>=0; i--)
	{
		cout << " to " << (char)(path[i]+65);
		cout << " of distance " << graph[path[i+1]][path[i]] << endl;
		cout << "Then from " << (char)(path[i]+65);
	}
	cout << " to " << destination;
	cout << " of distance " << graph[path[0]][destination - 65] << endl;
}

RouteFinder :: RouteFinder(void)										
{
	int i,j;
	for(i=0;i<10;i++)										
	{
		graph[i][i]=0;										
		for(j=0;j<10;j++)									
		{
			if(i!=j)										
			{
				graph[j][i]=10000;							
				graph[i][j]=10000;							
			}
		}
	}
}

RouteFinder :: ~RouteFinder (void)									
{
}

void main()
{
	RouteFinder grid;	
	char reply;
	grid.openfile();
	do
	{									
		grid.startend();									
		grid.route();										
		grid.displayRoute();
		cout << endl;
		cout << "Do you want to calculate another route (y/n) ? ";
		cin >> reply;
	}
	while ((reply == 'y') || (reply == 'Y'));
}