# Dijkstra algorithm

• 04-28-2004
Micko
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?

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; }```
• 04-28-2004
axon
you could use something like this...

Code:

```printPath( Vertex v ) {     if( v.path != NOT_A_VERTEX )     {             printPath( v.path );             cout << " to ";       }       cout << v; }```
this is with a somewhat different class design though. Similar print algo worked fine for me.
• 04-28-2004
Micko
I really didn't see this realization.
Could you be more specific or paste your solution?
Since this realization works for cost. Information on traverse order is hidden in this code.
I cannot figure out how I can extract it. Or maybe this kind of solution is not for that purpose?
• 04-29-2004
XSquared
What you're gonna need to do is to keep an array which stores the parent of each node on the graph. That's not actually Dijkstra's algorithm by the way, but I can't remember the name of the algorithm you're using.
• 04-29-2004
Micko
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.
• 04-30-2004
Micko
Is this question really that hard?