强森算法求两点最短路径的基本流程及代码实现

对于强森算法，给定的一个图中，算法首先会构造一个新的节点s，然后从新构造的这个节点引出多条边分别连通图中的每一个节点，这些边的长度一开始是被设置为0的，然后使用贝尔曼-福德算法进行计算，算出从s到图中每一个节点的最短路径。

而在运行贝尔曼-福德算法的过程中如果发现给定的图存在负数环，那么就要停止后续的计算，因为含有负数的环的图不存在最短路径，而如果给定的图是不存在负数的环的，那么此时就已经得到了s到所有节点的最短路径，那么使用公式来修改每条边的长度，由此就可以将图中的所有负数的边都修正成为正数的边。

又遍历给定的图中的所有节点，运用迪杰斯特拉算法来计算其到其他节点的最短路径，然后对结果依据公式来进行逆运算，也就是将所得的结果加入边就可以得到边长没有修改的时候所对应的最短路径。

强森算法使用python实现的代码如下：

def johnson(vertex_list ,edge_vertex, edges): s = len(vertex_list) edge_vertex[s] = vertex_list.copy() for v in vertex_list: #新增节点到其他节点的边长为0 edges[(s, v)] = 0 vertex_list.append(s) bellman_ford_distance = bellman_ford(s, vertex_list, edges) #计算新节点到其他所有节点的最短距离 print("shortest path from new point to other points are: ", bellman_ford_distance) if bellman_ford_distance == None: #图中含有负环 print("graph contains negative circle"