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

---

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.

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?

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.

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?