Кратчайший путь в взвешенном ориентированном графе

Question

Мне нужно найти кратчайший путь между двумя узлами s, t во взвешенном ориентированном графе. Вот ограничения:

1. Вес может быть отрицательным.
2. Путь должен пройти через конкретное ребро, давайте назовем ее e и shes от узла u к v.
3. Выходной путь должен быть простым, то есть мы проходим через узел только один раз.

Теперь у меня есть идея для решения, но я не знаю, будет ли вывод простым путем или нет.

Мое решение состоит в том, чтобы запустить алгоритм Bellman Ford дважды, один раз от s, второй от v. Кратчайший путь будет s к u, u к v, v к t.

Поскольку я хочу, чтобы все было просто, я не буду использовать узлы, которые я уже использовал во втором запуске Bellman Ford.

Поскольку я хочу, чтобы он был кратчайшим, я проверим, быстрее ли работает bellman ford от v до t, прежде чем переходить от s к u (если есть узел, оба используют где лучшее место для его размещения). ).

Спасибо за помощников!

Answer 1

Даже нахождение такого пути является NP-полным. Это связано с тем, что проблема двух вершинных / реберных непересекающихся путей является NPC в ориентированных графах. Предположим, что ребро e = (u, v), тогда вы ищете (s, u), (v, t) непересекающиеся пути, но это является NP-полным в орграфах.

Здесь вы можете найти результат твердости: https://www.sciencedirect.com/science/article/pii/0304397580900092

Ваш текущий алгоритм, основанный на Bellman-ford, не дает правильного ответа для всех случаев (он может не найти путь, пока есть путь), однако, это может быть хорошей эвристикой. Если ваш график был ненаправленным, то задача была намного проще.

Если вы разрешаете повторять вершины, то любой алгоритм кратчайшего пути является правильным способом сделать это.