c++ - 如何在无向图上修复有向图？

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

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

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

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