/*This is a complete and correctly functioning 
  Shortest Path algorithm in C++ using Dijkstra's Algorithm.
  For information on how Dijkstra's Algorithm works:
  Visit the following link: https://w...content-available-to-author-only...e.com/watch?v=WN3Rb9wVYDY */
  /*This Program was designed and constructed by (Mazhar Mustapha)*/
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
using namespace std;

struct node { // Struct is for node or letter in the diagram, each node has a value attached to it according to Dijkstra's algorithm
	char symbol; 
	int v;
}; 
struct path { // Struct is for path of each edge. Each edge has a specific length
	string movement;
	int L;
};
void display(node *, int, path *, int, char, char); // Neatly display results of input
void test_path(char, char, path *, node *, int); // The actual process of testing and finding the shortest path
int find_path_sub(path *, char, int); // Find subscript for path location.
int find_path_sub_two(char); // Find subscript using last character in a string.
int find_path_sub_third(char); // Find subscript using first character in a string.
string find_path(char, node *, int); // Returns the deciphered string which had lowest path value.
int main()
{
	int x; char s, e;
	node *ptrN; path *ptrP;
	cout << "# of vertices: "; cin >> x; // Number of nodes
	const int n = x;
	ptrN = new node[n]; x = 97;
	for (int i = 0; i < n; i++)
	{
		ptrN[i].symbol = x; //Assigns a letter starting 'a' and increments to the defined number of n.
		x++;
	}
	cout << "Enter start and end: "; cin >> s >> e; // Start and Ending nodes, defined by its letter.
	for (int i = 0; i < n; i++)
	{
		if (s == ptrN[i].symbol)
			ptrN[i].v = 0; // Set starting node value to 0
		else
			ptrN[i].v = 9999999; // Set all other nodes to INFINITE.
	}
	cout << "Enter number of edges: "; cin >> x; // Number of connections
	const int m = x;
	ptrP = new path[m]; // Allocate number of paths needed.
	for (int i = 0; i < m; i++)
	{
		cin.ignore(20, '\n');
		cout << "[PATH] ";
		if (i == 0)
		{
			cout << "!ALPHABETICAL ORDER {EX. ab = (a to b)}"; // It is ESSENTIAL that the inputs here are entered in Alphebetical order, otherwise there will be errors.
		}
		cout << "| Edge " << (i + 1) << ": ";
		getline(cin, ptrP[i].movement);
		cout << "Length: "; cin >> ptrP[i].L;
	}
	display(ptrN, n, ptrP, m, s, e);
	test_path(s, e, ptrP, ptrN, m);
	delete[] ptrP;
	delete[] ptrN;
	system("PAUSE");
	return 0;
}
void display(node *PtrN, int n, path *PtrP, int m, char start, char end)
{
	cout << "Vertices: ";
	for (int i = 0; i < n; i++)
	{
		cout << PtrN[i].symbol << " ";
	}
	cout << endl << "Start: " << start << endl << "End: " << end << endl;
	cout << "-----PATHS-----\n";
	for (int i = 0; i < m; i++)
	{
		cout << PtrP[i].movement;
		cout << " - [L] = " << PtrP[i].L;
		cout << endl;
	}
}
void test_path(char start, char end, path *ptr, node *Ptr, int m)
{
	vector<int> record;
	vector<string> final;
	char begin = start; 
	int x, y, z, L;
	bool initial = true;
	string t, fpath;
	while (begin != end)
	{
		if(initial)
			x = find_path_sub(ptr, begin, m);
		initial = false;
		t = ptr[x].movement; // Set t with first path for while loop to activate.
		while (t[0] == begin && x < m)
		{
			y = find_path_sub_two(t[1]);
			z = find_path_sub_third(t[0]);
			Ptr[y].v = ptr[x].L + Ptr[z].v;
			record.push_back(Ptr[y].v);
			x++;
			if (x == m)
				continue;
			t = ptr[x].movement; // test while loop at the beginning.
		}
		if (record.size() != 0) {
			L = record[0];
			for (int i = 0; i < record.size(); i++)
			{
				if (record[i] < L)
					L = record[i];
			}
		}
		fpath = find_path(begin, Ptr, L);
		final.push_back(fpath);
		record.clear(); // Clear record for next loop.
		x = 0; // x equals 0 for safety purposes.
		initial = true; // Initial true for t to contain next path.
		begin = fpath[1]; // Begin ewuals the last character of the string. Example: a to b, now we need to start from b.
	}
	cout << "Final Path: ";
	for (int i = 0; i < final.size(); i++)
	{
		cout << final[i] << " ";
	}
	cout << endl;
}
int find_path_sub(path *ptr, char start, int size)
{
	string temp;
	for (int i = 0; i < size; i++)
	{
		temp = ptr[i].movement;
		if (start == temp[0])
			return i;
	}
}
int find_path_sub_two(char last)
{
	int j = 97;
	char test;
	for (int i = 0; ;i++)
	{
		test = j;
		if (test == last)
			return i;
		j++;
	}
}
int find_path_sub_third(char first)
{
	int j = 97;
	char test;
	for (int i = 0; ;i++)
	{
		test = j;
		if (test == first)
			return i;
		j++;
	}
}
string find_path(char b, node *ptr, int value)
{
	string f = "  ";
	f[0] = b;
	for (int i = 0; ;i++)
	{
		if (value == ptr[i].v)
		{
			f[1] = ptr[i].symbol;
			break;
		}
	}
	return f;
}