? 最短路徑 之 Floyd 算法
? 最短路徑 之 Dijkstra 算法
Bellman算法差不多是Floyd算法和Dijkstra算法的結(jié)合體颤诀。
核心代碼
// Bellman-Ford
dis[1] = 0;
for (int k = 1; k < n; k++)
for (int i = 1; i <= m; i++)
dis[v[i]] = min(dis[v[i]], dis[u[i]] + w[i]);
Bellman算法需要用鄰接表來儲(chǔ)存圖拼弃。u[i], v[i], w[i]分別表示第i條邊的起點(diǎn)、終點(diǎn)和權(quán)值。dis數(shù)組表示指定頂點(diǎn)（這里是1）到其余各個(gè)頂點(diǎn)的最短路徑尤筐。
上面代碼最后一行表示看看能否通過u[i] --> v[i]這條邊矾端，使得1號(hào)頂點(diǎn)到v[i]號(hào)頂點(diǎn)的距離變短，即1號(hào)頂點(diǎn)到u[i]號(hào)頂點(diǎn)的距離（dis[u[i]]）加上u[i] --> v[i]這條邊（權(quán)值為w[i]）的值是否比1號(hào)頂點(diǎn)到v[i]號(hào)頂點(diǎn)的距離（dis[v[i]]）要小携冤。這一點(diǎn)非常像Dijkstra算法的“松弛”操作悼粮。
再回過頭來看Floyd算法，它的三重循環(huán)k, i, j表示i號(hào)頂點(diǎn)經(jīng)過前k個(gè)頂點(diǎn)到j(luò)號(hào)頂點(diǎn)的最短路徑曾棕。Bellman的二重循環(huán)k, i和這個(gè)類似扣猫，表示進(jìn)行k輪得到1號(hào)頂點(diǎn)最多經(jīng)過k條邊到達(dá)其余頂點(diǎn)的最短路徑。
由于最短路徑不包含回路翘地，所以Bellman算法最多松弛n-1輪申尤，如果在這之后仍然能夠松弛則說明這個(gè)圖里面包含負(fù)權(quán)回路。因此Bellman算法可以用來判斷圖中是否存在負(fù)權(quán)回路衙耕，這是它優(yōu)于Dijkstra和Floyd之處昧穿。
判斷是否存在負(fù)權(quán)回路只需要在循環(huán)完n-1輪后再加下列代碼即可。
bool flag = false;
for (int i = 1; i <= m; i++)
if ( dis[v[i]] > dis[u[i]] + w[i] )
flag = true;
這樣Bellman算法的時(shí)間復(fù)雜度是O(NM)臭杰，比Dijkstra算法還要高粤咪。但事實(shí)上在很多情況下Bellman算法經(jīng)常會(huì)在未達(dá)到n-1輪松弛前就已經(jīng)求得了最短路徑，之后的每一次循環(huán)都不會(huì)有松弛操作渴杆。因此可以用一個(gè)布爾變量來標(biāo)記dis是否發(fā)生了變化寥枝，如果沒有發(fā)生變化就可以跳出循環(huán)。
// Bellman-Ford
for (int k = 1; k < n; k++)
{
bool check = false;
for (int i = 1; i <= m; i++)
if (dis[v[i]] > dis[u[i]] + w[i])
{
dis[v[i]] = dis[u[i]] + w[i];
check = true;
}
if(!check) break;
}
分析Bellman算法的流程磁奖，發(fā)現(xiàn)它有很大的時(shí)間都浪費(fèi)在了循環(huán)中判斷是否需要松弛囊拜。但是在每一次實(shí)施松弛后，就已經(jīng)有一些頂點(diǎn)完成了最短路徑的計(jì)算比搭，在此之后它們的值都不會(huì)再發(fā)生變化冠跷。因此我們就可以每次僅對(duì)最短路徑估計(jì)值發(fā)生變化的頂點(diǎn)的所有出邊進(jìn)行松弛。
隊(duì)列優(yōu)化的Bellman算法
它的操作方法是這樣的：
每次選取隊(duì)首頂點(diǎn)u身诺，對(duì)頂點(diǎn)u的每一條出邊進(jìn)行松弛蜜托。如果松弛成功且這條邊的終點(diǎn)不在隊(duì)列中，就把該頂點(diǎn)放入隊(duì)列中霉赡。由于一個(gè)頂點(diǎn)同時(shí)出現(xiàn)在隊(duì)列中沒有意義橄务，所以可以用一個(gè)數(shù)組book來判重。頂點(diǎn)u松弛完畢后就將u出隊(duì)穴亏。如此循環(huán)直至隊(duì)空蜂挪。
這里需要用到鏈表重挑，我們用數(shù)組來模擬一下。
核心代碼
// Queue-optimized Bellman-Ford
/*
first[u[i]]表示頂點(diǎn)u[i]的第一條邊的編號(hào)棠涮，next[i]表示“編號(hào)為i的邊”的“下一條邊”的編號(hào)
q是C++ STL中的隊(duì)列模板
*/
dis[1] = 0;
book[1] = 1;
q.push(1);
while(!q.empty())
{
int cur = q.front();
for (int k = first[cur]; k != -1; k = next[k])
if (dis[v[k]] > dis[u[k]] + w[k])
{
dis[v[k]] = dis[u[k]] + w[k];
if(!book[k])
{
book[k] = 1;
q.push(k);
}
}
book[cur] = 0;
q.pop();
}
隊(duì)列優(yōu)化的Bellman算法在形式上類似于廣度優(yōu)先搜索谬哀，但不同之處在于廣搜的時(shí)候一個(gè)頂點(diǎn)出隊(duì)后通常不會(huì)再次入隊(duì)。
當(dāng)一個(gè)頂點(diǎn)入隊(duì)超過n次严肪，那么就可以判斷這個(gè)圖里面存在負(fù)環(huán)史煎。
隊(duì)列優(yōu)化的Bellman算法關(guān)鍵在于只有那些在前一遍松弛成功的頂點(diǎn)才能引起與它們相連頂點(diǎn)的最短路徑估計(jì)值的變化。
