最短路（贝尔曼·福德）

Lag_longlong

2026-07-14 16:09:46

发布于：广东

7阅读

0回复

0点赞

(防透视)——————————————————————————————————————————————
上课老师也是讲了最短路语法，给大家简单分享一些。老师大号

Bellman-Ford模板：

1.1 为何需要n-1轮松弛？

理论依据：无负环图中，任意两点最短路径最多包含n-1条边（n为节点数）。
松弛过程：
- 第1轮：得到最多1条边的最短路径；
- 第k轮：得到最多k条边的最短路径；
- 第n-1轮后：所有最短路径必然收敛。
提前终止优化：若某轮无任何松弛发生，可提前结束循环。

1.2 负环检测机制

关键判定：若第n轮松弛仍能更新距离，则图中存在从源点可达的负权环。
原理：负环允许无限绕行使路径长度无限减小，最短路径无定义。
基础code：

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

struct Edge { int u, v, w; };  
const int INF = 0x3f3f3f3f;    

vector<Edge> edges;           // 边集（无需建图）
int dist;               // 源点到各点距离
int n, m;                     // 节点数、边数

// 返回值：true=存在负环，false=无负环
bool bellman_ford(int start) {
    // 初始化：源点距离为0，其余为无穷大
    fill(dist, dist + n + 1, INF);
    dist[start] = 0;
    
    // **核心：执行n-1轮松弛**
    bool updated = false;
    for (int i = 1; i <= n - 1; i++) {
        updated = false;
        for (auto &e : edges) {
            // 仅当起点可达时才松弛
            if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) {
                dist[e.v] = dist[e.u] + e.w;
                updated = true;
            }
        }
        // 提前终止：无更新即收敛
        if (!updated) break;
    }
    
    // **第n轮检测负环**
    if (updated) {
        for (auto &e : edges) {
            if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) {
                return true;  // 存在负环
            }
        }
    }
    return false;  // 无负环
}