Znalezienie najkrótszej ścieżki w obecności cykli ujemnych

Biorąc pod uwagę ukierunkowany wykres cykliczny, na którym ciężar każdej krawędzi może być ujemny, koncepcja „najkrótszej ścieżki” ma sens tylko wtedy, gdy nie ma żadnych cykli ujemnych, iw takim przypadku można zastosować algorytm Bellmana-Forda.

Jestem jednak zainteresowany znalezieniem najkrótszej ścieżki między dwoma wierzchołkami, która nie wymaga cyklizacji (tj. Pod warunkiem, że nie możesz odwiedzić tego samego wierzchołka dwa razy). Czy ten problem jest dobrze zbadany? Czy można zastosować wariant algorytmu Bellmana-Forda, a jeśli nie, czy istnieje inne rozwiązanie?

Interesuje mnie również problem równoważnych par, do którego w innym przypadku mógłbym zastosować Floyda – Warshalla.

Ścieżki bez powtarzających się wierzchołków nazywane są ścieżkami prostymi , dlatego szukasz najkrótszej prostej ścieżki na wykresie z cyklami ujemnymi.

Można to zmniejszyć od problemu najdłuższej ścieżki . Gdyby dla twojego problemu istniał szybki solver, wówczas otrzymując wykres z dodatnimi wagami krawędzi, zanegowanie wszystkich wag krawędzi i uruchomienie solvera dałoby najdłuższą ścieżkę na oryginalnym wykresie.

Zatem twój problem jest trudny do rozwiązania.