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.
