算法: Johnson 算法是什么?
来源:简书 发布时间:2020-05-21 14:24:29

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

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,欢迎访问。

undefined

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 h = bellman_ford(graph, s);

//重新计算除s以外的其它点权重

ArrayList 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));

}

}

作者:某昆

猜你喜欢