Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am studying for an oncoming test from graph theory and I've been solving some problems from homework assignments few years old. So I unfortunately can't find the solutions anywhere. Therefore I would just like to politely ask whether someone can please spare a few minutes and review my conclusions.

$1$-A)
State an example of a nondirected graph which has a single negative-weighted edge, but Dijkstra algrithm still computes the shortest path correctly for some vertexes (but not all). 1-A solution

$1$-B)
State an example of a nondirected graph which has a single negative-weighted edge, but Dijkstra algrithm still computes the shortest path correctly for all vertexes.
1-B solution

$1$-C)
State an example of a graph and its vertes such that the output of Dijkstra algorithm on this graph and the given vertex won't be minimal paths. (State the graph, the starting vertex, the real minimal paths and the minimal paths found by Dijkstra algorithm)
1-C solution

Starting vertex is $A$.
Real minimal paths are:
$A\rightarrow C \ 0$
$A\rightarrow B \ 1$
Dijkstra minimal paths:
$A\rightarrow C \ 0$
$A\rightarrow B \ 2$

I am a bit confused about this one - I know that Dijkstra's algorithm anticipates only nonnegative edge weights so it never "backtracks", but I have doubts that even Bellman-Ford would solve that, since the graph is not oriented, it seems to me that it must be cyclic, so I can lower the value of some paths indefinitely.

$2)$
Consider the following algorithm for seeking minimal paths in finite non-oriented graph with negative-weighted edges. Mark the weight with lowest value as $h$. Then add $|h|$ to all edge weights. All weights are now non-negative. Let's pick a vertex $v$ and find the minimal paths from it using Dijkstra's algorithm. Prove or disprove, that using this approach we get minimal paths from vertex $v$ in the original graph. (We would substract $k|h|$ from all paths found, $k$ is the path's length)

I think that it wouldn't work and I would disprove it using the following example:

Suppose we have a graph
2 solution
The minimal path $A \rightarrow B$ has a value of $0$, and goes through $ACDB$

The lowest weight is $-2$, so by adding it to the rest we get:
2 solution
Now the minimal path $A \rightarrow B$ has a value of $4$ and goes through $AB$
By susbstracting $4\times 2$ we get that path $A \rightarrow B$ has a value of $-4$, which obviously does not correspond with the original graph.
Therefore it is not possible to get the original minimal paths using this modification.

Thanks in advance! :)

share|improve this question
2  
You are right, Bellman-Ford can't solve 1(c), since your graph is undirected, the edge with weight $-2$ is really a negative loop, and Bellman-Ford could tell you that. –  sxu Nov 9 '11 at 1:15
    
Can't edit my previous comment, but if you make the edge directed as $(A,B)$, $(A,C)$ and $(C,B)$, Dijkstra still fails. –  sxu Nov 9 '11 at 1:22
    
The part about subtracting $4\times2$ isn't right. You're to subtract $k$, length of path, which is 1 (not 4 - that's the weight of the path), times $|h|$, which is 2, so you subtract 2, not 8. –  Gerry Myerson Nov 9 '11 at 3:37
    
@GerryMyerson Ok, my bad. But still - The minimal path is then 2, which is still incorect, isn't it? –  Alexandar Živkovič Nov 9 '11 at 13:00
    
@Shen Well that's the problem, it has to be undirected graphs. So should I come up with something different? –  Alexandar Živkovič Nov 9 '11 at 13:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.