Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/forums/c/)
-   -   shortest path algorithm (http://www.go4expert.com/forums/shortest-path-algorithm-t12237/)

totototo 19Jul2008 03:16

shortest path algorithm
 
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: C++

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;
   

}



All times are GMT +5.5. The time now is 05:59.