floyed应该是大家接触最短路首先了解到的算法简单的四行代码却能把所有点对之间的最短距离求出来相信很多人刚刚接触到这个算法时没有深刻理解算法的原理~~~我写这篇文章是源于南宁区域赛热身赛的一道题目由于对此算法理解不透彻比赛时候没有能将一道变形题做出来于是比赛结束后再次思考了这个算法得到了一些收获于是写下了这篇文章~~for(int k1;kn;k) for(int i1;in;i) for(int j1;jn;j) dp[i][j]min(dp[i][j],dp[i][k]dp[k][j]);主要的操作对点的松弛操作很容易理解给人咋一看的感觉就是对于每一个点对之间对于所有点都松弛一边但算法的正确性却并不是那么容易的证明~首先引入这样一种请况对于一张图已知原图中各个点对之间的最短距离现在加入一个新的点和与该图相连的若干边求加入之后新图各个点对之间的最短距离。首先对于新加的点我们可以在新图跑一边最短路求出该点到原集合中每一个点的最短距离在其逆图上跑一边最短路求出原集合中的每一个点到该点的最短距离~那么此点到原集合中每一个点之间的最短距离都是正确的但是对于原集合中的每一个点对之间的最短距离可能能通过松弛此点从而距离变短所以原集合中的每一个点对之间的距离还应该更新一遍。for(int i1;in;i) for(int j1;jn;j) dis[i][j]min(dis[i][j],dis1[i]dis2[j]); //dis1[u]表示u点到新加入点的最短距离,dis2[v]表示新加入点到v点的最短距离那么正题来了floyed是怎样维护每个点对之间的最短距离从而达到保证了算法的正确性呢我的理解是floyed是一个动态规划的过程通过维护一个逐渐增大的集合对任意点对 (i,j)dp[i][j] 是中间点只允许来自当前集合时的最短距离。随着集合的增长集合包含了原图中所有的点时算法就求出了每个点对之间的最短距离。对于算法过程的解释void floyed() { for(int k1;kn;k) { for(int i1;ik;i) for(int j1;jk;j) dp[i][j]min(dp[i][j],dp[i][k]dp[k][j]); //原集合中的每一个点可以通过此新加入的点松弛一遍 for(int i1;ik;i) for(int jk1;jn;j) dp[i][j]min(dp[i][j],dp[i][k]dp[k][j]); //原集合中的每一个点到集合外每一个点的临时最短距离 for(int ik1;in;i) for(int j1;jk;j) dp[i][j]min(dp[i][j],dp[i][k]dp[k][j]); //集合外的每一个点到原集合中的每一个点的临时最短距离 for(int ik1;in;i) for(int jk1;jn;j) dp[i][j]min(dp[i][j],dp[i][k]dp[k][j]); //按照算法定义集合外的点之间可以通过此点松弛距离 } }维护增长的集合是前k-1个点外层第k次循环的时候是将第k个点加入此集合中。此时dp[i][j]表示路径的中间点只来自原集合ij结点之间的临时最短距离(刚开始的时候集合为空那么表示直接相连)所以对于所有点对之间的临时最短距离都可以对此点松弛一遍从而保证了算法的正确性。第一次循环开始之间集合为空此时初始状态为原图中每个点对之间直接距离第k次循环能保证k1次循环时的正确性根据归纳法所以得证floyed算法的正确性~~~~~