一，Johnson算法的思想
二，新权重的确定
我们定义新权重w'(u,v)=w(u,v)+h(u)-h(v)，满足两个性质：一是对于所有结点对(u,v)，路径p是使用原权重函数w时从结点u到v的一条最短路径，当且仅当p是在使用新权重函数w’时从u到v的一条最短路径，二是新权重为非负值。
三，Johnson算法介绍
四，Johnson算法的伪代码
JOHNSON(G,w)
1. compute G’,where G’.V=G.V∪{s},G’.E=G.E∪{(s,v):v∈G.V},w(s,v)=0 for all v∈G.V
2. if BELLMAN_FORD(G’,w,s)==FALSE
3. print”the input graph contains a negative-weight cycle”
4. else for each vertex v∈G’.V
5. set h(v) to the value of δ(s,v) computed by the Bellman-Ford algorithm
6. for each edge(u,v)∈G’.E
7. w'(u,v)=w(u,v)+h(u)-h(v)
8. let D=(duv)be a new n*n matrix
9. for each vertex u∈G.V
10. run DIJKSTRA(G,w’,u) to compute δ'(u,v) for all v∈G.V
11. for each vertex v∈G.V
12. duv=δ'(u,v)+h(v)-h(u)
13. return D
第1行中，在图G中加入结点S，并让S到各结点的权重为0；第2行中，用Bellman-Ford算法计算S到各结点的最短路径，如果返回false，说明有负环，如果为true，继续下面的语句；第4-12行中，有四个循环，第一个循环将每个结点的h值算出，也就是前面BF算法算出来的最短路径，第二个循环将每条边的权重根据新权重确定方法重新赋值，随后创建最终的最短路径权重矩阵D，第三个循环对每个结点进行一次Dijkstra算法计算每个结点到其他所有结点的最短路径，并让duv等于算出来的最短路径减去前面加上的h(u)-h(v)；第13行返回最短路径权重矩阵D
五，Johnson算法的复杂度
时间复杂度：O(V²lgV+VE)
六，Johnson算法的代码
这里用了二维数组表示矩阵
int Johnson_Algo(Graph * graph) { int D; D = (int )malloc(NODESIZE * sizeof(int *)); for (int i = 0; i < NODESIZE; i++) { D[i] = (int *)malloc(NODESIZE * sizeof(int)); } Graph *g = buildGraph_Johnson(graph); if (Bellman_Ford_Algo(g, g->getNodeList().back()) == false) { cout << "存在负边环"; } else { for (int i = 0; i < g->getNodeList().size()-1; i++) { g->getNodeList()[i]->setH(g->getNodeList()[i]->getD()); } for (int j = 0; j < g->getEdgeList().size(); j++) { Edge *edge = g->getEdgeList()[j]; edge->setW(edge->getW() + edge->getStartNode()->getH() - edge->getEndNode()->getH()); } for (int u = 0; u < graph->getNodeList().size(); u++) { Dijkstra_Algo(graph, graph->getNodeList()[u]); for (int v = 0; v < graph->getNodeList().size(); v++) { D[u][v] = graph->getNodeList()[v]->getD()+ graph->getNodeList()[v]->getH()- graph->getNodeList()[u]->getH(); } } } return D; }发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/216122.html原文链接：https://javaforall.net
