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

13

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.

Jleahy
źródło

Odpowiedzi:

23

Ś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.

BlueRaja - Danny Pflughoeft
źródło
1
To jest piękna odpowiedź. Poprosiłem kilka osób o IRL bez żadnych rozwiązań, a kiedy im to wytłumaczyłem, ich reakcja była taka sama jak moja - „oczywiście czuję się teraz tak głupio”.
jleahy