如何修复无向图?

Question

我无法正确更正代码，因此图形是无向的。通过输入，按条件，应该有许多顶点，边，然后是相邻顶点及其权重的列表

using namespace std;
const int inf = 10000000;
struct edge {
int u, v, w;
};
int n, m, v, i;
vector<edge> e;
void solve() {
vector<int> d(n, inf);
d[v] = 0;
for (;;) {
bool any = false;
for (int j = 0; j < m; ++j)
if (d[e[j].u] < inf)
if (d[e[j].v] > d[e[j].u] + e[j].w) {
d[e[j].v] = d[e[j].u] + e[j].w;
any = true;
}
if (!any)  break;
}
cout << d[d.size()-1] << endl;
}
int main() {
cin >> n >> m;
edge t;
for (i = 0; i<m; i++)
{
cin >> t.u >> t.v >> t.w;
t.u--; t.v--;
e.push_back(t);
}
solve();
}

Answer 1

从数学的角度来看，如果用一对方向相反的有向边替换每个无向边，则无向图应该等价于有向图。

据我所知，您正在尝试实现贝尔曼-福特算法。有关您的实施的一些说明。如我所见，您的v全局变量未正确初始化。这是故意假设源是索引为 0 的顶点吗？贝尔曼-福特找到从源到所有其他顶点的最短路径;您输出具有最大索引的顶点路径的长度，这是您所期望的吗？

一个主要问题：如果你有一个负循环(这是可能的，因为你使用有符号的int来存储权重)会发生什么？贝尔曼-福特算法的好处是，如果图形的某些边具有负权重，它就可以正常工作。此外，它允许您检测负循环的存在，但在您的情况下，算法将进入无限循环。解决方案是用n限制迭代次数;如果在第 n 次迭代中，您发现您仍然没有离开循环，则您的图形中存在一个负循环。