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$-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$-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)
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
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:
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! :)
