floyd最短路径算法是用于求图中任意两点之间最短路径的经典算法，但是关于其正确性的证明书上以及网上并没有很好的解释。一年前自己从最短路径结果本身出发想出了证明办法，但是一直没有发表，今天和朋友又聊起了这个话题，就整理了思路，写出来，与大家分享。

       我们这里从有N个节点的无向图入手进行证明。若图中两个节点不连通，那么经过算法计算后仍为不连通。若它们连通就必然存在一条最短路径。假设任意2节点之间存在一条最短路径，该路径上有M个节点（M<N）。floyd算法为三重循环，我们重点考虑最外层循环，我们将最外层循环此时所在的节点称为“桥点”。桥点遍历到了某一节点时，算法就会计算任意一点A到桥点的距离加上任意一点B到桥点距离的和，并将这个和与矩阵中存储的A到B的路径的距离进行比较，将短的存入矩阵中相应的位置。可以根据以下代码进行理解。

下面是证明用到的图

       为了叙述方便，我们假设固定两节点分别为A和B，它们之间最短路径的节点为中间部分的12个节点，因为桥点会遍历完图中的N的节点，因此必然会遍历A、B以及中间的12个节点。

       假设桥点遍历到了s5节点，则由floyd算法我们必然会有计算s4-s5加上s5-s6的过程，而且这个计算结果会保存到矩阵里，因为最短路径上任意一段都是最短路径，因此它的计算结果必然被保存，我们也就知道了s4-s5-s6这段路径的距离。这里将s4和s6分别称为“桥沿节点”，s5成为“桥顶节点”。这样我们就知道了2个桥沿节点经过桥顶节点之后的路径距离，而且这个距离还是它们之间的最短路径距离。

       我下面就要证明这个桥会变大，而且不同的桥会连接，最终会变成一个大桥，这个大桥的两个边沿节点就是A和B。首先桥顶都是被桥点遍历过的节点，不会再被遍历(下面会说明)，所以下面桥点只会遍历桥沿节点或者其它节点。若遍历的桥沿节点，则桥会扩大，如s9扩展为s8-s9，若不是桥沿节点就会产生新的桥顶节点和新的桥。若一个桥的桥顶节点都被遍历过了那么桥点遍历桥沿节点时，它会变大，但是桥顶节点还是都被遍历过了。若2个桥的桥沿节点为同一几点，那么桥点遍历到这个节点时就会将2个桥合为一个桥。如图中s3和s5被s4和成s3-s4-s5，若2个桥的桥顶节点都被遍历过了，那么由桥点连接起来的新的大桥的所有的桥顶节点也都是被遍历过的。

        OK，所有的桥在产生时都只有一个桥顶节点，而且桥顶节点被桥点遍历过了，这些初始桥的桥顶节点都被遍历过，它们的扩展方式只有桥边节点被桥点遍历，或者与其它的桥合并，这样产生的新的大桥的桥顶节点也都是被遍历过的。以此类推，所有的桥顶节点都已经被桥点遍历过，下面桥点只会遍历桥沿节点扩展桥，或者其它节点产生新的桥，因为桥点会遍历N个节点，因此会遍历完中间路径上的每一个节点，因此实际运算时会产生桥，然后桥点遍历桥顶节点之外的节点来产生新的桥，或者扩充桥，最后，这些桥不断扩大，导致桥沿节点重合，桥点可定会遍历桥沿节点，因此桥会合并，最终出现一个桥沿节点为A和B的大桥，这时我们也就知道了A和B之间最短路径的距离。

        因为A和B为任意节点，所以任何2个节点之间最短路径上的节点被桥点遍历完，都可以求得它们之间的最短路径。因为桥点会遍历完N个节点，所以任意连通的2个节点之间的最短路径上的节点都会被遍历到，所以我们也就会在计算过程中计算出过最短路径距离，记住，我们每计算一个都会将计算结果与矩阵中的数值进行比较，将小的存入矩阵，所以这个过程中我们会在计算出最短路径后将它填入矩阵。注意：这个最短路径如果存在就一定会在某次计算得到其结果。

       有向图一样的，因为计算过程中会两个方向都计算以此。比如桥点遍历到s5时，s4-s5加上s5-s6会计算一次，s6-s5加上s5-s4还会计算一次，因此有向图同样适用。