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