一、bellman-ford算法
1、概述
bellman-ford算法適用于負(fù)權(quán)邊的圖，求 1 到 n 的最多經(jīng)過k條邊的最短距離。
如圖所示：
| 1 | 2 | 3 | |
|---|---|---|---|
| dist | 0 | ∞ \infty ∞ | ∞ \infty ∞ |
? \Downarrow ?
| 1 | 2 | 3 | |
|---|---|---|---|
| dist | 0 | 1 | ∞ \infty ∞ |
? \Downarrow ?
| 1 | 2 | 3 | |
|---|---|---|---|
| dist | 0 | 1 | 2 |
此過程中出現(xiàn)了串聯(lián)的結(jié)果，所以是錯(cuò)誤的，此時(shí)需要進(jìn)行備份操作。
備份操作如下：
for(int i = 0; i < k; i++){
memcpy(backup, dist, sizeof(dist);//backup存的是上一次迭代的結(jié)果
for(int j = 0; j < m; j++){
..................
}
}
2、特例
為了防止出現(xiàn)串聯(lián)，保證符合題目條件，需要備份。
注意：
b
e
l
l
m
a
n
?
f
o
r
d
算法中是不存在負(fù)權(quán)回路的
注意：\textcolor{red}{bellman-ford算法中是不存在負(fù)權(quán)回路的}
注意：bellman?ford算法中是不存在負(fù)權(quán)回路的
3、舉例
bellman-ford算法的常規(guī)操作
for 循環(huán)遍歷 n 次
for 遍歷所有邊 a，b，w
dist[b] = min(dist[b], dist[a] + w);
//此過程稱為松弛操作
如圖：
如果1
→
\to
→a
→
\to
→b的距離比1
→
\to
→b的短則更新dist[b]。
循環(huán)完之后，所有邊的距離一定滿足dist[b]
≤
\le
≤dist[a]+w，此不等式也稱三角不等式。
4、bellman-ford算法模板
時(shí)間復(fù)雜度
O
(
n
m
)
O(nm)
O(nm)，
n
n
n表示點(diǎn)數(shù)，
m
m
m表示邊數(shù)
注意在模板題中需要對(duì)下面的模板稍作修改，加上備份數(shù)組，詳情見模板題。文章來源：http://www.zghlxwxcb.cn/news/detail-809690.html
int n, m; // n表示點(diǎn)數(shù)，m表示邊數(shù)
int dist[N]; // dist[x]存儲(chǔ)1到x的最短路距離
struct Edge // 邊，a表示出點(diǎn)，b表示入點(diǎn)，w表示邊的權(quán)重
{
int a, b, w;
}edges[M];
// 求1到n的最短路距離，如果無法從1走到n，則返回-1。
int bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
// 如果第n次迭代仍然會(huì)松弛三角不等式，就說明存在一條長(zhǎng)度是n+1的最短路徑，由抽屜原理，路徑中至少存在兩個(gè)相同的點(diǎn)，說明圖中存在負(fù)權(quán)回路。
for (int i = 0; i < n; i ++ )
{
for (int j = 0; j < m; j ++ )
{
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
if (dist[b] > dist[a] + w)
dist[b] = dist[a] + w;
}
}
if (dist[n] > 0x3f3f3f3f / 2) return -1;
return dist[n];
}
Acwing-Bellman-Ford算法模板文章來源地址http://www.zghlxwxcb.cn/news/detail-809690.html
到了這里，關(guān)于Acwing-基礎(chǔ)算法課筆記之搜索與圖論的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
