Как закрепить ориентированный граф на ненаправленном?

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-й итерации вы обнаружите, что вы все еще не вышли из цикла, в вашем графике есть отрицательный цикл.