本篇文章介绍了，稀疏图上的Johnson算法的详解。需要的朋友参考下

算法步骤简述： 1.计算图G加入新结点后的图G’，加入的新结点0到所有原结点之间距离为0，同时形成新的边集E’； 2.使用Bellman-Ford算法处理G’，并形成0结点到各结点的最小距离d。 3.如果Bellman-Ford算法检测出有负权回路则提示FALSE并退出，否则继续。 4.对所有G’中的顶点v,根据0结点到v的最小距离，将h(v)设置为这个值。 5.对所有的边w(u,v)，权值更新为w(u,v)+h(u)-h(v) 6.对图G中所有结点运行Dijkstra算法计算与其他顶点最短距离