Biorąc pod uwagę ważony nieukierunkowany wykres G i dwa węzły U, V, aby uzyskać najkrótszą ścieżkę. Jak mogę uzyskać najkrótszą ścieżkę od U do V, która używa parzystej liczby krawędzi (jeśli to możliwe, aby ją uzyskać)?Najkrótsza ścieżka z parzystą liczbą krawędzi
Znalazłem kilka artykułów w sieci mówiących, że konieczna jest modyfikacja oryginalnego wykresu. Ale nie mogę zrozumieć, jak to zrobić.
Jest kilka dobrych materiałów do zbadania tego problemu?
Musisz zbudować wykres pośredni i uruchomić wykres Dijkstry na tym wykresie.
względu wykres G = (V, E) utworzyć nowy wykres G' = (V', E') z V' nowy zbiór wierzchołków v_even i v_odd dla każdego wierzchołka v w V i E' zbiór wierzchołków następująco: Jeśli (u, v) jest krawędzią w G, a następnie (u_odd, v_even) i (u_even, v_odd) są krawędzie w G', o tej samej wadze.
Oczywiście nowy wykres ma dwa razy więcej krawędzi i wierzchołków niż oryginalny wykres.
Teraz, jeśli chce znaleźć najkrótszą ścieżkę między s i t w G, wystarczy uruchomić Dijkstry na G' znaleźć najkrótszą ścieżkę między s_even i t_even.
Czas działania to nadal O(|V| log |E|).
To da ci najkrótszy nawet spacer, a nie najkrótszą nawet ścieżkę. Chociaż to, co można znaleźć za pomocą algorytmu Dijkstry, jest ścieżką, po scaleniu z powrotem "bliźniaczych" krawędzi, może stać się szlakiem, a nawet spacerem. Jako kontrprzykład, weź wykres uzyskany z rozłącznego połączenia trójkąta i ścieżki o długości 3, a następnie zidentyfikuj wierzchołek trójkąta z wewnętrznym wierzchołkiem ścieżki. – Untitled
@ Bez tytułu, jeśli rozumiem twój argument poprawnie: moje podejście jest niepoprawne, ponieważ jednym ze sposobów na przekształcenie spaceru długości nieparzystej w równomierny spacer jest wykonanie pełnej rundy w cyklu o nieparzystej długości. Masz rację, to ważny przykład, że to podejście nie działa w ogóle. –
A co z uruchomieniem Dijkstry, gdzie każdy węzeł ma dwie wartości. Jeden jest nieparzysty (pochodzący z równej wartości), a drugi jest nawet wartością.
Dijkstra to chciwy algorytm. Nie można przechowywać obu wartości w tym samym węźle, ponieważ zostanie ono odwiedzone tylko raz, a wartość parzysta może być bardzo różna od wartości nieparzystej. –
Innym sposobem jest zbudowanie nowego wykresu z dwoma typami węzłów, w którym każdy węzeł nieparzysty wskazuje na węzeł i na odwrót. W ten sposób nie modyfikuje się Dijkstry (myślałem), ale wykres. –
To da ci spacer, a nie ścieżkę. Proszę zobaczyć mój komentarz na temat odpowiedzi Vincenta. – Untitled
Taka ścieżka musi mieć jeden z końcowych punktów i kopię v jako drugi punkt końcowy, ponieważ są to jedyne odkryte wierzchołki. Jeśli scalisz kopie i pozbędziesz się dodanych krawędzi, znaleziona ścieżka odpowiada parzystej ścieżce, ponieważ zaczyna się od jednej kopii, a kończy na innej. Również każda ścieżka parzysta odpowiada ścieżce rozszerzającej (według tego samego argumentu), dlatego minimum jednego jest również minimum drugiego. Zostało to wyjaśnione w here.
Czy możesz przesłać link do łatwo dostępnego papieru? –
@ LukaRahne Przepraszam Luka. Nie mogłem go znaleźć. Zgaduję, że jeśli poprosisz autorów, przyznają ci dostęp. Może spróbuj poprosić o nie na stronie ResearchGate tego artykułu. – Untitled
To pytanie lepiej pasuje do stosu informatyki. – Untitled