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; }