1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

shortest path algorithm

Discussion in 'C' started by totototo, Jul 18, 2008.

  1. totototo

    totototo New Member

    Joined:
    Jul 18, 2008
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    0
    Hi,
    I am trying to write a code to compute the shortest path between any two nodes in a graph. I wrote the code but the problem is that it is very slow when I run it for let us say 65 nodes (for every pair of nodes, the algorithm computes the shortest path). I saw on the internet that there are ways to do so, but they are very complicated codes. However, in my code, I use the Priority Queue built-in package so that I quickly extract the smallest value. Could you please help me in making the code fast?

    An example of a graph:

    1--(distance = 9)---> 2 ---(distance = 12)------> 3
    | ^
    | (distance = 10) | (distance=1)
    V |
    4 --------(distance = 2)------------------------------> 5

    The path from node 1 to node 3: 1,4,5,3 is the shortest because 13 < 21

    Code:
    double Spanner::Find_distance_UDG(int start_vertex,int end_vertex) 
    { 
    	Thread a;// Just assume that you only need two things from this class index(the label of a node), and dist (the distance between a node and its neighbor)
    	priority_queue<Thread> QQ1;
    	queue<Thread> Q1;
    	int UNVISITED = 0,VISITED=2;//,UNDEFINED = -1;
    	init(); //it makes all the nodes unvisited
    	int v, w;
     	double distance = 0;
    	double final_distance = 100000000;
    	double power_distance = 0; // ignore this variable whenever you find it in the code
    	a.index = start_vertex;
    	a.dist = distance;
    	a.dist_power = 0.0;  // ignore this variable whenever you find it in the code
    	QQ1.push(a);
    	setMark(start_vertex, VISITED); //mark this node as a visited node
    	while (QQ1.size()!= 0) 
    	{ 
    		v=QQ1.top().index;
    		distance = QQ1.top().dist;
    		power_distance = QQ1.top().dist_power; 
    		QQ1.pop();
    	
    		if ( v == end_vertex )
    		{
    		final_distance = distance;
    		least_power = power_distance; 
    		return final_distance;
    		}
    	else
    	  { 
    		for (int k  = 0; k < nodes[v].nbrcnt2; k++ )
    		{
    			w = nodes[v].nbrlist2[k]; //Each node v has some neighbors in its list nbrlist2
    			if (getMark(w) == UNVISITED) //To see if this node has not been visited before
    			{   
    				setMark(w, VISITED); // Change the node status to visited
    				a.index = w;
    				a.dist = distance+ dis(v,w);
    				a.dist_power = power_distance + (pow(dis(v,w),2)*1.000000);
    				QQ1.push(a);
    				
    			}
    			else
    			{
    				int size = QQ1.size();
    				int flag = 0; //This flag is used to see if the node is already in the priority queue
    				while(size !=0 && flag == 0)
    				{
    				  Thread b;
    				  b.index = QQ1.top().index;
    				  b.dist = QQ1.top().dist;
    				  b.dist_power = QQ1.top().dist_power;
    				  QQ1.pop();
    				  if(b.index == w)
    				  {   flag = 1;
    					  if(b.dist > (distance + dis(v,w)))
    					   {  b.dist = (distance + dis(v,w));
    					      b.dist_power = power_distance + (pow(dis(v,w),2)*1.000000);
    					   }
    				  }
    				  size--;
    				  Q1.push(b);
    				  
    				}
    				while(Q1.size()!=0)
    				{
    				  Thread b;
    				  b.index = Q1.front().index;
    				  b.dist = Q1.front().dist;
    				  b.dist_power = Q1.front().dist_power;
    				  Q1.pop();
    				  QQ1.push(b);
    				}
    			}
    			
    		}//for (int k  = 0; k < nodes[v].nbrcnt2; k++ )			
    	  
    	  }//else
    
    
    
    	}
    	
       if( final_distance == 100000000) //This is just for testing purposes, however it did not reach it before
            final_distance = 0;
    	return final_distance;
    	
    
    }
    
    
     

Share This Page