问题描述：
带负权值边的有向图中的最短路径路径问题：对于一个带负权值边的有向图，实现 Bellman - Ford 算法，求出从指定顶点 s 到其余顶点的最短路径，并判断图中是否存在负环。
❗算法分析❗：
Dijkstra 算法之所以能够运行，是因为从起始点 s 到任一顶点 v 的最短路径一定会经过比 v 距离 s 更近的点。但当边值可以为负时，这条原则不再成立。
但是，我们仍可利用 Dijkstra 算法的思想。Dijkstra 算法可被视为一个update操作，从源点 s 到 目标点 t 的路径最多有 |V|-1 条边。由于我们并不知道所有的最短路径，所以我们只能考虑所有可能的路径，即将 dist[t] 值更新 |V|-1 次。
该 Bellman - Ford 算法中，也利用了动态规划方法?：
定义子问题：min( dist[i] ) 为从源点到点 i 的最短距离。
最小子问题：0 → i 有直接路径时，dist[i] = edges[0][i]；dist[0] = 0。
状态转移方程：dist[i] = min(dist[i], min(dist[j] + edges[j][i]))。
❗算法实现❗：
#include <iostream> #include <vector> using namespace std; int vexnum; int edgenum; vector<vector<int>> edges; vector<int> dist; bool Bellman_Ford(); int main() { cout << "请输入顶点数、边数:" << endl; cin >> vexnum >> edgenum; edges.resize(vexnum, vector<int>(vexnum, INT_MAX)); cout << "请输入各边的顶点及权值:" << endl; for (int i = 0; i < edgenum; ++i) { int tmp1, tmp2, tmp; cin >> tmp1 >> tmp2 >> tmp; edges[tmp1][tmp2] = tmp; } dist.resize(vexnum, INT_MAX); if (Bellman_Ford()) { cout << "不含负环" << endl; //输出从源点到各点的最短路径 cout << "从源点到其余各点的最近距离:" << endl; for (int i = 1; i < vexnum; ++i) { cout << "从 0 到" << i << " : " << dist[i] << endl; } cout << endl; } else { cout << "含有负环" << endl; } return 0; } bool Bellman_Ford() { // 给 dist 数组赋初值 dist[0] = 0; for (int i = 1; i < vexnum; ++i) { if (edges[0][i] != INT_MAX) { dist[i] = edges[0][i]; } } for (int k = 1; k < vexnum + 1; ++k) //更新 V 次, 检查第 v 次更新时 dist 值是否还会变化 { // 更新 dist[t] 的值 for (int t = 1; t < vexnum; ++t) { for (int i = 1; i < vexnum; ++i) { if (edges[i][t] != INT_MAX && dist[i] != INT_MAX && dist[t] > dist[i] + edges[i][t]) { dist[t] = dist[i] + edges[i][t]; if (k == vexnum) { return false; } } } } } return true; }代码检验：
Bellman_Ford代码检验
