1
$\begingroup$

Of course assuming there aren't any negative cycles. I saw this question somewhere. And i saw a complicated solution which says to build three such graphs and connect between them in a very complicated manner. My question is why isn't my simple solution good for it? My simple solution is to first find the negative edge . And then start traversing from that edge with dijkstra. I think once you start with that edge, dijextra should work. So that way i mange it in O(e + vlogV) . So why isn't my easy solution mentioned there. Is my solution correct?

$\endgroup$
2
  • $\begingroup$ I think here is another algorithm for this case if all weight of edges strictly > 0: Make the negative edge with cost 0 and let weight of edge denoted by r; since no edge can beat edge, then solve by Dijkstra's algorithm. When you finished, if any path that use the negative edge with weight s for example, then do the following: s= s-r. I need to think for how to improve it if we have edges with weight >= 0. $\endgroup$
    – user777
    Nov 19 '19 at 19:13
  • $\begingroup$ Another way to deal with weight >=0. So, we have at most n-1 paths [from source node to all other nodes]. Now, assign weight with variable $a$ to the negative weight. Apply Dijkstra's algorithm from that source node to all other nodes, in any case you use the negative edge, then find other path without using negative edge, so in total we have 'two path' for each 'path' resulted from Dikstra's algorithm, one with weight something plus a and one without a. Now, do arithmetic to compare the best path. Try to follow any gaps the other part. $\endgroup$
    – user777
    Nov 19 '19 at 19:31
2
$\begingroup$

No. The negative edge will not always be part of the shortest path. For example, in the digraph

A <==[+1]== B ==[+4]==> C ==[-1]==> D ==[+4]==> E

the shortest path departing from B is the path from B to A, and does not include the negative edge (C,D).

Even when the negative edge is part of the shortest path, it won't necessarily be the first edge of the path.

$\endgroup$
2
  • $\begingroup$ The question title says shortest paths. I think, OP wants to find the (individually) shortest path to every node, not the overall shortest path. $\endgroup$
    – Albjenow
    Nov 19 '19 at 11:10
  • $\begingroup$ If that is the case, "starting dijkstra from the negative edge" makes even less sense, since the source node might be in a completely different part of the graph than the negative edge. $\endgroup$
    – Vincenzo
    Nov 19 '19 at 13:31
0
$\begingroup$

I want to add that the method of replacing the weight of negative edge by $0$ or $a>0$ also has drawbacks. Consider the following example:

enter image description here

If we replace $-10$ with something non-negative, Dijkstra will never find path $0 \rightarrow 1 \rightarrow 2$, and it will say that the optimal path from $0 \rightarrow 2$ has weight $1$.

Running Dijkstra on some copies of the initial graph is a common and understandable method, if it is explained properly. Here it's enough to have two copies of the vertex set. Let $G=(V,E)$ be the initial graph, where $e=(u, v, w)$ is the negative edge of weight $w$. Then let $V_0$ and $V_1$ be two copies of $V$, each connected by all edges from $E$ except $e$, and draw edge $e'=(u_0, v_0, w)$. One can prove that Dijkstra works correctly in such graph, and the optimal answer for each vertex $v$ will equal $\min({d[v_0], d[v_1]})$.

If we don't want to multiply a graph, we can guarantee the occurrence of the negative edge in all shortest paths by compressing $u$ and $v$ into one super-vertex $S$. Edges of the new graph should be modified of the following way: $(x \rightarrow u)$ should go to $S$ now, $(v \rightarrow y)$ should go from $S$, $(u \rightarrow y)$ and $(x \rightarrow v)$ should go away.

$\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.