Function johnson_reweight 

fn johnson_reweight<G, F, K>(
    graph: G,
    edge_cost: F,
) -> Result<Vec<K>, NegativeCycle>
where
    G: IntoEdges + IntoNodeIdentifiers + NodeIndexable + Visitable,
    G::NodeId: Eq + Hash,
    F: FnMut(G::EdgeRef) -> K,
    K: BoundedMeasure + Copy + Sub<K, Output = K>,

Add a virtual node to the graph with oriented edges with zero weight to all other vertices, and then run SPFA from it. The found distances will be used to change the edge weights in Dijkstra’s algorithm to make them non-negative.