前言
上一篇文章已经阐述了Floyd-Warshall算法，适用于存在负权重路径的稠密图。本文讲述的算法适用于稀疏图。
全源最短路径求解其实是单源最短路径的推广，求解单源最短路径的两种算法时间复杂度分别为：
- Dijkstra 单源最短路径算法：时间复杂度为 O(E + VlogV)，要求权值非负；
- Bellman-Ford 单源最短路径算法：时间复杂度为 O(VE)，适用于带负权值情况；
如果对全图顶点遍历，使用Dijkstra 算法，时间复杂度将变成O(VE + V2logV)，看起来优于 Floyd-Warshall 算法的 O(V3)。不过，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));
}
}