Znalezienie najtańszego ścieżkę z ignorując jeden koszt

Question

Chcę Najkorzystniejsze ścieżkę między 2 wierzchołki i mogę wybrać jedną ścieżkę, które mogę iść za darmo, np.

Najtańszy ścieżkę między wierzchołkami 1 i 6 to 1-3-4-5-6 - Idę na krawędzi 1-3 (koszt 30) za darmo i to daje mi całkowity koszt 21.

Czy istnieje inny sposób niż sprawdzenie wszystkich ścieżek przez jeden?

Answer 1

Jednym ze sposobów, aby to zrobić byłoby wykonać następujące czynności:

1. Duplikat swój wykres, tak, że masz oryginalny graf G z węzłami 1,2, itd. oraz kopię G 'z węzłami 1', 2 'itd. i odpowiednie krawędzie.
2. Dla każdej krawędzi (a, b) G, wykonaj łuk (skierowany!) Od a do b ', a drugi od b do a, oba z kosztem 0.
3. Wreszcie, użyj dowolnego algorytmu najkrótszej ścieżki od dowolny wierzchołek subgraphu G do dowolnego wierzchołka G '(1 do 6' w twoim przykładzie).

Zasadniczo dzieje się tak, że przełączasz się z podgrafu G na G ', gdy używasz swojego jokera.

Możesz generalizować stamtąd do dowolnej liczby krawędzi jokera, dodając dodatkowe kopie i łącząc każde nowe z ostatnim. W takim przypadku możesz jednak dodać cele przy użyciu mniej jokerów, aby uwzględnić przypadki, w których najkrótsza ścieżka wymaga mniejszej liczby krawędzi niż jokery.