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

#include <queue>
#include <vector>
#include <deque>
#include <list>

using namespace std;

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

struct struct_edge {
	int dest;	//destination
	int weight;
};

struct struct_Node_ShortestPath {
	int shortestDistance;
	int prevPath;
	int prevPath_weight;
};

vector<string> split(const string& s, char delim) {
	vector<string> result;
	stringstream ss(s);
	string item;

	while (getline(ss, item, delim)) {
		result.push_back(item);
	}

	return result;
}

int main()
{
	//Initialize graph's nodes
	struct list<struct_edge> Nodes_Edges_records[1000];	// create list array to save nodes' edges records from file

	//Read graph's nodes connection from a file
	std::ifstream inputfile("graph3.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);
			}


			struct_edge tmp_node_edge;
			int tmpEdgesCount = 0;
			list<struct_edge> tmp_List;
			for (auto i : vectorStr)
			{
				if (tmpEdgesCount % 2 == 0)
					tmp_node_edge.dest = stoi(i);
				else
				{
					tmp_node_edge.weight = stoi(i);
					tmp_List.push_back(tmp_node_edge);
					
				}

				tmpEdgesCount++;
			}

			Nodes_Edges_records[node_count] = tmp_List;
			node_count++;
		}
		inputfile.close();
	}

	std::vector<struct_Node_ShortestPath> graph_ShortestPath(node_count);
	for (int i = 0; i < node_count; i++) {
		if (i == 0)
			graph_ShortestPath[i].shortestDistance = 0;
		else
			graph_ShortestPath[i].shortestDistance = INFINITY;

		graph_ShortestPath[i].prevPath = -1;
		graph_ShortestPath[i].prevPath_weight = -1;
	}
	cout << "Shortest Path 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 (struct_edge tmpNodeEdge : Nodes_Edges_records[top]) {
				sum = graph_ShortestPath[top].shortestDistance + tmpNodeEdge.weight;
				if (graph_ShortestPath[tmpNodeEdge.dest].shortestDistance > sum) {
					graph_ShortestPath[tmpNodeEdge.dest].shortestDistance = sum;
					graph_ShortestPath[tmpNodeEdge.dest].prevPath = top;
					graph_ShortestPath[tmpNodeEdge.dest].prevPath_weight = tmpNodeEdge.weight;

					q.push(tmpNodeEdge.dest);
				}
			}
		}
	}
	cout << "Finish Shortest Path derivation" << endl;

	//Print shortest path to all nodes
	cout << endl;
	for (int i = 0; i < node_count; i++) {
		if (graph_ShortestPath[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 = graph_ShortestPath[i].prevPath;
			while (preRoute != -1) {
				cout << preRoute << " --> ";
				preRoute = graph_ShortestPath[preRoute].prevPath;
			}
			cout << "End\n";
		}

		cout << "Shortest distance is " << graph_ShortestPath[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 << graph_ShortestPath[i].prevPath << " " << graph_ShortestPath[i].prevPath_weight << "\n";
	}
	myfile.close();

	return 0;
}