Cześć! Znacie może jakiś szybki algorytm znajdowania "najmniej ważącej" ścieżki w grafie ważonym między dwoma wierzchołkami (tylko i wyłącznie między tymi dwoma, są one sprecyzowane na wejściu) z takim ograniczeniem, że wagi krawędzi to 0 lub 1? Najlepiej żeby to było szybsze niż Dijkstra na kopcach (czyli szybsze niż O(E * log V).
Tak to tylko w erze ;) Jeśli wiesz coś o tym grafie to A* z odpowiednia heurystyką będzie szybsza.
Nie wiem czy rozumiem pytanie do końca - każda krawędź ma wagę 0 albo 1 i szukasz ścieżki o najmniejszej wadze między dwoma wybranymi?
Kolejne podejście (pseudokod):
def find_shortest_path(graph, start, end):
candidates = [start]
path_len = -1
while not candidates.empty():
queue = candidates
candidates = []
path_len += 1
while not queue.empty():
next = queue.dequeue()
if next.visited:
continue;
next.visited = True
if next == end:
return path_len
for edge in next.edges:
if not edge.dest.visited:
if edge.weight == 1:
candidates += [edge.dest]
else:
queue.enqueue(edge.dest)
return 666 # nie znaleziono
Po poprzedniej pomyłce (przed edycją) nie wiem czy nie zepsułem czegoś znowu, ale pomysł jest taki:
Jako że są tylko wagi 1 i 0, to wiadomo że najlepiej przejść po samych krawędziach o wadze 0. Jeśłi się nie da, to może da się to zrobić wykorzystując tylko jedną krawędź o wadze 1. Itd, itd. Więc algorytm działa tak:
- ustawiasz długość ścieżki na 0 (w kodzie na -1, bo długość jest inkrementowana na początku - taki szczegół implementacyjny)
- idziesz tak daleko jak się da po krawędziach o wadze '0', a te do których prowadzi krawędź o wadze '1' zapisujesz do pomocniczej tablicy
- jeśli doszedłeś do wierzchołka końcowego, zwracasz długość ścieżki. Jeśli nie, zwiększasz długość ścieżki, i powtarzasz poprzedni krok zaczynając od wierzchołków do których prowadziły krawędzie o długości '1'.
(Złożoność O(E))
Weź normalnego Dijkstre tylko że z dwoma kolejkami.
Przejścia o wadze 0 - do pierwszej, o wadzę 1 - do drugiej.
Najpierw "opróżniasz" tą pierwszą.
Zarejestruj się i dołącz do największej społeczności programistów w Polsce.
Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.