Djikstra Algo Ouput Problem

[L10nelMessi]

Hi,
I am currently doing a project on Graphs and its almost complete. Whenever i enter a char other than A it gives me errors. I still can't figure out what causes it?

Here's the matrix for the code

0 5 5 0 0 0 0 0 0 0 0 0 0 0 0 0
5 0 4 3 0 0 0 0 0 0 0 0 0 0 0 0
5 4 0 7 7 0 0 8 0 0 0 0 0 0 0 0
0 3 7 0 0 0 0 11 0 0 16 13 14 0 0 0
0 0 7 0 0 4 0 5 0 0 0 0 0 0 0 0
0 0 0 0 4 0 9 0 0 0 0 0 0 0 0 0
0 0 0 0 0 9 0 0 0 0 0 0 0 12 0 0
0 0 8 11 5 0 0 0 3 0 0 0 0 0 0 0
0 0 0 0 0 0 0 3 0 4 0 0 0 0 0 0
0 0 0 0 0 0 0 0 4 0 0 0 0 3 0 8
0 0 0 16 0 0 0 0 0 0 0 5 0 7 0 4
0 0 0 13 0 0 0 0 0 0 5 0 9 0 4 0
0 0 0 14 0 0 0 0 0 0 0 9 0 0 5 0
0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 7
0 0 0 0 0 0 0 0 0 0 0 4 5 0 0 0
0 0 0 0 0 0 0 0 0 8 4 0 0 7 0 0

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <sstream>
#include<queue>

using namespace std;

// Number of vertices 
// in the graph
#define V 16
// A utility function to find the 
// vertex with minimum distance
// value, from the set of vertices
// not yet included in shortest
// path tree

int minDistance(int dist[], bool sptSet[])
{
	// Initialize min value
	int min = INT_MAX, min_index;
	for (int v = 0; v < V; v++)
	{
		if (sptSet[v] == false && dist[v] <= min)
			min = dist[v], min_index = v;
	}
	return min_index;
}

// Function to print shortest // path from source to j // using parent array
void printPath(int parent[], int j)
{
	// Base Case : If j is source

	if (parent[j] == -1)
		return;

	printPath(parent, parent[j]);
	int src = 0;
	char x;

	if (j == 0)
	{
		x = 'A';
	}
	else if (j == 1)
	{
		x = 'B';
	}
	else if (j == 2)
	{
		x = 'C';
	}
	else if (j == 3)
	{
		x = 'D';
	}
	else if (j == 4)
	{
		x = 'E';
	}
	else if (j == 5)
	{
		x = 'F';
	}
	else if (j == 6)
	{
		x = 'G';
	}
	else if (j == 7)
	{
		x = 'H';
	}
	else if (j == 8)
	{
		x = 'I';
	}
	else if (j == 9)
	{
		x = 'J';
	}
	else if (j == 10)
	{
		x = 'K';
	}
	else if (j == 11)
	{
		x = 'L';
	}
	else if (j == 12)
	{
		x = 'M';
	}
	else if (j == 13)
	{
		x = 'N';
	}
	else if (j == 14)
	{
		x = 'O';
	}
	else if (j == 15)
	{
		x = 'P';
	}
	cout << x;

}

// A utility function to print  // the constructed distance // array

void printSolution(int dist[], int n, int parent[])
{
	int src = 0;
	char x;
	if (src == 0)
	{
		x = 'A';
	}
	else if (src == 1)
	{
		x = 'B';
	}
	else if (src == 2)
	{
		x = 'C';
	}
	else if (src == 3)
	{
		x = 'D';
	}
	else if (src == 4)
	{
		x = 'E';
	}
	else if (src == 5)
	{
		x = 'F';
	}
	else if (src == 6)
	{
		x = 'G';
	}
	else if (src == 7)
	{
		x = 'H';
	}
	else if (src == 8)
	{
		x = 'I';
	}
	else if (src == 9)
	{
		x = 'J';
	}
	else if (src == 10)
	{
		x = 'K';
	}
	else if (src == 11)
	{
		x = 'L';
	}
	else if (src == 12)
	{
		x = 'M';
	}
	else if (src == 13)
	{
		x = 'N';
	}
	else if (src == 14)
	{
		x = 'O';
	}
	else if (src == 15)
	{
		x = 'P';
	}

	cout << "Vertex		Distance			Path \n";

	for (int i = 0; i < V; i++)
	{
		int sr = i;
		char x1;

		if (sr == 0)
		{
			x1 = 'A';
		}
		else if (sr == 1)
		{
			x1 = 'B';
		}
		else if (sr == 2)
		{
			x1 = 'C';
		}
		else if (sr == 3)
		{
			x1 = 'D';
		}
		else if (sr == 4)
		{
			x1 = 'E';
		}
		else if (sr == 5)
		{
			x1 = 'F';
		}
		else if (sr == 6)
		{
			x1 = 'G';
		}
		else if (sr == 7)
		{
			x1 = 'H';
		}
		else if (sr == 8)
		{
			x1 = 'I';
		}
		else if (sr == 9)
		{
			x1 = 'J';
		}
		else if (sr == 10)
		{
			x1 = 'K';
		}
		else if (sr == 11)
		{
			x1 = 'L';
		}
		else if (sr == 12)
		{
			x1 = 'M';
		}
		else if (sr == 13)
		{
			x1 = 'N';
		}
		else if (sr == 14)
		{
			x1 = 'O';
		}
		else if (sr == 15)
		{
			x1 = 'P';
		}

		cout << "\n" << x << "->" << x1 << "		" << dist[i] << "-------------------------------->" << x;
		printPath(parent, i);
		cout << endl;

	}

}

// Funtion that implements Dijkstra's
// single source shortest path
// algorithm for a graph represented
// using adjacency matrix representation

void dijkstra(int graph[V][V], int src)
{
	// The output array. dist[i]  will hold the shortest distance from src to i
	int dist[V];
	// sptSet[i] will true if vertex  i is included / in shortest path tree or shortest distance  from src to i is finalized
	bool sptSet[V];
	// Parent array to store  shortest path tree
	int parent[V];
	// Initialize all distances as   INFINITE and stpSet[] as false

	for (int i = 0; i < V; i++)
	{
		parent[0] = -1;
		dist[i] = INT_MAX;
		sptSet[i] = false;
	}

	// Distance of source vertex  from itself is always 0

	dist[src] = 0;

	// Find shortest path  for all vertices
	for (int count = 0; count < V - 1; count++)
	{
		// Pick the minimum distance vertex from the set of vertices not yet processed.   u is always equal to src  in first iteration.
		int u = minDistance(dist, sptSet);
		// Mark the picked vertex  as processed
		sptSet[u] = true;
		// Update dist value of the   adjacent vertices of the  picked vertex.

		for (int v = 0; v < V; v++)
		{
			// Update dist[v] only if is
			// not in sptSet, there is
			// an edge from u to v, and 
			// total weight of path from
			// src to v through u is smaller  than current value of dist[v]

			if (!sptSet[v] && graph[u][v] && dist[u] + graph[u][v] < dist[v])
			{
				parent[v] = u;
				dist[v] = dist[u] + graph[u][v];
			}
		}

	}
	// print the constructed  distance array
	printSolution(dist, V, parent);
}

// Driver Code
int main()
{	
	cout << "Shown below is the Matrix" << endl;
	cout << endl;
	cout << "------------------------------------------------------" << endl;
	//  Let us create the example
	// graph discussed above
	//  int graph[V][V] =
	//{
	// {0,5,5,0,0,0,0,0,0,0,0,0,0,0,0,0},
	// {5,0,4,3,0,0,0,0,0,0,0,0,0,0,0,0},
	// {5,  4,  0 , 7 , 7 , 0  ,0,  8,  0 , 0 , 0,  0,  0,  0  ,0,  0},
	// {0,  3,  7 , 0  ,0 , 0  ,0,  11, 0 , 0 , 16, 13, 14, 0  ,0,  0},
	// {0,  0,  7  ,0  ,0 , 4  ,0,  5,  0 , 0 , 0 , 0,  0 , 0  ,0,  0},
	// {0,  0,  0 , 0  ,4 , 0  ,9,  0,  0 , 0 , 0 , 0,  0 , 0  ,0,  0},
	// {0,  0,  0  ,0  ,0 , 9  ,0,  0,  0 , 0 , 0 , 0,  0 , 12, 0,  0},
	// {0,  0,  8 , 11 ,5 , 0  ,0,  0,  3 , 0 , 0 , 0,  0 , 0 , 0,  0},
	// {0,  0,  0  ,0  ,0 , 0  ,0,  3,  0 , 4 , 0 , 0,  0 , 0 , 0,  0},
	// {0,  0,  0  ,0  ,0 , 0  ,0,  0,  4 , 0 , 0 , 0,  0 , 3 , 0,  8},
	// {0,  0,  0  ,16 ,0 , 0  ,0,  0,  0 , 0 , 0 , 5,  0 , 7 , 0,  4},
	// {0,  0,  0  ,13 ,0 , 0  ,0,  0,  0 , 0 , 5 , 0,  9 , 0 , 4,  0},
	// {0,  0,  0  ,14, 0 , 0  ,0,  0,  0 , 0 , 0 , 9,  0 , 0 , 5,  0},
	// {0,  0,  0  ,0 , 0 , 0  ,0,  0,  0 , 3 , 0 , 0,  0 , 0 , 0,  7},
	// {0,  0,  0  ,0,  0 , 0  ,0,  0,  0 , 0 ,0  ,4,  5  ,0 , 0 , 0},
	// {0,  0,  0  ,0  ,0 , 0 , 0,  0,  0 , 8 ,4  ,0 , 0  ,7,  0 , 0}
	// };
	int rows = 16;
	int columns = 16;
	int graph[V][V];
	for (int i = 0; i<rows; i++)
	{
		for (int j = 0; j<columns; j++)
		{
			graph[i][j] = NULL;
		}
	}

	ifstream ifile;
	ifile.open("Matrix.txt");
	while (!ifile.eof())
	{
		for (int i = 0; i < rows; i++)
		{
			for (int j = 0; j < columns; j++)
			{
				ifile >> graph[i][j];
			}
		}
	}
	for (int i = 0; i < rows; i++)
	{
		for (int j = 0; j < columns; j++)
		{
			cout << graph[i][j] << "  ";
		}
		cout << endl;
	}
	cout << "----------------------------------------------------" << endl;
	int x = 0;
	char source = NULL;
	cout << "Enter a source from A-P: " << endl;
	cin >> source;
	x = source - 65;
	dijkstra(graph, 0);
	system("pause");
	return 0;
}

[seeplus]

You can simplify some of the code:

void printPath(int parent[], int j)
{
	// Base Case : If j is source

	if (parent[j] != -1) {
		printPath(parent, parent[j]);

		//const char x = 'A' + j;
		//const int ascii = x - 'A';
		//cout << ascii;
		cout << j;
	}
}

void printSolution(int dist[], int n, int parent[])
{
	const int src = 0;
	const char x = 'A' + src;	// x is always A as src is always 0 !!!

	cout << "Vertex		Distance			Path \n";

	for (int i = 0; i < V; ++i) {
		const char x1 = 'A' + i;

		cout << "\n" << x << "->" << x1 << "		" << dist[src] << "-------------------------------->" << x;
		printPath(parent, src);
		cout << endl;
	}
}