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.
Finding shortest paths in undirected graphs with possibly negative edge weights
algorithms;graph theory;shortest path;weighted graphs;reference question
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 Dijkstras 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.