Algorytm znajdowania najlepszych ścieżek K na wykresie, bez wspólnych wierzchołków, ujemnych wag?

Question

Używam Bellmana-Forda, aby znaleźć najkrótszą ścieżkę na wykresie z ujemnymi wagami. Wykres nie ma możliwości pętli ani połączeń dwukierunkowych. Chciałbym znaleźć najkrótsze ścieżki K na wykresie, gdzie ścieżki nie mają wspólnych wspólnych węzłów. Czy istnieje algorytm, który mogę sprawdzić, aby dowiedzieć się, jak to zrobić? Prosta implementacja jest ważniejsza niż prędkość w danym momencie.

Dodano: Dzięki za komentarze. Aby było jasne, szukam najlepszych sposobów K, aby uzyskać od określonego węzła początkowego do określonego węzła końcowego, bez żadnych innych wspólnych węzłów. Potrzebuję globalnego optimum; sekwencyjne znajdowanie najlepszych i usuwanie węzłów nie daje satysfakcjonujących rezultatów. Ten: https://en.wikipedia.org/wiki/Yen%27s_algorithm, daje smak tego, o czym mówię, ale w tym przypadku wymaga nie ujemnych kosztów krawędzi, a także umożliwia udostępnianie węzłów.

Answer 1

Myślę, że problem można rozwiązać, znajdując minimalny przepływ kosztów.

Załóżmy przekształcić wykres w następujący sposób:

1. zastąpienia każdego węzła V innych niż źródła i komorowy z dwoma węzłami V1 i V2 połączonych krawędzi masy 0 z v1 do v2. W przychodzące brzegi dawnego przeciwko wejść do v1 i wychodzącej urlopu z v2. Z tym problemem jest to, że nie używa się tych krawędzi więcej niż jeden raz.

2. Ustaw pojemność 1 na wszystkie krawędzie.

Znalezienie przepływ wartości K dadzą Ci K ścieżek, które nie podzielają węzeł (ze względu na umieszczenie zdolności do 1 w tych nowych krawędziach). Jeśli więc przepływ ten jest przepływem kosztów minimalnych, będziesz mieć, że te ścieżki mają także minimalną możliwą sumę kosztów.

Zakłada się, że nie ma krawędzi łączącej źródło i zlew bezpośrednio. Sprawdź osobno tę skrzynkę narożną.