Conservative weighting

From Egres Open
Jump to: navigation, search

Given a directed graph D=(V,A), a weighting [math]w:A \to {\mathbb R}[/math] is conservative if the weight of every directed cycle is non-negative. In an undirected graph G=(V,E), a weighting [math]w:E \to {\mathbb R}[/math] is called conservative if the weight of every cycle is non-negative.

A minimum weight path between two nodes in a digraph with a conservative weighting can be computed using Johnson's algorithm: first find a potential using the Bellman-Ford algorithm, then modify the arc weights by the potential and use Dijkstra's algorithm on the resulting non-negative weighting.

Finding a minimum weight path in an undirected graph with a conservative weighting is more difficult and amounts to finding a minimum weight T-join. A combinatorial algorithm was developed by Sebő in [1]; see also [2]. For a survey on the structural aspects of undirected distances and T-joins, see Sebő [3] and Frank [4].


  1. A. Sebő, Finding the t-join structure of graphs, DOI link, author link
  2. M. Conforti, R. Rizzi, Shortest paths in conservative graphs, DOI link, technical report
  3. A. Sebő, Undirected distances and the postman-structure of graphs, DOI link, author link
  4. A. Frank, A survey on T-joins, T-cuts, and conservative weightings, ResearchGate link, author link.