//**************************************************************************
#include <iostream.h>
#include <limits.h>
#include <string.h>
#include "vertex.h"
#include "priqueue.h"
#include "adjlist.h"
#include "hash.h"
#include "dijkstra.h"
//**************************************************************************
// Implementation of dijkstra's algorithm, accepts graph G as input
// Returns array of vertices V forming shortest path edges
void dijkstra(int source, AdjList& G, Vertex *V, HashTable& T, int print_heap)
{
int i;
int num_vert = G.no_of_verts();
PriQueue Q(num_vert); // Declares a Priority queue

G.setDist(source,0);
G.setKnown(source,1);
// Initializes queue for edges from source to all others
Vertex *vert = G.start(source);
while (vert)
	{
	 Vertex adder(vert->name,source,vert->distance);
	 Q.Insert(adder);
	 G.setDist(vert->name,vert->distance);
	 vert = vert->next;
	}
// INT_MAX is used for no edge between two vertices 
for (i=1;i<=num_vert;i++)
	{
	 if (i != source && !Q.IsThere(i))
	 	{
 	 	 Vertex adder(i,source,INT_MAX);
 	 	 Q.Insert(adder);
		}
	}

for (i=1;i<=num_vert-1;i++)
	{
	 if (print_heap) Print_Heap(Q,T);

	 Vertex min = Q.Delete_Min(); 	// Removes the smallest edge
	 V[min.name-1] = min; 		// And adds it to array V
	 V[min.name-1].distance = G.distance(min.name)-G.distance(min.parent);

	 G.setKnown(min.name,1);
	 Vertex *vert = G.start(min.name);
	 if (min.distance != INT_MAX)
	   while (vert)
	 	{
	 	 if (!G.Known(vert->name))
		 	{
	 	 	 int dist = vert->distance;
			 int new_weight = min.distance + dist;
	 	 	 if (new_weight < G.distance(vert->name))
			 	{
				 G.setDist(vert->name,new_weight);
				 Q.Decrease_Key(vert->name,new_weight,min.name);
				}
			}
		 vert = vert->next;
		}
	}

if (print_heap) cout << endl;
}
//**************************************************************************
// Prints the Path from "source" to "dest"
void Print_Path (int source, int dest, Vertex *V, AdjList& G, HashTable& T)
{
cout << endl;

if (dest == source) 
	{
	 cout 	<< '\t' << T.name_of(dest) << " is the source !!" << endl 
	 	<< endl;
	 return;
	}

int total = 0;
Print_Path_Rec(source,dest,V,G,T,&total);

if (total != INT_MAX) 
	cout << '\t' << "total cost: " << total << endl;

cout << endl;
}
//**************************************************************************
// Recursive routine called by Print_Path
void Print_Path_Rec (int source, int dest, Vertex *V, AdjList& G, 
		HashTable& T, int *total)
{
int dist = V[dest-1].distance;

if (dist == INT_MAX) 
	{
	 cout << '\t' << "Cannot get to " << T.name_of(dest) << "." << endl;
	 *total = dist;
	 return;
	}

if (V[dest-1].parent != source)
	Print_Path_Rec(source,V[dest-1].parent,V,G,T,total);

cout 	<< '\t' << T.name_of(V[dest-1].parent) << " -> " 
	<< T.name_of(V[dest-1].name) 
	<< " " << dist << endl;

*total += dist;
return;
}
//**************************************************************************
void Print_Dijkstra (int source, Vertex *V, HashTable& T)
{
cout << "Shortest paths computed by Dijkstra's algorithm with focus \""
	<< T.name_of(source) << "\" ->" << endl;
cout << endl;
for (int i=0;i<T.nodes_of();i++)
	if (i != (source-1))
		{
		 cout 	<< '\t' << T.name_of(V[i].parent) << " to " 
		 	<< T.name_of(V[i].name) << " -> ";
		 if (V[i].distance != INT_MAX)
			cout << V[i].distance << endl;
		 else
		 	cout << "Unreachable" << endl;
		}
cout << endl;
}
//**************************************************************************
void Print_Heap (PriQueue& Q, HashTable& T)
{
cout << "Heap[" << Q.getSize() << "] -> ";
for (int i=1;i<=Q.getSize();i++)
	{
	 cout << "(" << T.name_of(Q.getName(i)) << ",";
	 if (Q.getWeight(i) != INT_MAX)
		 cout << Q.getWeight(i);
	 else
	 	 cout << "Inf";
	 cout << ") ";
	}
cout << endl;
}
//**************************************************************************