? 最短路徑 之 Dijkstra 算法
? 最短路徑 之 Bellman 算法
Floyd算法是基于一種動態(tài)規(guī)劃的思想次企。
點u到點v的最短路徑可能是u直接到v不需要經(jīng)過其他的中轉(zhuǎn)點嫉到，也有可能經(jīng)過兩個或多個中轉(zhuǎn)點后會更短 即 u -> k1 -> k2 -> ...... -> ki -> v陪踩。
當(dāng)只允許經(jīng)過1號頂點的時候 求最短路徑 時間復(fù)雜度是 O(N2)其骄。
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
e[i][j] = min(e[i][j], e[i][1] + e[1][j]);
只允許經(jīng)過2號頂點的時候 求最短路徑 時間復(fù)雜度是 O(N2)辐烂。
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
e[i][j] = min(e[i][j], e[i][2] + e[2][j]);
這兩個一綜合就成了 只允許經(jīng)過1虎囚、2號頂點時的最短路徑 调煎，
而我們的目的是求 經(jīng)過所有n個頂點時的最短路徑。
所以我們只需要令k = 1, 2, 3, ..., n
就成了從i號頂點到j(luò)號頂點經(jīng)過前k號頂點的最短路徑铺遂，
一共進行n次便可以求得 時間復(fù)雜度是 O(N3)
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
e[i][j] = min(e[i][j], e[i][k] + e[k][j]);
Floyd算法與頂點的關(guān)系密切衫哥，適用于稠密圖，可以處理負權(quán)邊襟锐，但是不能處理負權(quán)回路撤逢。
因為帶有負權(quán)回路的圖有可能不存在最短路徑，每循環(huán)一次這個負權(quán)回路的最短路徑就會減少粮坞，算法無法結(jié)束蚊荣。
Floyd算法的時間復(fù)雜度為 O(N3)，但由于它實現(xiàn)起來非常容易莫杈，所以當(dāng)對時間復(fù)雜度要求不大的時候妇押，用Floyd算法來求指定兩點之間的最短路徑或者指定一個點到其余各個頂點的最短路徑也是可行的。
完整代碼
#include <iostream>
using namespace std;
int main()
{
int e[101][101], n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if(i == j)
e[i][j] = 0;
else
e[i][j] = 0xffff;
for (int i = 1; i <= m; i++)
{
int u, v, w;
cin >> u >> v >> w;
e[u][v] = w;
}
// Floyd - Warshall
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
e[i][j] = min(e[i][j], e[i][k] + e[k][j]);
// output...
return 0;
}
