Floyd-Warshall算法是求解任意兩點最短路的有力武器。其也適用于存在負邊的情況。
DP思路，假定只使用前K個點時i到j的最短距離為d[k][i][j]
那末，使用前K+1個點就能夠分成兩種情況
①i到j的最短路用到了第K+1個點(d[k+1][i][j] = d[k][i][j])
②i到j的最短路沒有用到第K+1個點(d[k+1][i][j] = d[k][i][k]+d[k][k][j]);
所以，d[k+1][i][j] = min(d[k][i][j],d[k][i][k]+d[k][k][j])
使用轉動數組，就能夠寫成2維數組的情勢
d[i][j] = min(d[i][j],d[i][k]+d[k][j])
Floyd算法可以在O(V^3)的時間內解出，判斷圖中是不是有負圈，只需要檢查是不是存在d[i][i]是負數的頂點i就能夠了。
//d[i][j]表示i->j的權值，不存在時設為INF 但是d[i][i]設為0
for(int k = 0 ; k < V ; k ++) {
for(int i = 0 ; i < V ; i ++) {
for(int j = 0 ; j < V ; j ++) {
d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
}
}
}由于實現起來非常簡單，如果復雜度在可以承受的范圍以內，單源最短路也能夠使用Floyd-Warshall算法來進行求解。
在有向圖中，如果需要判斷每兩個點是不是存在路徑，那末也能夠用Floyd算法來進行傳遞閉包。
只需要改成d[i][j] = d[i][j] || (d[i][k]&&d[k][j])便可(預處理也要變化)
下一篇 張堯學獲獎申報材料，讀后有感
程序員人生，我編程，我富裕，記住wfuyu網，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內容是作者原創，少部分收集于互聯網供大家一起學習，原版權很多不明，如有侵權請聯系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
