In this tutorial I'll introduce potentials as it applies to directed graphs and discuss a few of its applications. I haven't seen many resources about this topic, so I decided to write one.

Prerequisites:

• Shortest path algorithms (Dijkstra and Bellman-Ford)
• For the Min Cost Max Flow section, you should be familiar with Ford-Fulkerson. But you can benefit from this blog with just the Johnson's Algorithm section.

Introduction

For notation, let's say there is a weighted, directed graph $$$G=(V,E)$$$. Let $$$n=|V|$$$ and $$$m=|E|$$$. For simplicity, let's assume there are no loops or multiple edges between the same pair of nodes in the same direction. For an edge $$$u\to v$$$, we will use $$$w(u\to v)$$$ to denote its weight.

Let's motivate the idea of a potential, so the definition doesn't seem to come out of nowhere. In shortest paths, you may be aware that negative edges create a lot of issues. First, it's possible that negative cycles exist. In that case, it's possible for a path to have arbitrarily small weight, and we say that $$$\mathrm{dist}(u\to v)=-\infty$$$. (By the way, we allow a path to revisit vertices. If we required a simple path, then it's NP-complete.)

Even if there are no negative cycles, the negative edges are still problematic for us. Dijkstra's algorithm can give incorrect results, and we typically use Bellman-Ford instead, which has a worse complexity. Dijkstra's is $$$O(m\log n)$$$ while Bellman-Ford is $$$O(mn)$$$. Technically, Dijkstra's algorithm can be improved to $$$O(m+n\log n)$$$ with Fibonacci heaps, but it's not very important for the purposes of this blog. I mention it anyway in case you're confused why other resources have a different complexity.

One possible idea to deal with negative edges is to "reweigh" the graph so that all weights are non-negative, and it still encodes the information of shortest paths in the original graph. Obviously, we can't just replace the weights with whatever we want. One way we can modify weights is to pick a vertex $$$v$$$, increase the weights of incoming edges to $$$v$$$ by some real value $$$x$$$, and decrease the weights of outgoing edges from $$$v$$$ by the same amount $$$x$$$. This way, any path that goes through $$$v$$$ will have the same weight as before. Therefore, the only affected paths are the ones that begin or end at $$$v$$$. But we can observe that any path beginning or ending in $$$v$$$ will just be offset by $$$x$$$, and a shortest path will remain the shortest.

Now, we have the motivation to define a potential. The idea is that we want to apply this kind of vertex offset for all vertices independently in such a way that all the new weights are non-negative.

Definition: A function $$$p:V\to \mathbb{R}$$$ is called a potential of graph $$$G$$$ if for every edge $$$(u\to v)\in E$$$, it holds that $$$w(u\to v)+p(u)-p(v)\ge 0$$$.

Note that if a graph has a negative cycle, then you cannot create a potential for it. This is because the weight of a cycle is unchanged by the reweighing.

Johnson's Algorithm

Given our graph $$$G$$$, we would like to compute length of the shortest path from $$$u$$$ to $$$v$$$, for all pairs $$$(u, v)$$$. For simplicity, let's assume there are no negative cycles in the graph. Perhaps the best algorithm you know about for this problem is Floyd-Warshall, which works in $$$O(n^3)$$$. It works correctly for negative edges, which you might not have known about.

Johnson's Algorithm solves this problem more efficiently for sparse graphs, and it uses the following steps:

1. Compute a potential $$$p$$$ for the graph $$$G$$$.
2. Create a new weighting $$$w'$$$ of the graph, where $$$w'(u\to v)=w(u\to v)+p(u)-p(v)$$$.
3. Compute all-pairs shortest paths $$$\mathrm{dist}'$$$ with the new weighting.
4. Convert the distances back to the original graph, with the equation $$$\mathrm{dist}(u\to v)=\mathrm{dist}'(u\to v)-p(u)+p(v)$$$.

We need to go into more detail about how steps 1 and 3 can be done. Step 3 is easier to understand, so let's address it first. The weighting $$$w'$$$ is all non-negative, so we can use Dijkstra's algorithm to get correct distances. We simply run Dijkstra's algorithm once for every vertex $$$u$$$, to get the distances from $$$u$$$ to every other vertex. Since we run Dijkstra's algorithm $$$n$$$ times, and each time takes $$$m\log n$$$, the complexity for this stage is $$$O(nm\log n)$$$. Technically, it can be improved to $$$O(n(n\log n+m))=O(n^2\log n+nm)$$$ if you use Fibonacci heaps.

Now, how do we do step 1? The key idea is that shortest path values themselves satisfy the requirement of a potential! In fact, let's fix some vertex $$$s$$$, and assign $$$p(v)=\mathrm{dist}(s\to v)$$$ for all vertices $$$v$$$. Assume for contradiction that $$$p$$$ is not a potential. Then there is some edge $$$u\to v$$$ such that $$$w(u\to v)+p(u)-p(v)<0$$$. This means that $$$\mathrm{dist}(s\to v)>\mathrm{dist}(s\to u)+w(u\to v)$$$. This means that if we take the shortest path from $$$s$$$ to $$$u$$$, then take the edge from $$$u$$$ to $$$v$$$, the total weight will be smaller than the shortest distance from $$$s$$$ to $$$v$$$. Clearly, this is impossible, so $$$p$$$ is in fact a potential.

Actually, I lied to you. The above proof is only correct if the chosen vertex $$$s$$$ can reach all vertices $$$v$$$. Otherwise, we would have infinite potentials which is not allowed by the definition. But we're almost there. Let's simply create a brand new vertex $$$s$$$, and create an edge $$$s\to v$$$ with weight $$$0$$$ for every vertex $$$v$$$. We will define the potential based on the shortest distance from $$$s$$$, and it will be correct. Note that the property of a potential is still valid if we delete some vertices and edges, so it's not a problem to remove $$$s$$$ after we compute the potential.

Now, you might be thinking, "wait, I thought the point of a potential is to help us compute shortest paths, and now you're telling me we need to use shortest paths to compute the potential? I want my upvote back!" But remember, we're trying to compute all-pairs shortest paths. Running an algorithm like Bellman-Ford from every starting vertex would be expensive. But here, we're only running such an algorithm once, from the new vertex $$$s$$$. Then we use a more efficient algorithm (Dijkstra) for the all-pairs part. So for this step 1, we just run Bellman-Ford once on the graph with the new vertex $$$s$$$. The complexity of step 1 is $$$O(nm)$$$.

Overall, step 3 is the bottleneck and Johnson's algorithm has complexity $$$O(nm\log n)$$$ (or $$$O(n^2\log n + nm)$$$ if you use Fibonacci heap).

Min Cost Max Flow

I will present the minimum cost maximum flow (MCMF) problem, show how to solve it, then show how potentials can make it faster. If you want formal proofs, I recommend resources below. My proofs here will be business casual.

We are given a directed graph $$$G=(V, E)$$$. There are two special nodes $$$s$$$ and $$$t$$$, called the source and sink. Every edge $$$u\to v$$$ has a capacity $$$c(u\to v)$$$ and a cost $$$w(u\to v)$$$. A flow is defined as an assignment $$$f:E\to \mathbb{R}$$$ such that:

• For every edge $$$u\to v$$$, the flow sent along this edge is non-negative and does not exceed the capacity. Formally, $$$0\le f(u\to v)\le c(u\to v)$$$.
• For every vertex $$$u$$$ ($$$u\ne s$$$, $$$u\ne t$$$), flow-out equals flow-in. Formally,

The value of a flow is defined as $$$\sum\limits_{u:(s\to u)\in E}f(s\to u)$$$. The cost of a flow is defined as $$$\sum\limits_{(u\to v)\in E}f(u\to v)w(u\to v)$$$.

The maximum flow problem simply asks to maximize the value of the flow. The MCMF problem asks us to find the minimum cost flow among all flows with the maximum possible value.

Let's recall how to solve the maximum flow problem with Ford-Fulkerson. We iteratively send flow from $$$s$$$ to $$$t$$$ by finding an augmenting path, which is a path of edges from $$$s$$$ to $$$t$$$ using only edges that are below full capacity. Also, we include reversed edges that allow us to send flow "back". We can find such a path with DFS.

In MCMF, we do almost the same thing, except that we must find the shortest path each iteration. A forward edge $$$u\to v$$$ has weight $$$w(u\to v)$$$ and the corresponding back edge has weight $$$-w(u\to v)$$$. We ignore edges at full capacity (and back edges whose corresponding forward edge has no flow to send back).

Since this graph has negative edges, we might use Bellman Ford each iteration. But with potentials, we can do better. We already know that if we're given a potential for the graph, then the shortest path can be computed easily with Dijkstra. But when we send flow along an augmenting path, it changes which edges are at full capacity, which can make the potential invalid for the next iteration.

How can we compute the potential for the next iteration more efficiently than running Bellman-Ford every time? It turns out that we can use the shortest path results from the Dijkstra to assign the potentials for the next iteration for free. This works because the shortest distances create a potential for the edges involved, as mentioned in the Johnson's algorithm section. So we just need to check that the edges that change from sending flow do not create an issue. Suppose an edge becomes full capacity. Then it is removed from our graph for shortest path computations, and it cannot make the potential invalid. Suppose an edge was at full capacity but not after sending flow along the augmenting path. In this case, the reversed edge satisfied the inequality before sending flow, which automatically means this edge satisfies it (since $$$w(u\to v)=-w(v\to u)$$$).

Now, given a potential for one iteration we can compute it for the next iteration for free. But what about the first iteration? In many cases, the costs are all non-negative and we can just use $$$p(u)=0$$$ for the potential. Otherwise if there are no negative cycles, we can run Bellman-Ford to get the initial potential. I'm not aware of how to deal with negative cost cycles, and I haven't yet seen it appear in a problem. If you're knowledgeable about negative cycles in MCMF, I'd love to hear about it in the comments.

Ignoring a possible Bellman-Ford or similar to compute the initial potential, the complexity is $$$O(F(m\log n))$$$. With Fibonacci heap, you get $$$O(F(m + n\log n))$$$. Note that for very dense graphs, it's optimal to do the simple $$$O(n^2)$$$ Dijkstra algorithm which doesn't use any heap.

template<typename Cap, typename Cost>
struct mcmf {
    struct edge {
        int v;
        Cap cap, flow;
        Cost cost;
    };
    int n;
    vector<edge> e;
    vector<vector<int>> g;
    vector<Cost> dist, pot;
    vector<Cap> f;
    vector<bool> vis;
    vector<int> par;
    bool n2dijkstra = false;
    mcmf(int n) : n(n), g(n), dist(n), pot(n), f(n), vis(n), par(n) {}
    void add_edge(int u, int v, Cap cap, Cost cost) {
        int k = e.size();
        e.push_back({v, cap, 0, cost});
        e.push_back({u, cap, cap, -cost});
        g[u].push_back(k);
        g[v].push_back(k ^ 1);
    }
    pair<Cap, Cost> solve(int s, int t) {
        Cap flow = 0;
        Cost cost = 0;
        while(true) {
            fill(dist.begin(), dist.end(), numeric_limits<Cost>::max());
            fill(vis.begin(), vis.end(), false);
            dist[s] = 0;
            f[s] = numeric_limits<Cap>::max();
            if(n2dijkstra) {
                while(true) {
                    int x = -1; Cost d = numeric_limits<Cost>::max();
                    for(int i = 0; i < n; i++) {
                        if(!vis[i] && dist[i] < d) {
                            x = i;
                            d = dist[x];
                        }
                    }
                    if(x == -1) break;
                    vis[x] = true;
                    for(int i : g[x]) {
                        Cost d2 = d + e[i].cost + pot[x] - pot[e[i].v];
                        if(!vis[e[i].v] && e[i].flow < e[i].cap && d2 < dist[e[i].v]) {
                            dist[e[i].v] = d2;
                            f[e[i].v] = min(f[x], e[i].cap - e[i].flow);
                            par[e[i].v] = i;
                        }
                    }
                }
            }else {
                priority_queue<pair<Cost, int>, vector<pair<Cost, int>>, greater<>> Q;
                Q.push({0, s});
                while(!Q.empty()) {
                    Cost d; int x;
                    tie(d, x) = Q.top(); Q.pop();
                    if(vis[x]) continue;
                    vis[x] = true;
                    for(int i : g[x]) {
                        Cost d2 = d + e[i].cost + pot[x] - pot[e[i].v];
                        if(!vis[e[i].v] && e[i].flow < e[i].cap && d2 < dist[e[i].v]) {
                            dist[e[i].v] = d2;
                            f[e[i].v] = min(f[x], e[i].cap - e[i].flow);
                            par[e[i].v] = i;
                            Q.push({d2, e[i].v});
                        }
                    }
                }
            }
            if(!vis[t]) break;
            for(int i = 0; i < n; i++) {
                dist[i] += pot[i] - pot[s];
            }
            cost += dist[t] * f[t];
            flow += f[t];
            int x = t;
            while(x != s) {
                e[par[x]].flow += f[t];
                e[par[x] ^ 1].flow -= f[t];
                x = e[par[x] ^ 1].v;
            }
            dist.swap(pot);
        }
        return {flow, cost};
    }
};

Resources

• Johnson's Algorithm (Wikipedia)
• Hungarian Algorithm (Wikipedia) Special case of MCMF with potentials
• Minimum Cost Flow without potentials (cp-algorithms) I believe their complexity analysis is wrong, but otherwise a good resource.

Practice Problems

• Johnson's Algorithm
  • https://codeforces.me/gym/101498/problem/L
• MCMF
  • https://cses.fi/problemset/task/2121
  • https://cses.fi/problemset/task/2129
  • https://cses.fi/problemset/task/2130