2
$\begingroup$

I'm presented with the following algorithm:


Dijkstra's Shortest-Path Algorithm

This algorithm finds the length of a shortest path from veftex $a$ to vertex $z$ in a connected, weighted graph. The weight of edge $(i,j)$ is such that $w(i,j)>0$, and the label of vertex $x$ is $L(x)$. At termination, $L(z)$ is the length of a shortest path from $a$ to $z$.

$\hspace{1cm}$Input: A connected, weighted graph in which all weights are positive; vertices $a$ and $z$

$\hspace{1cm}$Output: $L(z)$, the length of a shortest path from $a$ to $z$

1$\hspace{0.75cm}$dijkstra(w,a,z,L){

2$\hspace{0.75cm}$ L(a)=0

3$\hspace{0.75cm}$ for all vertices x$\neq$a

4$\hspace{0.75cm}$ L(x)=$\infty$

5$\hspace{0.75cm}$ T = set of all vertices

6$\hspace{0.75cm}$ //T is the set of vertices whose shortest distance from a has

7$\hspace{0.75cm}$ //not been found

8$\hspace{0.75cm}$ while(z$\in$T){

9$\hspace{0.75cm}$ chose v$\in$T with minimum L(v)

10$\hspace{0.75cm}$ T=T-{v}

11$\hspace{0.75cm}$ for each x$\in$T adjacent to v

12$\hspace{0.75cm}$ L(x)=min{L(x),L(v)+w(v,x)}

13$\hspace{0.75cm}$ }

14$\hspace{0.75cm}$}


I'm then asked the following question:


True or false? This algorithm finds the length of the shortest path in a connected, weighted graph even if some weights are negative. If true, prove it; otherwise, provide a counter example.


My question is what is being communicated in this algorithm?

$\endgroup$
  • $\begingroup$ What is your problem here? What have you tried? $\endgroup$ – dtldarek Aug 4 '13 at 19:25
  • $\begingroup$ Are you asking about what the algorithm is calculating, or are you asking how it is calculated, or are you asking how to prove that the calculation is correct? $\endgroup$ – DanielV Jan 24 '14 at 23:08
1
$\begingroup$

I'm not sure I completely get the question -- you are having trouble understanding Dijkstra's algorithm? The Wikipedia article is good, and there are many nice worked examples on the web. I would try to work through some of these examples, and then ask specific questions if you're still confused about how the algorithm works.

As for the homework problem you've quoted, here's a hint: any algorithm, Dijkstra or otherwise, for finding a shortest path will only work if such a path actually exists. Can you come up with an example of a connected weighted graph where no shortest path exists between some pair of nodes?

$\endgroup$
0
$\begingroup$

The question is a bit ambiguous, due to nonstandardized notation. The question is: can a path consist of repeated vertices and/or edges? Some authors say yes (and, when no, they call it a simple path), while others say no (and, when yes, they call it a walk instead of a path). More on that on Wikipedia.

If your path can have repetitions, then see what happens with the graph that has a cycle with (total) negative weight, and tell us what you got. Otherwise, I see no difference between edges with negative and nonnegative weights.

$\endgroup$
  • $\begingroup$ No need for a negative cycle. It suffices to present an example for which $g(v) = 0$ is not an admissible heuristic for A*. $\endgroup$ – Peter Taylor Aug 4 '13 at 21:14
0
$\begingroup$

Actually, Dijkstra's Algorithm does not work for negative weights. There is an easy counterexample for that:

Let the set of vertices $V = {a, z, x}$ and the set of edges $A = {(a, x), (a, z), (x, z)}$. Now consider the weight function which is defined such that $w((a, x)) = 10$, $w((a, z)) = 5$, $w((x, z)) = -10$.

You might want to draw this to see why here we do not actually find the correct shortest path from vertex $a$ to vertex $z$ using Dijkstra's Algorithm. The set $T$ consists only of $a$ in the beginning. $L(z) = 5$ and $L(x) = 10$ at this point. So in the next step of the algorithm we add $z$ to the set $T$ and return that the shortest path from $a$ to $z$ is of length $5$. But this is not true, since the path $a, x, z$ has length 0.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.