而且在运行Bellman-Ford算法的时候，正好可以侦测出图中是否有负环。

伪代码：
JOHNSON(g)
  let s be new Vertex
  g.insert(s)
  if BELLMAN-FORD(g,s) == flase
    there is a negative cycle in graph
  else
    for v equal to every vertex in g
      h(v) = min(v~>s)
    end
    for (u,v) equal to every edge in graph
      w’(u,v) = w(u,v) + h(u) - h(v)
    end
    let result be new Table
    for u equal to every vertex in g
      DIJSKTRA(g,u)
      for v equal to every vertex in g
        result[u][v] = min(u~>v) + h(v) - h(u)
      end
    end
  return result

时间复杂度:O(V?Elog2V+V2log2V+V?E)，V表示顶点的个数，E表示边的个数

证明了这么多的算法正确性，可以看到，证明是有技巧的，常用的只有三个方法，反证法、结构归纳法、Cut-And-Paste法。

经过图论的探讨，便可以理解算法与数学之间紧密的联系。解决问题要对问题本身的特征、属性进行总结或者提炼。有时要对问题进行相应的转化。然后根据问题的特征、性质推导出定理。再将定理拓展，提出推论。最后，算法就在灯火阑珊处了。

这感觉就像，不是你找到了合适的算法。而是合适的算法找到了你。