弗洛伊德最短路径算法理解

弗洛伊德最短路径算法理解"/>

弗洛伊德最短路径算法理解

（涉及到前面讲过的 warshall 算法）  floyd 要求图中每个定点之间的最短路径，其比迪杰斯特拉算法在这一问题上要先进的地方就在于各个点之间的最短路径是同步更新的。在 i 和 j 中间依次加入从 0 到 n-1 的点，如果设加入的点为 k ，当 i->k （之前算好的 i 到 k 的最短路径） +k->j 小于原来的 i->j 时，更新 i->j 。最后得到每两个点之间的最短路径。具体算法步骤看书上，我重点讲下面的东西。   假设 0->6->1->2 为 0 到 6 的最短路径，那么利用贪心算法的思想 0->6 一定为 0 到 6 的最短路径，路径上每一个点到下一个点都走的相互间的最短路径，当 k 从 0 到 n-1 依次作为中转点时，一定可以找到两个点之间只通过一个点中转后的最短路径，其中若 k==i 或 k==j 可看做没有中转，所以 0 到 1 的最短路径 0->1 就可以替换 0->6->1 （因为 6 是那个最小路径中转点），所以 0->6->1->2 变为 0->1->2 ，然后以 1 作为中转点时又缩短为 0->2 ，这样就可以证明该路径确实为 0 到 2 的最短路径，因为每一个点都会作为中转点，因此两个点之间的最短路径都能利用缩短思想证明能求的出来，这里的缩短思想和 warshall 算法真的好像。