Thread: Dijkstra algorithm problem.

  1. #1
    Registered User
    Join Date
    May 2005
    Posts
    76

    Dijkstra algorithm problem.

    Hi,
    I don't think if it's the best sub-forum to ask that question but there isn't any suitable.
    Ok, I found a description of Dijkstra's algorithm on wiki's site:
    http://en.wikipedia.org/wiki/Dijkstra's_algorithm
    and there is a pseudocode of it:
    Code:
    1   function Dijkstra(G, w, s)
    2      for each vertex v in V[G]                        // Initialization
    3         do d[v] := infinity
    4            previous[v] := undefined
    5      d[s] := 0
    6      S := empty set
    7      Q := set of all vertices
    8      while Q is not an empty set
    9         do u := Extract-Min(Q)
    10           S := S union {u}
    11           for each edge (u,v) outgoing from u
    12              do if d[v] > d[u] + w(u,v)             // Relax (u,v)
    13                 then d[v] := d[u] + w(u,v)
    14                    previous[v] := u
    15                    Q := Update(Q)
    And in my implementation i followed by that code. But when i finished it i noticed that if there is no relax of (u,v) (lines 12-14) then "previous[v]" is still undefined. Does anybody have an idea where should i set previous[v] before?
    Thanks.
    apacz

  2. #2
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    If you haven't looked at the pseudocode for Djikstras algorhithm on this site here's a link. Maybe it will help, and maybe it will be a waste of time. I've not had the
    dubious pleasure of working the algorhithm myself so I can't help you much beyond offering another source of information.

    http://www.cprogramming.com/tutorial.../dijkstra.html
    You're only born perfect.

  3. #3
    Registered User
    Join Date
    May 2005
    Posts
    76
    thx, but well, I read a few descripions of dijkstra and in that which you put link to, my question also appears:
    Code:
    while(F is missing a vertex)
       pick the vertex, v, in U with the shortest path to s
       add v to F
       for each edge of v, (v1, v2)
            /* The next step is sometimes given the confusing name "relaxation"
            if(dist[v1] + length(v1, v2) < dist[v2])
                dist[v2] = dist[v1] + length(v1, v2)
                prev[v2] = v1
                possibly update U, depending on implementation
            end if
        end for
    end while
    We " add v to F" but prev[v] is not set, and what is more, if there's no relaxation next, prev[v] is not set so we're not able to step from the last vertex to the initial one :/

  4. #4
    Registered User
    Join Date
    Aug 2003
    Posts
    470
    But when i finished it i noticed that if there is no relax of (u,v) (lines 12-14) then "previous[v]" is still undefined. Does anybody have an idea where should i set previous[v] before?
    Thanks.
    apacz
    Initially, d[v] = infinity for all vertices except the source vertex, which is 0. So, d[v] > d[u] + w(u,v) is true if d[v] is infinity. As long as none of the vertices are iosolated from the source vertex, Extract-Min will keep extracting a vertex which is not infinite. When vertices are isolated from the source vertex, you'll have previous undefined for them, but this is what you want. A path from the source vertex cannot be made to any vertex that is isolated. Because C++ doesn't have a value for undefined, you need to make one up. I'd use -1 because an array index can never be negative.

  5. #5
    Registered User
    Join Date
    May 2005
    Posts
    76
    Tx,
    So it seems my implementation is wrong... can you have a glance at some peave of code ?
    Code:
    #define INF 1000000001
    Code:
    dijkstra_graph::dijkstra_graph(int i)
            : graph(i)
    {
                    d=new unsigned long[i];
                    pop=new int[i];
                    D=new bool[i];
                    D_size=0;
                    for(int y=0;y<i;y++)
                    {
                            pop[y]=-1;
                            D[y]=false;
                            d[y]=INF;
                    }
    }
    Code:
    int dijkstra_graph::shortest_way(int initial_vertex)
    {
            d[initial_vertex]=0; // step 1
            unsigned long   min=INF,vertex; // for step 3 (extra)
            while(D_size<vertex_number) // step 2
            {
                    for(int i=0;i<vertex_number;i++) // step 3
                    {
                            if(D[i]==false)
                            {
                                    if(d[i]<=min)
                                    {
                                            vertex=i;
                                            min=d[i];
                                    }
                            }
                    } // end of step 3
                    D[vertex]=true; // step 4
                    increase_D();
                    for(int i=0;i<vertex_number;i++) // step 5
                    {
                            if(edge_u_v(vertex,i)!=-1) // check if edge bettwen vertex and i exists.
                            {
                                    if( d[i] > d[vertex] + edge_u_v(vertex,i) ) // step 6
                                    {
                                            d[i]=d[vertex] + edge_u_v(vertex,i); // step 7
                                            pop[i]=vertex; // step 8
                                    }
                            }
                    } // end of step 5
    
            }
            return 0;
    }

  6. #6
    Registered User
    Join Date
    May 2005
    Posts
    76
    Ok, I found 2 bugs, and now it work fine. First:
    for(int i=0;i<vertex_number;i++) // step 3
    before that we there should be min=INF
    and the second bug was bad nulling **w.
    Anyway, thx for interest.
    Regards,
    apacz

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with grid problem (dynamic programming)
    By scp89 in forum C Programming
    Replies: 15
    Last Post: 05-07-2009, 12:16 PM
  2. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 02:30 AM
  3. Simple algorithm problem
    By stodd04 in forum C Programming
    Replies: 11
    Last Post: 03-04-2005, 11:08 AM
  4. algorithm problem
    By cdonlan in forum C++ Programming
    Replies: 3
    Last Post: 02-10-2005, 09:16 PM
  5. Algorithm question
    By PJYelton in forum C++ Programming
    Replies: 2
    Last Post: 10-28-2002, 10:52 AM