最短路

【算法-图论-最短路】最短路算法全攻略

0 条评论 最短路 无标签 联环己烷

Floyd

Floyd算法是一种$O(n^3)$时间复杂度的优秀的最短路算法,其极致简约四行代码如下:

for(RI k=1;k<=n;++k)
    for(RI i=1;i<=n;++i)
        for(RI j=1;j<=n;++j)
            if(dis[i][k]+dis[k][j]<dis[i][j]) dis[i][j]=dis[i][k]+dis[k][j];

思路也不难理解,我们每次求出只能经过前$k$个点的最短路,显然有一个dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);的DP方程。


京公网安备 11010802033049号