对floyd算法理解

最基础的floyd写法

for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(e[i][j]>e[i][k]+e[k][j])
e[i][j]=e[i][k]+e[k][j];

看了一两篇文章，总结一下，首先floyd求的是多源最短路，思想是：一开始用来存图的邻接矩阵对于两个点之间没有其他点的情况，已经是这个两个点之间的最短路径了，然后floyd算法试图在两点之间加其他的点，来更新它们之间的最短路径，这种做法是对这两个点之间有更短距离起作用的，所以在一开始的情况下，floyd算法只对两个点之间没有路径（也就是距离为无穷大时）起作用，可以感性的想象到k从1到n，对于两个点之间没有路径的来说，就是试图找到两个点中夹杂一个点的路径的情况来更新原来没有路径的情况，然后再找到两个点中夹杂两个点的情况（如果满足条件的话）来更新夹杂一个点的情况…以此类推，那么它又是如何从两个点之间夹杂一个点的路径的情况一步步地更新到两个点夹杂多个点的情况的呢，这就需要手动模拟下了。

首先建一个简单的图

图中已经得到1->2,2->3,3->4的最短路径分别为3,2,5，其他两袋奶之间的路径均为无穷大。然后执行floyd算法，依照循环顺序，k=1时，先以1为要更新的两个点之间夹杂的点，发现并没有这种情况，所以就不更新。

然后k=2，表示以2为要更新的两个点之间夹杂的点，然后发现可以更新1->3的路径长度为3+2=5。

然后k=3,依照循环的顺序，先是会发现可以更新1->4的路径长度为5+5=10（因为先前以更新1->3的路径长度为5，然后现在就相当于点1和3连接在了一起），这样就更新了两个点之间夹杂两个点的最短路径了，原理还是相当于更新两个点之间夹杂一个点的路径的情况，将这两个点之间无穷大的路径长度更新为10。然后还可以更新2->4的路径长度为2+5=7。

最后k=4，发现没有要更新的情况，结束循环。求得最终各个点之间的最短路径。

两个点之间夹杂更多点的情况，也同理可得，算法最核心的思想在于，对两个点之间夹杂另一个点的最短路径的情况的利用，夹杂一个点也可以说成是借助另一个点，更新原来两点的情况，当可以更新时，更新过后，这两个点就相当于相连在一起，当下一次更新夹杂更多点的情况时，同样用夹杂一个点的做法来更新，虽然这个例子很简单，并没有覆盖到各种情况，但是我们可以想象，再更复杂的图中，使用floyd算法，其实就是在局部的不停做类似上面手动模拟那样的更新操作，最后求得所有点的最短路径，不得不佩服前人思维之强大！！！