#include <stdio.h>
#include <iostream>
#include <string>
#include <sstream>
#include <fstream>
#include <cstring>
#include <climits>

#include <queue>
#include <map>

using namespace std;

#define INFINITY numeric_limits<int>::max( )

struct struct_Node_ShortestPath {
	int shortestDistance;
	int prevPath;
	int prevPath_Weight;
	std::map<int, int> map_Edges;
};

int main()
{
	//Initialize graph's nodes
	std::map<int, struct_Node_ShortestPath> theMap;

	//Read graph's nodes connection from a file
	std::ifstream inputfile("graph1.txt");
	int node_count = 0;
	if (inputfile.is_open())
	{
		//Read from file,  save the nodes' edges record into 'Nodes_Edges_records'
		string sLine;
		while (getline(inputfile, sLine)) {
			vector<string> vectorStr;
			stringstream ss(sLine);
			string item;

			while (getline(ss, item, ' '))
			{
				vectorStr.push_back(item);
			}

			int tmpEdgesCount = 0;
			int tmp_Dest, tmp_Weight;
			struct_Node_ShortestPath tmp_struct_Node;
			tmp_struct_Node.prevPath = -1;
			tmp_struct_Node.prevPath_Weight = -1;
			tmp_struct_Node.shortestDistance = INFINITY;
			for (auto i : vectorStr)
			{
				if (tmpEdgesCount % 2 == 0)
					tmp_Dest = stoi(i);
				else
				{
					tmp_Weight = stoi(i);
					tmp_struct_Node.map_Edges[tmp_Dest] = tmp_Weight;
				}

				tmpEdgesCount++;
			}

			theMap[node_count] = tmp_struct_Node;
			node_count++;
		}
		inputfile.close();
	}

	theMap[0].shortestDistance = 0;
	cout << "Graph initialize completed." << endl;;

	//Shortest Path derivation
	std::priority_queue <int, std::vector<int>, std::greater<int> > q;
	q.push(0);

	int top = -1, sum = 0;
	while (!q.empty()) {
		if (top == q.top())
			q.pop();
		else
		{
			top = q.top();
			q.pop();

			for (std::pair<int, int> tmp_Edges : theMap[top].map_Edges) {
				sum = theMap[top].shortestDistance + tmp_Edges.second;
				if (theMap[tmp_Edges.first].shortestDistance > sum) {
					theMap[tmp_Edges.first].shortestDistance = sum;
					theMap[tmp_Edges.first].prevPath = top;
					theMap[tmp_Edges.first].prevPath_Weight = tmp_Edges.second;

					q.push(tmp_Edges.first);
				}
			}
		}
	}
	cout << "Finish Shortest Path derivation" << endl;

	//Print shortest path to all nodes
	cout << endl;
	for (int i = 0; i < node_count; i++) {
		if (theMap[i].prevPath == -1)
			cout << "Shortest path from node \'0\' to node \'" << i << "\' is not yet being found\n";
		else {
			cout << "Shortest path from node \'0\' to node \'" << i << "\':\n"
				<< i << " --> ";
			int preRoute = theMap[i].prevPath;
			while (preRoute != -1) {
				cout << preRoute << " --> ";
				preRoute = theMap[preRoute].prevPath;
			}
			cout << "End\n";
		}

		cout << "Shortest distance is " << theMap[i].shortestDistance << "\n\n";
	}
	cout << endl;

	//Save Open Shortest Path First (OSPF) graph into file 'OSPF_info.txt'
	ofstream myfile;
	myfile.open("OSPF_info.txt");
	for (int i = 0; i < node_count; i++) {
		myfile << theMap[i].prevPath << " " << theMap[i].prevPath_Weight << "\n";
	}
	myfile.close();

	return 0;
}