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$
2
  • $\begingroup$ What is your problem here? What have you tried? $\endgroup$ Commented Aug 4, 2013 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$ Commented Jan 24, 2014 at 23:08

3 Answers 3

Reset to default
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$
1
  • $\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$ Commented Aug 4, 2013 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$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.