1. ## 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. 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

3. 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
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. 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. 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. 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