Czy ktoś mógłby mi wyjaśnić lub podać linki jak za pomocą BFS znaleźć najkrótszą drogę w grafie nieskierowanym, nieważonym? Algorytm BFS chyba rozumiem, ale nie rozumiem jak można go wykorzystać do znajdowania najkrótszej ścieżki...
0
0
W BFS zawsze sprawdzasz węzeł który jest najbliżej i który jeszcze nie został sprawdzony. Przy zapamiętywaniu węzłów które przeszedłeś dodaj referencję do węzła z którego do niego dotarłeś. Jeżeli więc znajdziesz już to czego szukasz, to po referencjach jesteś wstanie odtworzyć najkrótszą powrotną drogę. Jeżeli z tego zrobisz listę i odwrócisz porządek, będziesz miał listę węzłów które musisz przejść do celu i gwarancję że jest to jedna z najkrótszych ścieżek.
0
Klasyczny BFS wcale nie znajduje ścieżki najkrótszej, a przynajmniej nie koniecznie. Szukasz modyfikacji BFSa? To już nie lepiej użyć Dijkstry? ;]
Dla grafów nieważonych BFS znajdzie najkrótszą ścieżkę. W tym celu należy zapamiętywać w każdym nowo odwiedzonym weźle "skąd przyszliśmy" i następnie odtworzyć ściezkę kiedy dojdziemy do celu. Sprawdzamy z którego węzła doszliśmy od celu, nazwijmy go węzłem X. Potem sprawdzamy z którego węzła doszliśmy do X itd aż dojdziemy do pierwszego.