# Conservative weighting

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]}.

## References

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