网站手机客户端在线制作百度排名怎么做

问题描述：

       带负权值边的有向图中的最短路径路径问题：对于一个带负权值边的有向图，实现 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;
}

代码检验：