patternMinor
Finding shortest paths in undirected graphs with possibly negative edge weights
Viewed 0 times
shortestwithpossiblyweightsgraphspathsedgeundirectedfindingnegative
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#76578, answer score: 7
Revisions (0)
No revisions yet.