2
$\begingroup$

Currently we are discussing applying Johnson's algorithm on undirected graph with negative edge weights. And the graph may contains cycles, but the sum of weights of any cycle is guaranteed to be non-negative.

If we consider the undirected graph as bi-directed, then any negative-weight undirected edge will create a negative cycle in the bi-directed graph, and violate the prerequisite of Johnson's algorithm.

Is there any altered version of Johnson's algorithm can handle such scenario?

-- update 2017/12/30 --

Sorry, I forget to mention an additional constraint for the path: the path should be simple, which means one edge could only be travel for once.

$\endgroup$
2
$\begingroup$

Shortest simple paths

Finding the length of the shortest simple path is NP-hard, so there is no efficient algorithm.

Shortest paths (not necessarily simple)

The original version of the question didn't include the requirement that the path be simple. Below I include my answer to that version of the question, for posterity:

Decompose the graph into connected components. Solve the problem separately for each connected component.

If there is an edge with negative weight in the component, then for all pairs of vertices $u,v$ in the component, the distance from $u$ to $v$ is $-\infty$. So, you can output $d(u,v)=-\infty$ for all pairs $u,v$ in the component. You don't even need to run Johnson's algorithm.

(Why is that answer correct? Well, suppose the edge $(a,b)$ has negative weight. Then consider a path $u \leadsto a \to b \to a \to \cdots \to b \leadsto v$. Such a path can have arbitrarily small length, by traversing the cycle $a \to b \to a$ sufficiently many times.)

If there is no edge in the component with negative weight, you can use Johnson's algorithm to compute the distance between each pair of vertices in the component. Johnson's algorithm on this component will work fine, since this component has no negative-weight edges.

Finally, the distance between any two vertices that are in different components is $+\infty$, since there is no path between them.

$\endgroup$
  • $\begingroup$ Thanks for your answer. I am sorry for that I forget to mention an additional constraint for the path: the path should be simple, which means one edge could only be travel for once. And thus the path u-~->a->b->...->a->b-~->v should not be taken into consideration. Is there possibility for us to find simple path from the graph described above by algorithm similar to Johnson? $\endgroup$ – Wuyue Lu Dec 30 '17 at 11:45

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.