Bellman-Ford能处理负权边而Dijkstra不能，根本在于前者不依赖贪心假设，通过V-1轮全局松弛逐步传播最短路径；后者一旦锁定节点即不可更新，遇负权边便失效。
为什么Bellman-Ford能处理负权边而Dijkstra不能
Bellman-Ford不依赖“已确定最短路径节点不再更新”的贪心假设，它对所有边做 V-1 轮松弛操作，每次遍历都可能把更短的路径传播出去。Dijkstra在取出节点后就标记为“已完成”，一旦负权边出现在后续路径中，就无法回溯修正——这是根本区别。
注意：V 是顶点数，不是边数；轮数必须是 V-1，少一轮可能漏掉最长路径（比如链状图），多一轮则无意义（除非检测负环）。
标准实现里必须做V-1轮松弛，但可以提前终止吗
可以，而且推荐。如果某一轮中没有任何 dist[u] + weight(u,v) 成立，说明所有最短路径已收敛，后续轮次不会改变结果。
提前终止不影响正确性，还能显著提升平均性能（尤其稀疏图或无负权时）：
立即学习“C++免费学习笔记（深入）”；
- 用布尔变量
updated标记本轮是否发生松弛 - 每轮开始前设为
false，只要有一次成功更新就置为true - 一轮结束后若
updated == false，直接跳出循环
但别省略第 V-1 轮的逻辑框架——否则无法保证最坏情况下的正确性。
如何可靠检测图中是否存在负权环
在完成 V-1 轮松弛后，再额外执行一轮：如果仍有任意边满足 dist[u] + weight(u,v) ，说明存在从源点可达的负权环。
关键细节：
- 必须从源点出发可达的负环才算——所以初始化
dist[src] = 0，其余为INF（如INT_MAX/2，避免溢出） - 检测时若发现可松弛，不能只返回“有环”，还要考虑是否能从该环到达其他节点（实际应用中常需标记所有受负环影响的节点）
- 使用
INT_MAX作 INF 时，dist[u] + weight可能溢出为负数，造成误判；推荐用1e9或LLONG_MAX/3
邻接表存图时，边的存储顺序会影响结果吗
不影响最终最短距离（只要轮数足够），但会影响收敛速度和负环检测时机。
例如：若某条关键负权边总在每轮末尾才被处理，它触发的更新要到下一轮才能继续传播；而把它放在前面，可能早一两轮就稳定。
实操建议：
- 无需刻意排序，但避免把大量零权/正权边堆在前面、负权边全在后面
- 若已知部分边更可能参与最短路径（如按 BFS 层级组织），可优先放入
- 检测负环时，顺序不影响判定结果，只影响哪一轮暴露出来
真正容易被忽略的是初始化时对不可达节点的处理：它们的 dist 值在整个算法中保持 INF，后续任何基于 dist[u] != INF 的松弛判断都要加这个条件，否则可能用溢出值参与计算。
