A common technique in algorithm analysis involves transforming a problem to a more tractable form while preserving its essential structure. This is often achieved by re-weighting elements, such as edges in a graph, using a potential function. The core idea leverages the telescoping property of differences: (\sum_{i=1}^n (a_i - a_{i-1}) = a_n - a_0). This principle can be applied to graph algorithms to handle negative weights or to maintain specific invariants efficiently.

Consider the scenario of maintaining a dynamic deque where operations are performed at both ends. A typical approach is to model the deque using two stacks. When an element is pushed or popped from one end, it affects only one stack. If one stack becomes empty during a deletion, a rebalancing operation redistributes half the elements from the other stack. The correctness of this approach relies on ensuring that the cost of infrequent rebalancing is amortized across many cheap operations.

To analyze the time complexity, we can define a potential function (\phi) representing the absolute difference in the sizes of the two stacks. Each standard push or pop operation changes this potential by at most 1 and incurs a constant cost. The rebalancing operation, which has a linear cost proportional to the stack size, resets the potential to zero. By the amortized analysis formula (\hat{c}i = c_i + \phi_i - \phi{i-1}), the sum of amortized costs telescopes, bounding the total actual cost.

struct DequeHandler {
    vector<long long> leftStack, rightStack;
    void pushFront(int value) {
        leftStack.push_back(value);
    }
    void pushBack(int value) {
        rightStack.push_back(value);
    }
    int popFront() {
        if (leftStack.empty()) {
            rebalance(rightStack, leftStack);
        }
        int val = leftStack.back();
        leftStack.pop_back();
        return val;
    }
    int popBack() {
        if (rightStack.empty()) {
            rebalance(leftStack, rightStack);
        }
        int val = rightStack.back();
        rightStack.pop_back();
        return val;
    }
    void rebalance(vector<long long>& src, vector<long long>& dest) {
        int mid = src.size() / 2;
        dest.assign(src.rbegin(), src.rbegin() + mid);
        src.erase(src.end() - mid, src.end());
        reverse(dest.begin(), dest.end());
    }
};

Applying a similar re-weighting concept to graph theory leads to Johnson's algorithm for all-pairs shortest paths. The goal is to enable the use of Dijkstra's algorithm, which requires non-negative edge wieghts, on graphs that may contain negative weights. We assign a potential (h(v)) to each vertex and redefine the weight of an edge ( (u, v) ) as ( w'(u,v) = w(u,v) + h(u) - h(v) ). For any path from (s) to (t), the new path weight becomes ( w'(path) = w(path) + h(s) - h(t) ). Since (h(s) - h(t)) is constant for the pair, the shortest path structure is preserved.

The challenge is to choose potentials that make all re-weighted edges non-negative, i.e., ( w(u,v) + h(u) - h(v) \ge 0 ), which rearranges to ( h(v) \le h(u) + w(u,v) ). This is precisely the triangle inequality for shortest path distances. Therefore, we can compute a feasible set of potentials by finding the shortest distance from a new source vertex connected to all original vertices with zero-weight edges. This initial step requires solving a single-source shortest path problem on a graph that may have negative edges, for which an algorithm like the Bellman-Ford algorithm is suitable.

vector<long long> computePotentials(const Graph& g) {
    int V = g.vertexCount();
    vector<long long> dist(V + 1, INF);
    dist[V] = 0;
    for (int i = 0; i < V; ++i) {
        g.addEdge(V, i, 0); // Temporary auxiliary edge
    }
    // Run Bellman-Ford from the auxiliary vertex V
    for (int iter = 0; iter < V; ++iter) {
        bool updated = false;
        for (auto& edge : g.getAllEdges()) {
            if (dist[edge.from] != INF && dist[edge.to] > dist[edge.from] + edge.weight) {
                dist[edge.to] = dist[edge.from] + edge.weight;
                updated = true;
            }
        }
        if (!updated) break;
    }
    // Remove the auxiliary edges and return potentials for original vertices
    vector<long long> potential(dist.begin(), dist.begin() + V);
    return potential;
}

vector<long long> johnsonsAllPairs(Graph& g) {
    vector<long long> h = computePotentials(g);
    vector<long long> results;
    for (int src = 0; src < g.vertexCount(); ++src) {
        // Dijkstra's algorithm using re-weighted edges
        priority_queue<pair<long long, int>> pq;
        vector<long long> dist(g.vertexCount(), INF);
        dist[src] = 0;
        pq.push({0, src});
        while (!pq.empty()) {
            auto [d, u] = pq.top(); pq.pop();
            if (-d != dist[u]) continue;
            for (auto& e : g.adj[u]) {
                long long newWeight = e.weight + h[u] - h[e.to];
                if (dist[e.to] > dist[u] + newWeight) {
                    dist[e.to] = dist[u] + newWeight;
                    pq.push({-dist[e.to], e.to});
                }
            }
        }
        // Adjust distances back to original weights
        for (int v = 0; v < g.vertexCount(); ++v) {
            if (dist[v] != INF) dist[v] = dist[v] - h[src] + h[v];
        }
        // Store or process results for this source
        results.insert(results.end(), dist.begin(), dist.end());
    }
    return results;
}

This re-weighting technique is also fundamental to the Primal-Dual method for solving the minimum-cost flow problem. The Successive Shortest Path (SSP) algorithm repeatedly augments flow along the cheapest path from source to sink, which may introduce negative-cost residual edges. Maintaining vertex potentials allows Dijkstra's algorithm to be used instead of a Bellman-Ford variant for each shortest path computation.

Initially, all potentials are set to zero. After each shortest path computation using the adjusted costs ( c'(u,v) = c(u,v) + \pi(u) - \pi(v) ), the potentials are updated: ( \pi'(v) = \pi(v) + d(v) ), where (d(v)) is the shortest distance from the source under the adjusted costs. This update ensures that edges on the shortest path tree satisfy ( c'(u,v) = 0 ) and that newly created reverse edges in the residual network also have non-negative adjusted cost.

struct MinCostFlowSolver {
    struct Edge { int to, rev, cap, cost; };
    vector<vector<Edge>> graph;
    vector<long long> potential, dist;
    vector<pair<int, int>> parent;

    void addEdge(int u, int v, int cap, int cost) {
        graph[u].push_back({v, (int)graph[v].size(), cap, cost});
        graph[v].push_back({u, (int)graph[u].size() - 1, 0, -cost});
    }

    bool dijkstra(int source, int sink) {
        dist.assign(graph.size(), INF);
        parent.assign(graph.size(), {-1, -1});
        priority_queue<pair<long long, int>> pq;
        dist[source] = 0;
        pq.push({0, source});
        while (!pq.empty()) {
            auto [d, u] = pq.top(); pq.pop();
            if (-d != dist[u]) continue;
            for (int i = 0; i < graph[u].size(); ++i) {
                Edge& e = graph[u][i];
                if (e.cap <= 0) continue;
                long long newCost = e.cost + potential[u] - potential[e.to];
                if (dist[e.to] > dist[u] + newCost) {
                    dist[e.to] = dist[u] + newCost;
                    parent[e.to] = {u, i};
                    pq.push({-dist[e.to], e.to});
                }
            }
        }
        return dist[sink] < INF;
    }

    pair<int, long long> computeFlow(int source, int sink, int maxFlow) {
        potential.assign(graph.size(), 0);
        int flow = 0;
        long long totalCost = 0;
        while (flow < maxFlow && dijkstra(source, sink)) {
            for (int v = 0; v < graph.size(); ++v) {
                if (dist[v] < INF) potential[v] += dist[v];
            }
            int aug = maxFlow - flow;
            for (int v = sink; v != source; v = parent[v].first) {
                int u = parent[v].first;
                Edge& e = graph[u][parent[v].second];
                aug = min(aug, e.cap);
            }
            for (int v = sink; v != source; v = parent[v].first) {
                int u = parent[v].first;
                Edge& e = graph[u][parent[v].second];
                e.cap -= aug;
                graph[e.to][e.rev].cap += aug;
            }
            flow += aug;
            totalCost += (long long)aug * potential[sink];
        }
        return {flow, totalCost};
    }
};

In summary, the technique of applying a potential-based re-weighting, grounded in the telescoping difference property, provides a unified framework for designing efficient algorithms for dynamic data structures, all-pairs shortest paths, and minimum-cost flow. It transforms problems to eliminate negative weights, enabling the use of more efficient subroutines like Dijkstra's algorithm, while preserving the correctness of the solution through careful maintenance of invariants.