Aksjomaty dla najkrótszych ścieżek

Załóżmy, że mamy niekierowany wykres ważony $G = (V, E, w)$ (z wagami nieujemnymi). Załóżmy, że wszystkie najkrótsze ścieżki w $G$ są unikalne. Załóżmy, że mamy (sekwencje nieważonych krawędzi), ale nie znam samegoCzy możemy wytworzyć dowolny który dałby te ścieżki jako najkrótsze w czasie wielomianowym? Wersja słabsza: czy możemy zdecydować w czasie wielomianowym, czy takie istnieje? $\binom{n}{2}$ $G$ $G$ $G$

Oczywistym warunkiem koniecznym jest: dla każdej pary ścieżek ich przecięcie również jest ścieżką. Czy ten warunek jest wystarczający?

— ilyaraz
źródło

Muszę się mylić co do danych wejściowych: jeśli w połączeniu najkrótszych ścieżek masz dwa wierzchołki w cyklu, to są między nimi dwie ścieżki (które koniecznie są najkrótsze), a jedna z nich musi być krótsza wyjątkowość

u, v

$u,v$

— Suresh Venkat

@Suresh: Nie wiem, co chcesz uzyskać. Jeśli wykres G jest kompletnym wykresem, wówczas unikalna najkrótsza ścieżka między dowolnymi dwoma wierzchołkami jest pojedynczą krawędzią, a suma wszystkich tych najkrótszych ścieżek jest kompletnym wykresem.

— Tsuyoshi Ito,

Myślę, że odpowiedź brzmi „nie” dla rekonstruowania ważonego wykresu, ponieważ jeśli brakuje jakiegoś zbocza w danych wejściowych, może on (a) być pominięty na wykresie lub (b) być zboczem o naprawdę naprawdę dużej wadze. Myślę, że wersja bez obciążników jest bardziej interesująca. Ponadto, dlaczego wykres, który chcemy znaleźć, jest ważony, a ścieżki, które otrzymujemy, są nieważone?

— Artem Kaznatcheev

niech będzie zjednoczeniem najkrótszych ścieżek. czy istnieje powód, dla którego nie jest wykresem, który dałby te same najkrótsze ścieżki? lub innymi słowy, czy nie jest tak, że jeśli podane najkrótsze ścieżki nie są najkrótszymi ścieżkami w , to nie ma wykresu, dla którego są najkrótszymi ścieżkami?

H

$H$

H

$H$

H

$H$

— Sasho Nikolov

@SashoNikolov Jakie wagi należy przypisać do krawędzi?

— ilyaraz

Odpowiedzi:

Właśnie natknąłem się na to stare pytanie podczas przeprowadzania drobnych poszukiwań i zdarzyło mi się niedawno uzyskać odpowiedzi w tym artykule, które równie dobrze mogę podzielić. Mam nadzieję, że połączenie nekromancji nici i autopromocji jest wybaczalne.

Czy możemy wytworzyć dowolny G, który dałby te ścieżki jako najkrótsze w czasie wielomianowym? Wersja słabsza: czy możemy zdecydować w czasie wielomianowym, czy takie G istnieje?

Odpowiedź brzmi: tak dla obu. Algorytm Mohammada na pewno działa, ale istnieje szybsza i bardziej bezpośrednia metoda, która pozwala uniknąć konieczności uruchamiania wyroczni separacji sześciennej. Niech będzie pomocniczym niekierowanym ważonym wykresem, gdzie waga każdej krawędzi jest liczbą całkowitą wskazującą, ile ścieżek pobranych na wejściu zawiera tę krawędź. Rozważmy teraz wystąpienie przepływu wielokomorowego o pojemności skondensowanej nad (interpretowanie wag krawędzi jako pojemności), w którym celem jest jednoczesne przepchnięcie 1 jednostki przepływu między każdą parą węzłów. Oczywiście, tę instancję przepływu MC można spełnić, popychając przepływ w naturalny sposób wzdłuż ścieżek podanych na wejściu. Jak się okazuje, można udowodnić, że $H = (V, E, w')$ $e \in E$ $n \choose 2$ $H$ $n \choose 2$ ścieżki są unikatowymi najkrótszymi ścieżkami w niektórych wtedy i tylko wtedy, gdy jest to unikalny sposób spełnienia instancji przepływu MC. Możemy przetestować wyjątkowość, ustawiając LP, którego ograniczenia są typowe dla wykonalności przepływu MC plus pewnie starannie wybrana funkcja celu, a wagi krawędzi satysfakcjonującego można wyodrębnić z podwójnego tego LP. $G$ $G$

Oczywistym warunkiem koniecznym jest: dla każdej pary ścieżek ich przecięcie również jest ścieżką. Czy ten warunek jest wystarczający?

Ten warunek jest czasem nazywany „spójnością” (zestaw ścieżek jest spójny, jeśli przecięcie dowolnych dwóch jest podścieżką każdego z nich). Z powyższego wynika, że spójność nie jest wystarczająca. Jednym z dwóch przywiązanych do najmniejszych kontrprób jest następujący kodowany kolorami system czterech ścieżek w sześciu węzłach:

Innymi słowy, nie ma sposobu, aby przypisać wagi do 8 pokazanych tutaj krawędzi, tak aby wszystkie te cztery ścieżki były jednocześnie unikalną najkrótszą ścieżką między ich punktami końcowymi. Jednak każda para przecina się tylko na jednym węźle, więc są spójne (nawet jeśli wypełnimy je kilkoma dodatkowymi ścieżkami we właściwy sposób, aby łącznie ). Istnieje nieskończenie wiele takich kontrprzykładów; opis artykułu zawiera artykuł. $n \choose 2$

Trzy inne szybkie komentarze na ten temat:

Analogiczne stwierdzenia, które możesz mieć dla wszystkich, dobrze sobie radzą w ustawieniach grafów skierowanych zamiast niekierowanych,
Istnieje ładna topologiczna interpretacja tej teorii, która prowadzi do dodatkowych spostrzeżeń i intuicji na temat tego, w jaki sposób można skonstruować unikalne najkrótsze ścieżki, oraz
Z pewnych przyczyn technicznych teoria upraszcza ustawianie DAG zamiast grafów bezkierunkowych lub (cyklicznych).

— GMB
źródło

Możesz napisać problem jako LP, prawda? Dla dowolnych dwóch wierzchołków u, v i dowolnej ścieżki P od u do v, waga P jest większa lub równa wadze danej najkrótszej ścieżki między u i v. Są to wszystkie nierówności liniowe, i mimo że istnieją wykładniczo wielu, problem separacji występuje w P (to tylko problem najkrótszej ścieżki wszystkich par). Możesz więc użyć algorytmu Ellipsoid, aby go rozwiązać.

— Mohammad
źródło