Qquestion on Shortest paths algorithm

Discussion in 'C++' started by costantinos@gmail.com, Jul 26, 2006.

  1. Guest

    Hello. I have implemented the Dijkstra shortest path algorithm, it
    works fine but I have one question on how I can improve something.
    I want to find all the possible shortest paths from a node since there
    is a possibility to exist more than one shortest paths with the same
    distance.

    Does anyone has any idea how this could be done?

    Code


    double Dijkstra_Least_Cost(vector< vector<int> > graph, int
    start_vertex, ofstream &outputfile)
    {
    unsigned int graph_size = graph.size();
    unsigned int D_size = graph_size + 1;
    unsigned int ii, jj, W;
    unsigned int kk = 1;
    double average_distance = 0;
    double temp_d = 0;

    vector <int> distance;
    vector <int> predecessor;
    vector <bool> not_checked;
    map <int,int> intermediate_nodes;
    map<int, int>::const_iterator iter;
    vector< vector<int> > betweennes_l(D_size, vector<int>(D_size,0));


    outputfile <<"Starting from node: " << start_vertex << endl;

    //initialize the vectors
    distance.push_back(0); //in order to start from 1.
    not_checked.push_back(true); //in order to start from 1.
    predecessor.push_back(0); //in order to start from 1.


    for (ii = 1; ii < graph_size; ii ++)
    {
    distance.push_back(graph[start_vertex][ii]);
    not_checked.push_back(true);
    predecessor.push_back(start_vertex);

    }

    distance[start_vertex] = 0; //set start distance to zero
    predecessor[0] = -1;
    predecessor[start_vertex] = -1; //default start predecessor

    not_checked[start_vertex] = false; //mark as checked vertex

    bool done = false;

    int testing = 0;
    while (!done)
    {
    int V, shortest_d = BIG;

    for (jj = 1; jj < graph_size; jj ++)
    {
    //if it is <= we get a different route.
    if (distance[jj] <= shortest_d && not_checked[jj])
    {
    V = jj;
    shortest_d = distance[V];
    }
    }

    not_checked[V] = false; //for every neighbor W of V

    //edge relaxation
    for (W = 1; W < graph_size; W++)
    {
    if (graph[V][W] < BIG && not_checked[W])
    { //unchecked neighbor
    if (distance[W] > distance[V] + graph[V][W])
    {
    distance[W] = distance[V] + graph[V][W];
    predecessor[W] = V;
    }
    }

    while (kk < graph_size && !not_checked[kk])
    kk++;
    done = (kk == graph_size);//done=true if there are no unchecked
    neighbors
    }
    //*******************************************PRINT LEAST COST TO NODES
    for (ii = 1; ii < graph_size; ii++)
    {
    temp_d+=distance[ii];
    outputfile << "To arrive at node " << ii << " will cost" <<
    distance[ii] << endl;
    }
    average_distance = temp_d / (graph_size-2);
    //-2 because we dont count itself and also
    // the graph vector is 1 more than the number of nodes

    //E4
    cout << endl;

    //*******************************************PRINT LEAST COST TO NODES


    cout << "Shortest Paths" << endl; //Print out all shortest paths
    stack<int> temp; //No recursion- use stacks
    for (ii = 1; ii < graph_size; ii++)
    {
    int m = ii;
    int m1;

    while (predecessor[m] != -1)
    {
    m1 = m;
    temp.push(m);
    //intermediate_nodes[m]++; //how many times a node was used along
    the
    // paths. we will count the paths of length > 1
    m = predecessor[m];
    betweennes_l[m][m1]++;
    intermediate_nodes[m]++; //how many times a node was used along the
    //paths. we will count the paths of length > 2
    }

    int flag = 0;

    while ( !temp.empty() )
    {
    if (flag ==0 )
    {
    cout << start_vertex;
    }
    cout << "-"<< temp.top();
    flag++;
    temp.pop();
    }
    cout << endl;
    }



    for (iter=intermediate_nodes.begin(); iter !=
    intermediate_nodes.end(); ++iter)
    {
    if (iter->first != start_vertex)
    {
    cout << iter->first << ": " << iter->second << endl;
    }
    }
    cout << endl;

    cout << "Number of times each link is counted for the Shortest Path"
    << endl;

    for ( ii = 1; ii < graph_size; ii++)
    {
    for (jj = 1; jj < graph_size; jj++)
    {
    if (betweennes_l[ii][jj] != 0 )
    {
    cout << ii << "-"<< jj << "=" << betweennes_l[ii][jj]<< endl;
    }
    }
    }

    return average_distance;
    }





    Cheers
    costas
    , Jul 26, 2006
    #1
    1. Advertising

  2. Mark P Guest

    wrote:
    > Hello. I have implemented the Dijkstra shortest path algorithm, it
    > works fine but I have one question on how I can improve something.
    > I want to find all the possible shortest paths from a node since there
    > is a possibility to exist more than one shortest paths with the same
    > distance.
    >
    > Does anyone has any idea how this could be done?
    >


    [snip]

    > //edge relaxation
    > for (W = 1; W < graph_size; W++)
    > {
    > if (graph[V][W] < BIG && not_checked[W])
    > { //unchecked neighbor
    > if (distance[W] > distance[V] + graph[V][W])
    > {
    > distance[W] = distance[V] + graph[V][W];
    > predecessor[W] = V;
    > }
    > }


    [snip]

    This is more of a programming question than a C++ question so you might
    try comp.programming. To briefly address your question, you need to
    modify the logic of the above snippet to include a check for dist[W] =
    dist[V] + graph[V][W]. In such a case rather than replacing the
    predecessor of W with V, you must add V to a list of W's predecessors.
    The result is that, instead of each vertex having a path of predecessors
    back to the start, each vertex has a tree of predecessors back to the
    start, with each path through the tree being an equal shortest path.
    Mark P, Jul 26, 2006
    #2
    1. Advertising

  3. Guest

    Mark thanks for the reply.
    you are right on some point but the problem is that over there are
    passed only the values that have to do with the path that was already
    selected.

    mostly the problem is at



    //if it is <= we get a different route.
    for (jj = 1; jj < graph_size; jj ++)
    {

    if (distance[jj] <= shortest_d && not_checked[jj])
    {
    V = jj;
    shortest_d = distance[V];
    }
    }


    over there if i select <= and not < it gives another shortest path.
    the first problem it that it gives only 2 shortest paths ..and there
    are cases that there are more.
    The second problem is that even if I can see the two paths, i cannot
    store both of these paths. In order to achive it i have to modify the
    code (replace < with <= ) and run it for a second time.

    btw thanks for the tip. I have post it to comp.programming as well.
    , Jul 26, 2006
    #3
  4. Mark P Guest

    Please quote the relevant portions of the message to which you are replying.

    wrote:
    > Mark thanks for the reply.
    > you are right on some point but the problem is that over there are
    > passed only the values that have to do with the path that was already
    > selected.
    >
    > mostly the problem is at
    >
    >
    >
    > //if it is <= we get a different route.
    > for (jj = 1; jj < graph_size; jj ++)
    > {
    >
    > if (distance[jj] <= shortest_d && not_checked[jj])
    > {
    > V = jj;
    > shortest_d = distance[V];
    > }
    > }
    >


    I don't think so. The code above is to pick out the closest vertex not
    yet "finalized", which then becomes the source for the next relaxation
    pass. (And as an aside this is a pretty slow implementation since you
    take O(n) time to find that vertex. The conventional approach is to use
    a priority queue instead.)

    In any event, look back at my earlier reply. What you call the "edge
    relaxation" step is where you determine if there is a better route to a
    particular vertex. What you don't check for is the case of a tie-- two
    routes that are equally good. You need separate logic for the '>' case
    and the '=' case, but in the '=' case you need to save all equally good
    routes. As I said before, the way to do this is not to have a single
    predecessor value but a collection (list, vector, whatever) of values.

    Mark
    Mark P, Jul 27, 2006
    #4
  5. Guest

    Ok I can see what you are saying. I have implemented it and it works ok
    now with the concept that you told me. Since my predecessor was already
    a vector i constracted a map <int, vector <int>> and i store all the
    values of the predecessor when I have two equal length paths.
    My question now is how can i retrive these paths?
    Do I have to try all the possible combinations that can be made with
    the vectors (I can see a solution like that) or is there any easiest
    way.

    Cheers Costas
    , Jul 27, 2006
    #5
  6. Mark P Guest

    wrote:
    > Ok I can see what you are saying. I have implemented it and it works ok
    > now with the concept that you told me. Since my predecessor was already
    > a vector i constracted a map <int, vector <int>> and i store all the
    > values of the predecessor when I have two equal length paths.
    > My question now is how can i retrive these paths?
    > Do I have to try all the possible combinations that can be made with
    > the vectors (I can see a solution like that) or is there any easiest
    > way.
    >
    > Cheers Costas
    >


    Once again, when you reply to a post you need to quote the portion
    you're replying to. Just like I've quoted above what you wrote.

    The sets of predecessors define a DAG (directed acyclic graph). You'll
    need to build up all possible paths from start to finish. It's not that
    hard though-- you can do it recursively from the end point.
    Mark P, Jul 27, 2006
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. ThanhVu Nguyen
    Replies:
    6
    Views:
    5,806
    Karl Heinz Buchegger
    Aug 24, 2004
  2. Webdad
    Replies:
    20
    Views:
    1,874
    Jochus
    Dec 9, 2004
  3. Noah
    Replies:
    5
    Views:
    761
  4. rh0dium
    Replies:
    1
    Views:
    284
    rh0dium
    Jun 9, 2006
  5. Ohad Lutzky

    Paths, gentleman, paths

    Ohad Lutzky, Nov 6, 2006, in forum: Ruby
    Replies:
    2
    Views:
    181
    David Vallner
    Nov 7, 2006
Loading...

Share This Page