Johnson 全源最短路径算法

前言

上一篇文章已经阐述了Floyd-Warshall算法，适用于存在负权重路径的稠密图。本文讲述的算法适用于稀疏图。

全源最短路径求解其实是单源最短路径的推广，求解单源最短路径的两种算法时间复杂度分别为：

• Dijkstra 单源最短路径算法：时间复杂度为 O(E + VlogV)，要求权值非负；
• Bellman-Ford 单源最短路径算法：时间复杂度为 O(VE)，适用于带负权值情况；

如果对全图顶点遍历，使用Dijkstra 算法，时间复杂度将变成O(VE + V²logV)，看起来优于 Floyd-Warshall 算法的 O(V³)。不过，Dijkstra 算法要求权值重不能为负。

Johnson 算法能调整权重为负的图，使之能够使用Dijkstra 算法。

re-weight

以下图为例，Johnson 算法对下图进行re-weight操作，使权重不为负，并且re-weight后，计算出来的最短路径仍然正确。

首先，新增一个源顶点 ，并使其与所有顶点连通，新边赋权值为 0，如下图所示。

接下来重新计算新增顶点到其它顶点的最短路径，利用单源最短路径算法，图中存在负权重节点，使用bellman ford算法，计算新增节点到其它节点的最短路径 h[]，然后使用如下公式对所有边的权值进行 "re-weight"：

w(u, v) = w(u, v) + (h[u] - h[v]).

对于此公式的证明请参考算法导论一书。

现在除新增结点外，其它结点的相关边权重值都已经为正数了，可以将新增结点删除，对其它结点使用Dijkstra 算法了。

实现

Johnson 算法比Floyd-warshall算法更容易理解一些，实现较简单，代码如下。本博中所有代码均可见本人的github，欢迎访问。

public void johnson(MatrixGraph graph){
    Vertex s = new Vertex("s");
    graph.addVertex(s);
    for (int i = 0; i < graph.mList.size(); i++) {
        graph.addEdge(s, graph.mList.get(i), 0);
    }
    //计算s点到其它点的最短距离
    ArrayList<Integer> h = bellman_ford(graph, s);
    //重新计算除s以外的其它点权重
    ArrayList<MatrixEdge> edges = new ArrayList<>();
    MatrixEdge temp = null;
    for (int i = 0; i < VERTEX_NUM; i++) {
        for (int j = 0; j < VERTEX_NUM; j++) {
            temp = graph.mEdges[i][j];
            if (temp != null && temp.v1 != s && temp.v2 != s) {
                edges.add(temp);
            }
        }
    }
    
    System.out.println(" -------- ");
    
    for (int i = 0; i < edges.size(); i++) {
        temp = edges.get(i);
        temp.weight = temp.weight + h.get(graph.mList.indexOf(temp.v1)) - h.get(graph.mList.indexOf(temp.v2));
        System.out.print(temp + " | ");
    }
    System.out.println();
    System.out.println(" --------- ");
    
    graph.removeVertex(s);
    
    //根据重新计算的非负权重值，遍历调用dijkstra算法
    for (int i = 0; i < graph.mList.size(); i++) {
        dijkstra(graph, graph.mList.get(i));
    }
}