Algorytmy i struktury danych · Middle · Pytanie 28 z 75
Dlaczego BFS znajduje najkrótszą ścieżkę w grafie bez wag?
- 1Zawsze idzie krawędzią o najmniejszej wadze
- 2Sprawdza każdą możliwą ścieżkę przed decyzją
- ✓Poprawna odpowiedź: Odwiedza wierzchołki w kolejności ich odległości od startu
Wyjaśnienie
Kolejka przetwarza wszystkie wierzchołki w odległości 1, potem w odległości 2 i tak dalej. Gdy BFS pierwszy raz dociera do wierzchołka, robi to najkrótszą ścieżką. Dla krawędzi z wagami potrzebny jest Dijkstra.