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