5
$\begingroup$

The book "Algorithms" by Robert Sedgewick and Kevin Wayne hinted that (see the quote below) there are efficient algorithms for finding shortest paths in undirected graphs with possibly negative edge weights (not by treating an undirected edge as two directed one which means that a single negative edge implies a negative cycle). However, no references are given in the book. Are you aware of any such algorithms?

Q. How can we find shortest paths in undirected (edge-weighted) graphs?

A. For positive edge weights, Dijkstra's algorithm does the job. We just build an EdgeWeightedDigraph corresponding to the given EdgeWeightedGraph (by adding two directed edges corresponding to each undirected edge, one in each direction) and then run Dijkstra's algorithm. If edge weights can be negative (emphasis added), efficient algorithms are available, but they are more complicated than the Bellman-Ford algorithm.

Improve this question
$\endgroup$
2
  • $\begingroup$ If I am not wrong, we make the lightest/shortest edge 0-weighted. For example, if the shortest edge has weight -x, we add x to all edge weights. That's if you don't exploit any negative cycle. I don't know if you are allowed to do this. $\endgroup$
    – rus9384
    Commented Jun 9, 2017 at 14:06
  • 1
    $\begingroup$ This obviously doesn't work. Assume you have a graph with 3 nodes s,u,t and the following edges: (s,u) with weight -2, (u,t) with weight -1 and (s,t) with weight -2. The shortest path between s and t has weight -3, going through u. Now with the transformation you propose, the shortest path does not go through u anymore, so you miss the real shortest path. $\endgroup$
    – holf
    Commented Jun 9, 2017 at 14:10

1 Answer 1

Reset to default
7
$\begingroup$

I contacted one of the authors (Kevin Wayne; thanks) of the textbook "Algorithms, 4th Edition" and got a hint:

Try adding "t-joins" or "perfect matching" to your web searches.

Following this, I found the following two lecture notes:

Shortest Path Algorithms Luis Goddyn, Math 408: Using Edmonds' Minimum Weight Perfect Matching Algorithm to solve shortest path problems for undirected graph with negative-weight edges, provided that $(G, d)$ is conservatively weighted, that is, if $G$ has no negative weight directed circuits (circuits $C$ whose total weight $d(C)$ is negative), then Dijkstra’s algorithm stops with a shortest path tree $T$ rooted at $s$.

$T$-joins and Applications from CS 598CSC: Combinatorial Optimization uses the $T$-join techniques.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.