Który algorytm służy do wyszukiwania najkrótszej drogi w grafie?
Który algorytm służy do wyszukiwania najkrótszej drogi w grafie?
Wyjaśnienie i uzasadnienie dydaktyczne
Poprawna odpowiedź: A
Uzasadnienie i szersze wyjaśnienie:
Algorytm Dijkstry to klasyczny i jeden z najbardziej znanych algorytmów grafowych, służący do znajdowania najkrótszej ścieżki z jednego, startowego wierzchołka do wszystkich pozostałych wierzchołków w grafie ważonym, w którym wagi krawędzi są nieujemne. Jest on szeroko stosowany np. w nawigacji GPS i routingu sieciowym.
Dlaczego pozostałe odpowiedzi są nieprawidłowe?
- B. Algorytm Kruskala i D. Algorytm Prima służą do znajdowania minimalnego drzewa rozpinającego (MST), a nie najkrótszej ścieżki.
- C. Algorytm Floyda-Warshalla również znajduje najkrótsze ścieżki, ale między wszystkimi parami wierzchołków, a nie z jednego źródła.
Chcesz poćwiczyć całą kwalifikację INF.04?
Egzamin próbny na czas, nauka działami, losowe pytanie albo przegląd całej bazy — wszystko w przeglądarce i bez zakładania konta.
Pojęcia z tego pytania
- Algorytmy Najkrótszej Ścieżki w Grafie (Dijkstra, Bellman-Ford)Algorytmy wyznaczające trasę o najmniejszej sumarycznej wadze krawędzi między wierzchołkami w grafie ważonym (np. algorytm Dijkstry dla wag nieujemnych).
- Pojęcie i Cechy AlgorytmuUporządkowany, skończony i jednoznaczny ciąg instrukcji i kroków postępowania prowadzący do rozwiązania określonego problemu obliczeniowego dla poprawnych danych wejściowych.
- Zmienne i Stałe w programowaniuNazwane obszary pamięci operacyjnej przechowujące dane robocze programu; zmienne pozwalają na modyfikację wartości podczas działania, podczas gdy stałe mają wartość niezmienną.
Podobne pytania z działu „Algorytmy sortowania i wyszukiwania”
Ten sam obszar materiału z kwalifikacji INF.04. W całej bazie znajdziesz 23 pytań z tego działu.
- #93
Aby zaprojektować zestaw danych do zainicjowania algorytmu sortowania bąbelkowego tablicy, należy zastosować przynajmniej typy:
- #103
Metoda poszukiwań w tablicach posortowanych, która polega na podzieleniu tablicy na kilka bloków i wyszukaniu liniowym tylko w tym bloku, w którym docelowy element może się znajdować, w języku angielskim nosi nazwę
- #129
Który z wymienionych algorytmów działających na tablicy jednowymiarowej ma złożoność obliczeniową O(n2)?
- #143
Strategia budowania algorytmu poprzez podział na dwa lub więcej mniejszych podproblemów tak długo, aż fragmentu staną się proste do bezpośredniego rozwiązania jest metodą:
- #144
Z tabeli przedstawiającej złożoność obliczeniową algorytmów sortowania na dowolnym, dużym, zbiorze wejściowym (ponad 100 elementów) wynika, że najszybszą metodą jest algorytm sortowania: