Johnson Potential Reweighting
Use vertex potentials to turn negative edges into a safe nonnegative shortest-path problem.
Free theory articleUse vertex potentials to turn negative edges into a safe nonnegative shortest-path problem.
Concept & interpretation
Johnson's algorithm finds shortest paths between all pairs of vertices in a sparse, edge-weighted, directed graph. It allows some of the edge weights to be negative numbers, but no negative-weight cycles may exist.
Experiment
You can interact with the Johnson Potential Reweighting module to see how the graph topology and edge weights affect the potentials and reweighted values.
- Select "Negative cycle" in the Graph dropdown. Observe that the globally detected cycle immediately halts further calculation and changes the result Status to "Negative cycle".
- Select "Disconnected" in the Graph dropdown. Notice that the vertices' potential arrays still update since the super-source can reach them, but the Source-to-Target distances display as Unreachable.