今天跟大家唠唠我这几天刚搞定的 johnson 算法，这玩意儿刚开始看的时候，真有点头大，不过啃下来之后，感觉还挺有意思的。
事情是这样的，最近在搞图相关的算法，然后就碰到求所有节点对之间最短路径的问题。一开始想着直接用 Floyd-Warshall 算法一把梭，简单粗暴。但仔细一看，复杂度是 O(V^3)，V 是顶点数，这数据一大，跑起来就费劲。而且我这回处理的图是稀疏图，用 Floyd-Warshall 就有点浪费。
然后就想到 Johnson 算法，这玩意儿是专门解决稀疏图上的全源最短路径问题的，而且还能处理带负权边的图，前提是没有负权环。这不正是我需要的嘛
第一步，我先得搞明白 Johnson 算法的原理。
- 核心思想是 就是把带有负权边的图，通过重新赋权值的方式，转换成所有边权重都是非负的图。
- 为什么要这么做？ 因为 Dijkstra 算法只能处理非负权边的图，而 Dijkstra 算法的复杂度比 Bellman-Ford 算法低，所以 Johnson 算法就先用 Bellman-Ford 算法处理负权边，再用 Dijkstra 算法计算最短路径。
第二步，开始动手实现。
我用 Bellman-Ford 算法来计算每个节点到其他节点的最短路径，得到一个势函数（potential function），这玩意儿就是用来重新赋权值的关键。具体步骤如下：
- 新建一个虚拟节点，连接到图中的所有节点，权重都设为 0。
- 用 Bellman-Ford 算法计算从虚拟节点到所有节点的最短路径。
- 如果发现负权环，直接GG，Johnson 算法没法处理。
- 否则，就得到每个节点的势函数 h[i]。
我根据势函数重新计算图中每条边的权重。假设原来边 (u, v) 的权重是 w(u, v)，那么新的权重就是 w'(u, v) = w(u, v) + h[u] - h[v]。可以证明，这样重新赋值后，所有边的权重都是非负的。
就是对每个节点跑一遍 Dijkstra 算法，计算它到其他节点的最短路径。由于所有边的权重都是非负的，Dijkstra 算法就能派上用场。
第三步，代码调试。
这部分是最痛苦的，各种边界情况，各种小bug，真是防不胜防。我debug好久，才把代码跑通。期间还参考网上的一些代码，但是发现很多代码都写得比较复杂，不容易理解。我就自己重新写一遍，尽量让代码更简洁易懂。
第四步，性能测试。
我用一些随机生成的图做性能测试，发现 Johnson 算法在稀疏图上的表现确实比 Floyd-Warshall 算法好很多。数据量越大，优势越明显。
这回实践 Johnson 算法，让我对图算法有更深入的理解。虽然过程有点曲折，但是最终搞定的时候，还是很有成就感的。以后再遇到类似的问题，我就能更从容地应对。
我想说的是，算法这玩意儿，光看不行，一定要动手实践，才能真正理解其中的奥妙。而且在实践的过程中，你会遇到各种各样的问题，这些问题才是真正让你进步的动力。
好，今天就分享到这里，下次再跟大家聊聊其他的算法。