# Dijkstra algorithm problem.

• 05-28-2005
apacz
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
• 05-28-2005
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
• 05-28-2005
apacz
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 :/
• 05-28-2005
okinrus
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.
• 05-28-2005
apacz
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; }```
• 05-28-2005
apacz
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