Shortest Paths in Conservative Graphs

We give a polynomial algorithm to compute shortest paths in weighted undirected graphs with no negative cycles (conservative graphs). We show that our procedure gives a simple algorithm to compute optimal T-joins (and consequently all of their special cases, including weighted matchings). We finally give a direct algorithmic proof for arbitrary weights of a theorem of Sebo characterizing conservative graphs and optimal paths.