Johnson

What is Johnson

Johnson is used to solve the all-pairs shortest path with the strenths of Dijkstra and Bellman Ford.

How does it work

For Dijkstra, it is fast but can not solve the graph with negative edge weight. For Bellman-Ford, can solve it but too slow. For all-pairs shortest path, we can run Dijkstra on every node. So we can combine the speed of Dijkstra and the solution of negative edge weight of Bellman Ford. Because of Dijkstra, we must use Bellman Ford to relax all edges and ensure that the graph have no negative edge weight. To achieve this imagination, we will use a potential function and name it $p$.

Now we need to eliminate negative edge weights. Using the potential function $p$, we introduce a $w’(u,v)$, which satisfies $w’(u,v) = w(u,v) + h(u) - h(v) \ge 0$ holding true for all. By transposing the terms we get $h(v) \le h(u) + w(u, v)$, which holds true universally. It is the final result form of Bellman Ford. And because we want to solve the all-pairs shortest path, we will encounter the non-strongly connected graph. Setting a virtual node named s, it will connect all nodes directly and its out-edges weight is 0 always.

After introducing the virtual node s, we need to compute the potential function $p$, and check the negative weight circles. According to the function of $p$ and the function of Bellman Ford, we will use Bellman Ford to compute the $p$ and check the negative weight circles. And we need another adjacency list to contain the new weight. Then we can run Dijkstra on this adjacency list. When the Dijkstra ended, will need to restore the original edge weights.

Inplement in c++

vector<int> dist;
vector<int> p_dist;
vector<vector<pair<int, int>>> adj;
void init(int dots)
{
    p_dist = vector<int>(dots + 1, INT_MAX);
    adj = vector<vector<pair<int, int>>>(dots + 1); 
}

bool Bellman_Ford(int dots, int start)
{
    p_dist[start] = 0;
    for(int k = 0; k < dots - 1; ++k)
    {
        for(int u = 0; u <= dots; ++u)
        {
            if(p_dist[u] == INT_MAX) continue;
            for(auto [v, w] : adj[u])
            {
                if(p_dist[v] > p_dist[u] + w) p_dist[v] = p_dist[u] + w;
            }
        }
    }
    for(int u = 0; u <= dots; ++u)
    {
        if(p_dist[u] == INT_MAX) continue;
        for(auto [v, w] : adj[u])
        {
            if(p_dist[v] > p_dist[u] + w) return false;
        }
    }
    return true;
}
void Dijkstra(int start, vector<vector<pair<int, int>>>& n_adj)
{
    dist = vector<int>(n_adj.size(), INT_MAX);
    dist[start] = 0;
    vector<bool>visit(n_adj.size(), false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push({0, start});
    while(!pq.empty())
    {
        auto [d, u] = pq.top(); pq.pop();
        if(visit[u]) continue;
        visit[u] = true;
        for(auto [v, w] : n_adj[u])
        {
            if(dist[u] == INT_MAX) continue;
            if(dist[v] > w + dist[u])
            {
                dist[v] = w + dist[u];
                pq.push({dist[v], v});
            }
        }
    }
}
vector<vector<int>> Johnson(int dots)
{
    vector<vector<int>> empty;
    vector<vector<pair<int, int>>> n_adj(dots + 1); 
    for(int i = 1; i <= dots; ++i) adj[0].push_back({i, 0}); //Set the virtual node.
    if(!Bellman_Ford(dots + 1, 0)) return empty;
    for(int u = 1; u <= dots; ++u)
    {
        for(auto [v, w] : adj[u])
        {
            int new_w = w + p_dist[u] - p_dist[v];
            n_adj[u].push_back({v, new_w});
        }
    }
    vector<vector<int>> result(dots + 1, vector<int>(dots + 1, INT_MAX));
    for(int u = 1; u <= dots; ++u)
    {
        Dijkstra(u, n_adj);
        for(int v = 1; v <= dots; ++v)
        {
            if(u == v) result[u][v] = 0;
            else if(dist[v] == INT_MAX) result[u][v] = INT_MAX;
            else result[u][v] = dist[v] - p_dist[u] + p_dist[v]; 
        }
    }
    return result;
}

The explanation of result[u][v] = dist[v] - p_dist[u] + p_dist[v];

$\text{dist}[v] = \min \sum w’(x, y)
= \min \sum [w(x, y) + p_dist[x] - p_dist[y]]$

And $\sum (p_dist[x] - p_dist[y]) = p_dist[x] - p_dist[x_1] + p_dist[x_1] - p_dist[x_2] + \dots + p_dist[x_k] - p_dist[y] = p_dist[x] + p_dist[y] = p_dist[u] + p_dist[v]$. (First x and first y is u and v)

Time complexity