Thread: Dijkstra algorithm

Hi,
I found some material about Dijkstra algorithm and studying it.
I manage to make something that is working,but still have one serious problem.
This code that I found and modified works for finding minimal cost, but how can I determinate route which provides minimal cost.
I must admit that I didn't fully understand this code(those nested loops uhhh).
I tried to define an array in which it would be stored index numbers, for example if
path from node 0 to to node 3 is minimal cost when traverse over node 2 and , then array would be:
0 2 4 3.
There are two problems with this approach:
first how can I know how many nodes are traversed to achive minimal cost to define size of an array?
second how can I fill this array?
Please help!
Thanks in advance!

Code:

#include <iostream>
using namespace std;

class Graph
{
	int** adj_matrix;
	int** shortest_path_matrix;
	int *array;
	int size;
	void init_adj_matrix();
	void init_shortest_path_matrix();
	void load_adj_matrix();
	void load_shortest_path_matrix(int,int);
public:
	Graph(int);
	~Graph();
	void setup_matrix();
	int find_cost_of_shortest_path(int,int);
	void show()
	{
		for(int i=0;i<size;i++,cout<<endl)
			for(int j=0;j<size;j++)
				cout<<" "<<adj_matrix[i][j];
	}
	void show_array()
	{
		for(int i=0;i<size;i++)
		{
			cout<<array[i]<<" ";
		}
	}
	
};

Graph::Graph(int siz):size(siz)
{
	array=new int[size];
	adj_matrix=new int* [size];
	shortest_path_matrix=new int* [size];
	for(int i=0;i<size;i++)
	{
		adj_matrix[i]=new int[size];
		shortest_path_matrix[i]=new int[size];
		array[i]=0;
	}	
	setup_matrix();
}
Graph::~Graph()
{
	for(int i=0;i<size;i++)
	{
		delete adj_matrix[i];
		delete shortest_path_matrix[i];
	}
	delete adj_matrix;
	delete shortest_path_matrix;
	delete [] array;
}
void Graph::setup_matrix()
{
	init_adj_matrix();
	load_adj_matrix();
	init_shortest_path_matrix();
	
	
}
void Graph::init_adj_matrix()
{
	for(int i=0;i<size;i++)	
		for(int j=0;j<size;j++)
			adj_matrix[i][j]=0;
}
void Graph::init_shortest_path_matrix()
{
	for(int i=0;i<size;i++)	
		for(int j=0;j<size;j++)
			shortest_path_matrix[i][j]=adj_matrix[i][j];
}
void Graph::load_adj_matrix()
{
	int i,j,cost;
	char answer;
	const int beskonacno=9999;
	for(i=0;i<size;i++)
	{
		for(j=0;j<size;j++)
		{
			
			
			if((i!=j)&& (adj_matrix[i][j]==0)){
			//matrix bliskosti se ucitava od strane korisnika
			cout<<"Is there direct connection between node "<<i<<" and node "<<j<<" ?"<<endl;
			cout<<"Your answer (y for yes any other for no): ";
			cin>>answer;
			if((answer=='y')||(answer=='Y'))
			{
				cout<<"Enter cost: ";
				cin>>cost;
				adj_matrix[i][j]=adj_matrix[j][i]=cost;
			}
			else
				adj_matrix[i][j]=adj_matrix[j][i]=beskonacno;
			}
		}
	}

}

void Graph::load_shortest_path_matrix(int poc,int kraj)
{
	int brojac=0;
	const int beskonacno=9999;
	for(int i=0;i<size;i++)
	{
		for(int j=0;j<size;j++)
		{
			for(int k=0;k<size;k++)
			{
				if(shortest_path_matrix[i][k]>0)
				{
					if((shortest_path_matrix[j][k]==beskonacno)||
						(shortest_path_matrix[i][k]+shortest_path_matrix[i][j]
						<shortest_path_matrix[j][k]))
						shortest_path_matrix[j][k]=shortest_path_matrix[i][k]+shortest_path_matrix[j][i];
				}
			}
		}
	}
}
int Graph::find_cost_of_shortest_path(int i,int j)
{
	load_shortest_path_matrix(i,j);
	return shortest_path_matrix[i][j];
}
int main()
{
	int number_of_nodes,source,destination,cost;
	cout<<"Enter number of nodes: ";
	
	cin>>number_of_nodes;
	
	Graph graph_obj(number_of_nodes);
	graph_obj.show();
	
	cout<<"Enter source index: ";
	cin>>source;
	//for the moment forget about weak checking of cin
	if(source>number_of_nodes-1)
	{
		cout<<"Error index"<<endl;
	}
	cout<<"Enter destination index: ";
	cin>>destination; 
	if(destination>number_of_nodes-1)
	{
		cout<<"Error index!"<<endl;
	}
	cost =graph_obj.find_cost_of_shortest_path(source,destination);

	cout<<"Shortest path between node "<<source<<" and node "<<destination<<
		" costs "<<cost<<"!"<<endl;
	//graph_obj.show_array();

	return 0;
}

This code is a modification that I find in C++ Unleashed.
axon suggested something

Code:

printPath( Vertex v )
{
     if( v.path != NOT_A_VERTEX )
     {
             printPath( v.path );
             cout << " to ";
      }
       cout << v;
}

but that doesn't help me much.
I would appreciate if someone has any example of implementation
to show.

Is this question really that hard?