Dijkstra algorithm

This is a discussion on Dijkstra algorithm within the C++ Programming forums, part of the General Programming Boards category; Hi, I found some material about Dijkstra algorithm and studying it. I manage to make something that is working,but still ...

  1. #1
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712

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

  2. #2
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    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.

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  3. #3
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712
    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?
    Last edited by Micko; 04-29-2004 at 12:40 AM.

  4. #4
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    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.
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  5. #5
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712
    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.

  6. #6
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712
    Is this question really that hard?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 02:30 AM
  2. Dijkstra algorithm problem.
    By apacz in forum C++ Programming
    Replies: 5
    Last Post: 05-28-2005, 05:16 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21