#include <iostream.h>
#include "linked_list.cpp"

// Use the maximum value of int to represent infinity
static const int INFINITY=32767;
// No cost can be negative, so use -1 to represent a non adjacent vertex
static const int NOT_ADJACENT=-1;

void main(void)
{
	int n, counter, counter2, adjacent, leastIndex, currentRow, vertex;
	unsigned cost;
	Linked_List<int> V, remainingV, output;
	int **adjacencyMatrix;
	unsigned **costMatrix;
	
	cout << "Enter number of vertices in the graph" << endl;
	do
	{
		cin >> n;
	} while (n < 1);

	adjacencyMatrix = new int*[n];
	for (counter=0;counter<n;counter++)
		adjacencyMatrix[counter] = new int[n];

	costMatrix = new unsigned*[n+1];
	for (counter=0;counter<=n;counter++)
		costMatrix[counter] = new unsigned[n];

	// Fill up the adjaceny matrix
	for (counter=0; counter < n; counter++)
	{
		// Add this vertex to V, the set of unchosen vertices
		V.add(counter);

		// Set the first row of the cost matrix to infinity
		costMatrix[counter][0] = INFINITY;

		// Clear out values for this row of the adjaceny matrix
		for (counter2=0; counter2 < n; counter2++)
			adjacencyMatrix[counter2][counter]=NOT_ADJACENT;

		while (true)
		{
			// Enter values for the adjaceny matrix
			cout << "Enter an adjacent vertex for vertex " << counter << " or enter -1 to finish with this vertex." << endl;
			do
			{
				cin >> adjacent;
			} while (adjacent < -1 || adjacent >= n);

			if (adjacent == -1)
				break;

			cout << "Enter non-negative cost from vertex " << counter << " to vertex " << adjacent << endl;
			cin >> cost;

			adjacencyMatrix[adjacent][counter]=cost;
		}
	}

	currentRow=1;

	// Set the initial values in the matrix
	// Ask for starting vertex, remove it from V, and add its adjacent values to the cost matrix
	cout << "Enter starting vertex" << endl;
	do
	{
		cin >> vertex;
	} while (vertex < 0 || vertex >= n);

	V.find(vertex);
	V.del();

	// Go through the list of values for the vertex to set the initial values for the cost matrix
	for (counter=0; counter < n; counter++)
	{
		if (adjacencyMatrix[counter][vertex]!=NOT_ADJACENT)
		{
			// Fill the array down
			for (counter2=0; counter2<n; counter2++)
				costMatrix[counter][counter2]=adjacencyMatrix[counter][vertex];
		}
	}

	// Record the first index in the last column of the current row of the cost matrix
	costMatrix[n][0]=vertex;

	// As long as vertices remain then continue
	while (currentRow++ < n)
	{
		// For each value in V, use this as the index in the costMatrix.
		// Among these indices, find the one with the lowest value and assign it to leastIndex

		// Initialize values to find the lowest cost index
		remainingV=V;
		leastIndex=remainingV.pop();
		
		// Find the lowest index among remaining vertices
		while(remainingV.size())
		{
			counter2=remainingV.pop();

			if (costMatrix[counter2][currentRow] < costMatrix[leastIndex][currentRow])
				leastIndex=counter2;
		}

		// Record the chosen index in the last column of the current row of the cost matrix
		costMatrix[n][currentRow]=leastIndex;

		// For each adjacent vertex from the chosen least index, if the cost to reach that vertex
		// is greater than the its cost plus the cost to reach the least index, then replace it with
		// the lesser value
		for (counter=0; counter < n; counter++)
		{
			if (adjacencyMatrix[counter][leastIndex]!=NOT_ADJACENT)
				if (costMatrix[counter][currentRow-1] > costMatrix[leastIndex][currentRow-1] + adjacencyMatrix[counter][leastIndex])
				{
					// Fill down
					for (counter2=currentRow; counter2 < n; counter2++)
						costMatrix[counter][counter2] = costMatrix[leastIndex][currentRow-1] + adjacencyMatrix[counter][leastIndex];
				}
		}

		// remove least index from V
		V.find(leastIndex);
		V.del();
	}

	cout << "Which vertex do you want to find the cost of reaching?" << endl;

	// Loop to input vertices
	while(true)
	{
		do
		{
			cin >> vertex;
		} while (vertex < -1 || vertex >=n);

		if (vertex==-1)
			break;

		cout << "Shortest cost is " << costMatrix[vertex][n-1] << endl;

		currentRow=n-1;
		output.clear();
		output.insert(vertex);

		// Loop to find path
		while (true)
		{
			while (currentRow>0 && costMatrix[vertex][currentRow] == costMatrix[vertex][currentRow-1])
				currentRow--;

			vertex=costMatrix[n][currentRow];
			output.insert(vertex);

			if (currentRow==0)
				break;
		}

		cout << "Path: ";
		while (output.size())
			cout << output.pop() << " ";
		cout << endl;

		cout << "Enter next vertex to find cost of reaching or -1 to stop." << endl;
	}
}