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

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

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 :/

Quote:

---

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.

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

---

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