Stosując BFS do ważonych wykresy

Question

ja przeglądu najkrótszej ścieżki algorytmów jednego źródła oraz video, nauczyciela wspomina, że ​​BFS/DFS nie może być wykorzystane bezpośrednio do znalezienia najkrótszych ścieżek w ważona wykres (I zgadnij, że wszyscy to już wiedzą) i powiedział, aby sam wypracować powód.

Zastanawiam się, jaka jest dokładna przyczyna/wyjaśnienie, dlaczego nie można go zastosować do ważonych wykresów. Czy to ze względu na wagę krawędzi czy cokolwiek innego? Czy ktoś może mi wyjaśnić, ponieważ czuję się trochę zdezorientowany.

PS: Przeszedłem przez pytanie this pytanie i this pytanie.

Answer 1

Rozważmy wykres tak:

A---(3)-----B 
|   | 
\-(1)-C--(1)/ 

najkrótszej ścieżki od A do B jest przez C (z całkowitej masy 2). Normalny BFS przejdzie ścieżką bezpośrednio z punktu A do punktu B, oznaczając B jako widoczny i od A do C, oznaczając literę C, jak widać.

W następnym etapie propagowanie z C, B jest już oznaczone jako widoczne, więc ścieżka od C do B nie będzie traktowana jako potencjalnie krótsza ścieżka, a BFS poinformuje cię, że najkrótsza ścieżka od A do B ma wagę 3.

Możesz użyć Dijkstra's algorithm zamiast BFS, aby znaleźć najkrótszą ścieżkę na ważonym wykresie. Funkcjonalnie algorytm jest bardzo podobny do BFS i może być napisany w sposób podobny do BFS. Jedyną zmianą jest kolejność, w której rozpatrujesz węzły.

Na przykład na powyższym wykresie, zaczynając od A, BFS przetworzy A -> B, następnie A -> C, i zatrzyma się tam, ponieważ widoczne są wszystkie węzły.

Z drugiej strony, algorytm Dijkstry działa w następujący sposób:

1. Rozważmy -> C (ponieważ jest to waga najniższej krawędzi od a)
2. Rozważmy C -> B (ponieważ jest to najniższa waga z każdego węzła, do którego dotarliśmy do tej pory, którego jeszcze nie rozważaliśmy)
3. Rozważ i zignoruj ​​A -> B, ponieważ B było już widziane.

Należy zauważyć, że różnica leży po prostu w zamówieniu, w której sprawdzane są krawędzie. BFS rozważy wszystkie krawędzie z jednego węzła przed przejściem do innych węzłów, podczas gdy Algorytm Dijkstry zawsze rozważyć najniższą masy niewidzialny kant, ze zbioru krawędzi podłączonego do wszystkie węzły, które były widoczne tak daleko.Brzmi to dziwne, ale pseudokod jest bardzo prosta:

create a heap or priority queue 
place the starting node in the heap 
dist[2...n] = {∞} 
dist[1] = 0 
while the heap contains items: 
    vertex v = top of heap 
    pop top of heap 
    for each vertex u connected to v: 
     if dist[u] > dist[v] + weight of v-->u: 
      dist[u] = dist[v] + weight of edge v-->u 
      place u on the heap with weight dist[u] 

Ten GIF z Wikipedii zapewnia dobrą wizualizację tego, co się dzieje:

Zauważ, że wygląda to bardzo podobny do kodu BFS, jedyną istotną różnicą jest użycie sterty, posortowanej według odległości do węzła, zamiast zwykłej struktury danych kolejki o nazwie.

Answer 2

Chociaż to prawda, ale można użyć BFS/DFS w ważonych wykresach, z niewielkimi zmianami na wykresie, jeśli ciężary wykresie są dodatnimi liczbami całkowitymi można zastąpić przewagę z masy n z n krawędziami o masie 1 z n-1 środku węzły. Coś takiego:

A-(4)-B 

będą:

A-(1)-M1-(1)-M2-(1)-M3-(1)-B 

I nie uważają tych środkowych węzłów (jak M1, M2, M3) w swoich ostatecznych wyników BFS/DFS.

---

Ten algorytm złożoność wynosi O (V * M) i M to maksymalna waga naszych brzegów, jeśli wiemy, że w naszych poszczególnych wykresach M<log V algorytm ten może być considerd, ale ogólnie ten algorytm może nie mieć taki dobry występ.