Johnson Reweighting Technique: Algorithm Analysis and Code

Introduction and Core Concepts

The johnson reweighting technique is a foundational graph algorithm strategy that solves the all-pairs shortest path (APSP) problem on sparse graphs that contain negative edge weights but no negative cycles. While many introductory algorithms assume all edge weights are non-negative, real-world networks frequently violate this assumption. Costs, profits, arbitrage opportunities, and traffic penalties can naturally be modeled as negative weights, making a robust APSP solution essential.

At its core, the johnson reweighting technique is not a standalone shortest-path algorithm but rather a clever reweighting framework that enables the use of Dijkstra's algorithm on graphs where it would normally fail. Dijkstra's algorithm, with its greedy approach and priority queue, requires non-negative edge weights to guarantee correctness. Bellman-Ford can handle negative weights but is too slow to run from every vertex. Johnson's approach bridges this gap: it computes a set of vertex potentials that transform every edge weight into a non-negative value while preserving the relative ordering of paths.

Why does this matter? For dense graphs, the Floyd-Warshall algorithm with its O(V^3) time complexity is often acceptable. However, for sparse graphs where the number of edges E is much smaller than V^2, Floyd-Warshall wastes enormous computational effort. The johnson reweighting technique achieves O(V^2 log V + V*E) time with a binary heap, which is asymptotically superior for sparse graphs. This makes it the algorithm of choice for large-scale road networks, social graphs, and communication networks where E = O(V log V) or E = O(V).

The Core Problem: Negative Weights and All-Pairs Shortest Paths

Consider a directed graph G = (V, E) with a weight function w: E → R. The goal of APSP is to find the shortest path distance between every pair of vertices (u, v). If the graph has no negative weights, we can simply run Dijkstra's algorithm V times. If it has negative weights but no negative cycles, we could run Bellman-Ford V times, but that costs O(V^2 * E), which is prohibitive.

A negative cycle is a cycle whose total edge weight is negative. If such a cycle is reachable, the concept of a shortest path becomes ill-defined because you can loop infinitely to decrease the path cost without bound. Johnson's algorithm explicitly detects this condition and aborts, which is a critical correctness guarantee. The reweighting technique itself depends on the absence of negative cycles to compute valid potentials.

The key insight of Johnson is that we can add a potential value h(v) to each vertex v and define a new weight function w'(u, v) = w(u, v) + h(u) - h(v). This transformation has two crucial properties: it makes all new weights non-negative, and it preserves shortest paths. That is, a path is shortest under w if and only if it is shortest under w'. The final true distances are then easily recovered by reversing the transformation.

How It Works

The johnson reweighting technique operates in three distinct phases. Each phase has a specific mathematical purpose and builds directly on the previous one. Understanding the theory behind each step is essential for correct implementation and for proving that the algorithm works.

Phase 1 introduces a new super source vertex s' that is connected to every original vertex v in V with a zero-weight edge (s', v). This augmented graph G' = (V', E') where V' = V ∪ {s'} allows us to compute single-source shortest paths to all vertices simultaneously. We then run the Bellman-Ford algorithm from s' to compute the shortest path distance h(v) = δ(s', v) for every vertex v. These h(v) values serve as the vertex potentials or reweighting function.

Phase 2 performs the actual reweighting. For every edge (u, v) ∈ E, we compute its new weight as w'(u, v) = w(u, v) + h(u) - h(v). The brilliance of this formula lies in the triangle inequality satisfied by shortest paths. Because h(v) ≤ h(u) + w(u, v) for all edges (a property of shortest paths computed by Bellman-Ford), it follows that w'(u, v) = w(u, v) + h(u) - h(v) ≥ 0. Thus every reweighted edge becomes non-negative, even if the original weight was negative.

Preservation of Shortest Paths

The reweighting is not arbitrary; it preserves path optimality. Consider any path p = v0 → v1 → ... → vk. Its reweighted length is w'(p) = ∑ w'(vi-1, vi) = ∑ (w(vi-1, vi) + h(vi-1) - h(vi)). This sum telescopes to w'(p) = w(p) + h(v0) - h(vk). Notice that for a fixed pair of endpoints (v0, vk), the term h(v0) - h(vk) is constant. Therefore, minimizing w'(p) is equivalent to minimizing w(p). Any shortest path under w' is also shortest under w.

Phase 3 leverages this property. Since all w' weights are non-negative, we can now run Dijkstra's algorithm from each vertex u ∈ V on the reweighted graph to compute all-pairs distances δ'(u, v). The final step converts these back to the original weights using the inverse formula: δ(u, v) = δ'(u, v) - h(u) + h(v). If Bellman-Ford in Phase 1 detects a negative cycle, the entire algorithm terminates and reports that no well-defined shortest paths exist.

This three-phase structure elegantly combines the generality of Bellman-Ford (handling negatives once) with the efficiency of Dijkstra (handling non-negatives many times). It is a classic example of algorithmic reduction and potential functions, a concept that also appears in amortized analysis and network flow algorithms.

Implementation

Implementing the johnson reweighting technique correctly requires careful handling of graph representation, infinity values, and the reweighting formula. Below are modular Python implementations that together form a complete and production-ready solution. All comparisons use escaped HTML entities to ensure safe rendering.

The first component computes the vertex potentials using Bellman-Ford from the added super source. We represent the graph as an edge list for this phase, which is the natural representation for Bellman-Ford. Early termination is included as an optimization when no relaxations occur in an iteration.

def compute_potentials(n, edges):
    """
    Compute vertex potentials h[v] using Bellman-Ford from super source.
    n: number of vertices (0 .. n-1)
    edges: list of (u, v, w) for original graph
    Returns: list h of size n
    Raises ValueError if negative cycle exists
    """
    # Add super source n connected to all vertices with 0 weight
    extended_edges = edges + [(n, v, 0) for v in range(n)]
    N = n + 1
    h = [float('inf')] * N
    h[n] = 0

    # Relax N-1 times
    for i in range(N - 1):
        updated = False
        for u, v, w in extended_edges:
            if h[u] + w < h[v]:
                h[v] = h[u] + w
                updated = True
        if not updated:
            break

    # Negative cycle detection
    for u, v, w in extended_edges:
        if h[u] + w < h[v]:
            raise ValueError("Graph contains a negative weight cycle")

    return h[:n]  # discard super source

The second component is an optimized Dijkstra implementation using a binary heap (priority queue). This will be executed V times on the reweighted graph. It uses an adjacency list representation, which is efficient for sparse graphs, and includes a visited set to avoid processing stale heap entries.

import heapq

def dijkstra_reweighted(n, adj_reweighted, source):
    """
    Dijkstra on graph with non-negative reweighted edges.
    n: number of vertices
    adj_reweighted: adjacency list where adj_reweighted[u] = list of (v, w_prime)
    source: source vertex
    Returns: list dist_prime where dist_prime[v] = delta'(source, v)
    """
    dist = [float('inf')] * n
    dist[source] = 0
    pq = [(0, source)]
    visited = [False] * n

    while pq:
        d, u = heapq.heappop(pq)
        if visited[u]:
            continue
        visited[u] = True
        # Skip stale entries where d > dist[u]
        if d > dist[u]:
            continue
        for v, w_prime in adj_reweighted[u]:
            # w_prime is guaranteed >= 0
            if dist[u] + w_prime < dist[v]:
                dist[v] = dist[u] + w_prime
                heapq.heappush(pq, (dist[v], v))
    return dist

The third block ties everything together, performing the reweighting, running Dijkstra from every source, and converting distances back to the original weight space. Note the construction of the reweighted adjacency list and the final correction step.

def johnson_all_pairs(n, edges):
    """
    Full Johnson's algorithm for APSP.
    n: number of vertices
    edges: list of (u, v, w) with possible negative weights
    Returns: n x n matrix dist where dist[u][v] is shortest path distance
    """
    # Step 1: Compute potentials
    h = compute_potentials(n, edges)

    # Step 2: Reweight edges to be non-negative
    adj_reweighted = [[] for _ in range(n)]
    for u, v, w in edges:
        w_prime = w + h[u] - h[v]
        # Due to floating point or correctness, w_prime should be >= 0
        # Clamp small negative epsilon to 0 if needed
        if w_prime < 0 and w_prime > -1e-9:
            w_prime = 0
        adj_reweighted[u].append((v, w_prime))

    # Step 3: Run Dijkstra from each vertex
    all_pairs = [[float('inf')] * n for _ in range(n)]
    for u in range(n):
        dist_prime = dijkstra_reweighted(n, adj_reweighted, u)
        for v in range(n):
            if dist_prime[v] < float('inf'):
                # Convert back: delta(u,v) = delta'(u,v) - h[u] + h[v]
                all_pairs[u][v] = dist_prime[v] - h[u] + h[v]
        all_pairs[u][u] = 0

    return all_pairs

A fourth helper is useful for building the graph from an adjacency list and for testing. This utility demonstrates how to handle disconnected components and how to verify the non-negativity invariant after reweighting, which is an excellent debugging check.

def build_and_validate(n, edges):
    """Helper to build graph and validate reweighting invariant."""
    h = compute_potentials(n, edges)
    print("Potentials h:", h)
    min_w_prime = float('inf')
    for u, v, w in edges:
        w_prime = w + h[u] - h[v]
        min_w_prime = min(min_w_prime, w_prime)
        assert w_prime >= -1e-9, f"Negative reweighted edge {(u,v,w)} -> {w_prime}"
        print(f"Edge {u} -> {v} : {w}  becomes  {w_prime:.2f}")

    print(f"Minimum reweighted weight: {min_w_prime:.2f} (>= 0 required)")
    # Example usage
    dist_matrix = johnson_all_pairs(n, edges)
    for row in dist_matrix:
        print(["inf" if x == float('inf') else f"{x:.1f}" for x in row])
    return dist_matrix

# Example graph with negative edge but no negative cycle
example_edges = [(0, 1, -2), (1, 2, 3), (0, 2, 1), (2, 3, -1), (1, 3, 2)]
build_and_validate(4, example_edges)

Step-by-Step Example

To solidify understanding, let us walk through a concrete example with four vertices. Consider the directed graph with edges: 0 → 1 (-2), 0 → 2 (4), 1 → 2 (3), 1 → 3 (2), 2 → 3 (-1). This graph has a negative edge (0 → 1) and a negative edge (2 → 3) but no negative cycle.

Step 1: Add super source s' = 4 with zero-weight edges to all vertices: 4 → 0 (0), 4 → 1 (0), 4 → 2 (0), 4 → 3 (0). Run Bellman-Ford from 4. Initialization: h[4]=0, others = inf. After first iteration, all vertices become 0 via the zero edges. Second iteration relaxes using original edges: h[1] can be improved via 0 → 1: 0 + (-2) = -2 < 0, so h[1] = -2. h[3] via 2 → 3: 0 + (-1) = -1 < 0, so h[3] = -1. Further iterations propagate: h[2] via 1 → 2: -2 + 3 = 1 < 0, so h[2] = 1 is not an improvement over 0, so it stays 0. Final potentials after convergence are h = [0, -2, 0, -1]. You can verify no further relaxation is possible and no negative cycle exists.

Step 2: Reweight every edge using w'(u,v) = w(u,v) + h[u] - h[v]. Compute each: 0 → 1: -2 + 0 - (-2) = 0, 0 → 2: 4 + 0 - 0 = 4, 1 → 2: 3 + (-2) - 0 = 1, 1 → 3: 2 + (-2) - (-1) = 1, 2 → 3: -1 + 0 - (-1) = 0. All reweighted edges are now non-negative (0, 4, 1, 1, 0), satisfying the invariant required for Dijkstra.

Running Dijkstra and Converting Back

Step 3: Run Dijkstra from each source on the reweighted graph. From source 0, Dijkstra yields distances δ': δ'(0,0)=0, δ'(0,1)=0, δ'(0,2)=1 (via 0→1→2 with cost 0+1), δ'(0,3)=1 (via 0→1→3 with cost 0+1, or 0→1→2→3 with cost 0+1+0=1). From source 1: δ'(1,1)=0, δ'(1,2)=1, δ'(1,3)=1. From source 2: δ'(2,3)=0.

Now convert back using δ(u,v) = δ'(u,v) - h[u] + h[v]. For example, the true distance from 0 to 3 is δ(0,3) = 1 - h[0] + h[3] = 1 - 0 + (-1) = 0. Let us verify manually in the original graph: Path 0→1→3 costs -2 + 2 = 0, and path 0→1→2→3 costs -2 + 3 + (-1) = 0. Both are 0, matching the computed result. The distance from 0 to 2 is δ(0,2) = 1 - 0 + 0 = 1, which corresponds to path 0→1→2 costing -2 + 3 = 1, which is indeed shorter than the direct edge 0→2 costing 4.

This walkthrough demonstrates two critical checks: first, that reweighting eliminates negativity, and second, that the conversion formula correctly restores original distances. If you implement the algorithm and your reweighted edges contain a negative value (beyond floating-point epsilon), your Bellman-Ford potentials are incorrect or a negative cycle exists.

Complexity Analysis

The efficiency of the johnson reweighting technique is best understood by analyzing each phase independently and then combining them. The choice of data structures, particularly the priority queue implementation for Dijkstra, has a significant impact on the final complexity.

Phase 1 runs Bellman-Ford on a graph with V+1 vertices and E+V edges. Its time complexity is O((V+1)*(E+V)) = O(V*E). This is the dominant cost for very sparse graphs but is executed only once. Its space complexity is O(V) for the distance array plus O(E) for the edge list.

Phase 2 reweights all edges in O(E) time and O(V+E) space to store the new adjacency list. This phase is linear and negligible compared to the other two.

Phase 3 runs Dijkstra's algorithm V times. With a binary heap, each Dijkstra run costs O((V+E) log V). Therefore V runs cost O(V*(V+E) log V) = O(V^2 log V + V*E log V). With a Fibonacci heap, the amortized cost per Dijkstra is O(E + V log V), yielding O(V*E + V^2 log V) total. For sparse graphs where E = O(V), this becomes O(V^2 log V), which is substantially better than Floyd-Warshall's O(V^3).

In terms of space, if you need to store the full all-pairs distance matrix, you will need O(V^2) space regardless of the algorithm. If you only need to answer queries on demand, you can avoid storing the full matrix and keep the reweighted graph plus potentials in O(V+E) space, running Dijkstra lazily. The best case for Bellman-Ford occurs when the graph has no negative edges or is already topologically sorted in a way that allows early termination after a few iterations.

It is important to note that the worst-case time complexity of Johnson with a binary heap is O(V*E log V). When the graph is dense, E approaches V^2, so this becomes O(V^3 log V), which is worse than Floyd-Warshall's O(V^3). Therefore, Johnson is specifically advantageous for sparse graphs, while Floyd-Warshall is preferable for dense graphs. This trade-off is a common interview discussion point.

Variations and Optimizations

While the classic johnson reweighting technique is powerful, several variations and optimizations can improve its performance in practical scenarios. These adaptations address specific graph properties or hardware constraints.

One common optimization is to replace Bellman-Ford with the Shortest Path Faster Algorithm (SPFA) or the Bellman-Ford with queue optimization for computing potentials. SPFA has an average-case time of O(E) on many real-world graphs, though its worst case remains O(V*E). For graphs without negative cycles that are not adversarially constructed, SPFA can dramatically reduce the time spent in Phase 1. Another alternative is to use topological ordering if the graph is known to be a Directed Acyclic Graph (DAG); in that case, potentials can be computed in O(V+E) via a single dynamic programming pass.

For the Dijkstra phase, the choice of priority queue is critical. While Fibonacci heaps offer better theoretical asymptotic complexity, they have large constant factors and are complex to implement. In practice, a binary heap or a pairing heap often performs better. For integer weights with a limited range, a Dial's algorithm (bucket-based Dijkstra) using a 0..C*V bucket array can achieve O(E + C*V) per run, and a Radix Heap can achieve O(E + V log C) where C is the maximum edge weight.

Advanced Variants

An important variation handles the case where you only need shortest paths between a subset of vertex pairs, such as k sources to all destinations. Instead of running Dijkstra V times, you run it only k times, reducing the cost to O(V*E + k*(V+E) log V). This is common in web server routing where only a few data centers act as sources.

Another optimization is incremental Johnson for dynamic graphs. If edge weights change slightly or a few edges are added, recomputing potentials from scratch is wasteful. Techniques using dynamic Bellman-Ford or maintaining potentials with Johnson's reweighting can update h values incrementally. Similarly, for parallel execution, each Dijkstra run is independent after reweighting, making Phase 3 embarrassingly parallel. A multi-threaded or distributed implementation can achieve near-linear speedup on V cores.

Memory optimization is also relevant for massive graphs that do not fit in RAM. An external-memory Johnson can store the reweighted graph on disk and run Dijkstra with an external priority queue. Alternatively, if you only need to detect whether a negative cycle exists and not the full APSP, you can stop after Phase 1, which is simply a negative-cycle detection routine.

Real-World Applications

The johnson reweighting technique finds application in any domain where all-pairs shortest paths are needed on sparse, potentially negatively-weighted networks. Its ability to handle negative weights while remaining efficient on sparse graphs makes it uniquely suited to several practical problems.

In transportation and logistics, road networks are classic sparse graphs where intersections are vertices and road segments are edges. While physical distances are non-negative, costs can be negative when modeling incentives, toll rebates, or profit for delivering goods. A logistics company optimizing delivery routes for a fleet across a city may need the shortest path between every pair of warehouses and drop points. Johnson's algorithm allows them to compute this efficiently without resorting to O(V^3) Floyd-Warshall on a graph with hundreds of thousands of nodes but only a few edges per node.

In financial systems and currency arbitrage, vertices represent currencies and edges represent exchange rates. By taking the negative logarithm of exchange rates, arbitrage opportunities become negative cycles. Before searching for arbitrage, analysts often need all-pairs best conversion rates. Johnson's algorithm not only computes these rates efficiently for sparse currency networks but also simultaneously detects arbitrage cycles via its Bellman-Ford phase. This dual capability is invaluable for high-frequency trading platforms.

Technology and Infrastructure Use Cases

In computer networks and web infrastructure, routing protocols like those used in software-defined networking (SDN) need to compute shortest paths between all pairs of switches or data centers. Link costs may be negative when representing available bandwidth credits or energy savings for using certain paths at off-peak times. Databases that store graph data, such as social networks or knowledge graphs, frequently need to answer many shortest-path queries. Precomputing all-pairs distances with Johnson allows for O(1) query time after the initial O(V*E + V^2 log V) preprocessing, which is ideal for read-heavy workloads.

Other notable applications include VLSI design, where wire lengths and delays are modeled as graphs with possible negative weights due to optimizations, and bioinformatics, where gene regulatory networks have inhibitory (negative) and excitatory (positive) interactions. In each case, the sparsity of the graph makes Johnson preferable to Floyd-Warshall.

Comparison with Alternatives

Choosing the right all-pairs shortest path algorithm depends on graph density, presence of negative weights, and implementation constraints. The johnson reweighting technique is one of several options, each with distinct trade-offs.

Floyd-Warshall is the simplest APSP algorithm to implement, using dynamic programming with three nested loops. It handles negative weights (but not negative cycles) and works for both dense and sparse graphs, but its O(V^3) time and O(V^2) space make it impractical for large sparse graphs. It is, however, extremely cache-friendly and easy to parallelize on GPUs for moderate V.

Running Bellman-Ford from each vertex (V * Bellman-Ford) is the most general approach, handling negative weights and detecting cycles, but its O(V^2 * E) time is almost always too slow. Running Dijkstra from each vertex without reweighting is very fast at O(V*(V+E) log V) but fails completely if any negative edge exists, as Dijkstra's greedy choice becomes invalid.

Johnson strikes the ideal balance for sparse graphs with negative weights: it pays the O(V*E) cost of Bellman-Ford only once, then enjoys the speed of Dijkstra V times. Its only disadvantage is implementation complexity and the requirement that no negative cycles exist, which Floyd-Warshall also shares.

* Using Fibonacci heap; with binary heap O(V*E log V + V^2 log V). The table makes it clear that for sparse graphs where E is much less than V^2, Johnson dominates Floyd-Warshall. For dense graphs where E is close to V^2, Floyd-Warshall's simplicity and lower constant factors often make it the pragmatic choice. The decision should be driven by profiling the actual graph density and the frequency of negative weights.

Common Mistakes and Best Practices

Implementing the johnson reweighting technique correctly requires attention to several subtle pitfalls that can lead to incorrect results or performance degradation. Awareness of these issues separates a working implementation from a robust one.

A frequent mistake is forgetting to add the super source correctly. Some implementations add a super source but fail to connect it to all vertices, or they connect it with non-zero weights. The super source must have a zero-weight edge to every vertex to ensure that h[v] is the true shortest distance from the super source, which guarantees the triangle inequality needed for non-negative reweighting. Another common error is integer overflow or mishandling of infinity. Using a large integer like 10**9 for infinity can overflow when adding negative weights; using float('inf') in Python or properly checking for infinity before addition is safer.

Another pitfall is incorrectly applying the reweighting formula. The formula is w'(u,v) = w(u,v) + h[u] - h[v], not h[v] - h[u]. Reversing the terms will not guarantee non-negativity and will produce incorrect distances. Similarly, the conversion back is δ(u,v) = δ'(u,v) - h[u] + h[v]; swapping signs here is a common bug that passes simple tests but fails on graphs with negative edges.

Developers also often forget that Dijkstra must be run on the reweighted graph, not the original. Running Dijkstra on the original graph after computing potentials defeats the entire purpose. Always verify that your reweighted adjacency list contains w' and that all w' are >= 0 before starting Phase 3. Adding an assertion as shown in the code above is a best practice.

Best Practices for Production Code

For best practices, always handle disconnected graphs gracefully. If a vertex is unreachable from another, the distance should remain infinity, and the conversion formula should not be applied to infinity values (inf - h[u] + h[v] is still inf). Check for infinity before converting. Use adjacency lists for sparse graphs and adjacency matrices only for dense graphs to optimize memory and cache performance.

Test your implementation thoroughly with edge cases: a graph with a single vertex, a graph with no edges, a graph with all positive weights (where Johnson should match repeated Dijkstra), a graph with a negative cycle (where it should raise an error), and a graph with zero-weight cycles. Use property-based testing to compare Johnson's output against Floyd-Warshall on small random graphs for correctness.

Finally, consider numerical stability. If weights are floating-point, small epsilon errors can cause w' to be slightly negative (e.g., -1e-16). Clamping values in the range [-1e-9, 0] to zero prevents Dijkstra from failing due to floating-point artifacts. Document your assumptions about weight types and graph representation clearly for future maintainers.

Interview Questions

Technical interviews frequently probe understanding of the johnson reweighting technique beyond mere memorization. The following questions test conceptual depth, proof understanding, and practical trade-offs.

Q1: Why can't we just add a constant to all edge weights to make them non-negative and then run Dijkstra?

Answer: Adding a constant C to every edge changes the shortest path ordering in a way that depends on the number of edges in the path. A path with many edges will have C added many times, while a path with few edges will have it added fewer times. For example, a path with two edges of weight 2 (total 4) vs. a path with one edge of weight 3 (total 3). If we add C=5 to each edge, the first path becomes (2+5)+(2+5)=14 and the second becomes 3+5=8, preserving order in this case, but consider path A: 1 edge weight 10 vs path B: 10 edges weight 1 each. Original: A=10, B=10 tie. After adding 5: A=15, B=60, now A is much shorter. Johnson's reweighting adds h[u]-h[v] which telescopes and adds a constant per path that depends only on endpoints, not path length, thus preserving shortest path ordering.

Q2: How does Johnson's algorithm detect negative cycles and why is this necessary?

Answer: Negative cycle detection happens in Phase 1 during the Bellman-Ford run from the super source. Bellman-Ford relaxes edges V times; if a relaxation is still possible on the V-th iteration, a negative cycle exists. This is necessary because if a negative cycle is reachable, shortest paths are undefined (distance is -infinity). Furthermore, the proof that w'(u,v) ≥ 0 relies on h satisfying the triangle inequality h[v] ≤ h[u] + w(u,v), which only holds if no negative cycles exist and h represents true shortest distances. If a cycle exists, potentials are invalid and reweighting fails.

Q3: What is the time complexity of Johnson's algorithm and when would you prefer Floyd-Warshall instead?

Answer: With a binary heap, Johnson is O(V*E log V + V^2 log V) and with a Fibonacci heap O(V*E + V^2 log V). Floyd-Warshall is O(V^3). For sparse graphs where E = O(V), Johnson is O(V^2 log V) which is much better than O(V^3). For dense graphs where E = O(V^2), Johnson becomes O(V^3 log V) which is worse than Floyd-Warshall's O(V^3). Therefore, prefer Floyd-Warshall for dense graphs, for very small V where simplicity matters, or when you need a simple GPU-friendly implementation. Prefer Johnson for large, sparse graphs, especially those with negative weights.

Q4: Prove that the reweighted edge weights w'(u,v) are non-negative.

Answer: By definition, h[v] is the shortest distance from the super source s' to v. For any edge (u,v), the shortest path to v cannot be longer than the shortest path to u plus the edge (u,v). This is the triangle inequality for shortest paths: h[v] ≤ h[u] + w(u,v). Rearranging gives w(u,v) + h[u] - h[v] ≥ 0. But the left side is exactly w'(u,v). Therefore w'(u,v) ≥ 0 for all edges. This holds because h values are computed via Bellman-Ford which guarantees this property when no negative cycles exist.

Q5: Can Johnson's algorithm work on undirected graphs?

Answer: Yes, but with a caveat. An undirected edge {u,v} with weight w is typically modeled as two directed edges (u,v,w) and (v,u,w). If w is negative, this immediately creates a negative cycle of length 2: u → v → u with total weight 2*w < 0. Therefore, an undirected graph with any negative edge weight inherently contains a negative cycle and Johnson's algorithm will correctly report that no well-defined shortest paths exist. For undirected graphs to be valid inputs to Johnson, all edge weights must be non-negative, in which case Johnson still works but is unnecessary; repeated Dijkstra without reweighting would suffice.