Floyd算法：
1、基本思想
求解所有點的路徑需要進(jìn)行n次試探。對于頂點i到頂點j的路徑長度，首先考慮讓路徑經(jīng)過頂點1，比較路徑（i，j）和（i，1，j）的長度取其短者為當(dāng)前求得的最短路徑長度。
Floyd算法的本質(zhì)是動態(tài)規(guī)劃。遞歸方程如下：
dp[i]j][k]=min{dp[i][j][k-1],dp[i][k][k]+dp[k][j][k]}
特殊的有：
當(dāng)k=0時，dp[i][j][0]=w(i,j)，其中dp[i][j][k]表示從i到j(luò)經(jīng)過k的最短路徑。
2、樣例代碼

//Floyd
viod Floyd() {
    for(iint i=0; i<sz; i++) {
        for(int j=0; j<sz; j++) {
            int i_distances[j][i]+distances[i][k];
            if(distances[j][k]>t_dis)
                distances[j][k]=t_dis;
        }
    }
}

3、注意事項
Floyd可以處理負(fù)權(quán)邊，但無法處理負(fù)環(huán)。
Floyd算法適用于無向圖，有向圖，此時一個無向邊次相當(dāng)于兩個有向邊。
求出全源最短路徑的計算復(fù)雜度為O（n³）。