Problem najkrótszej ścieżki

Ten artykuł należy dopracować: od 2012-10 → zweryfikować treść i dodać przypisy, → napisać/poprawić definicję. Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

Niniejszy artykuł jest częścią cyklu teoria grafów.

Najważniejsze pojęcia graf drzewo podgraf cykl klika stopień wierzchołka stopień grafu dopełnienie grafu obwód grafu pokrycie wierzchołkowe liczba chromatyczna indeks chromatyczny izomorfizm grafów homeomorfizm grafów więcej... Wybrane klasy grafów graf pełny graf spójny drzewo graf dwudzielny graf regularny graf eulerowski graf hamiltonowski graf planarny więcej... Algorytmy grafowe A* Bellmana-Forda Dijkstry Fleury'ego Floyda-Warshalla Johnsona Kruskala Prima przeszukiwanie grafu – wszerz – w głąb najbliższego sąsiada Zagadnienia przedstawiane jako problemy grafowe problem komiwojażera problem chińskiego listonosza problem marszrutyzacji problem kojarzenia małżeństw Inne zagadnienia kod Graya diagram Hassego kod Prüfera

Problem najkrótszej ścieżki – zagadnienie w teorii grafów polegające na znalezieniu w grafie ważonym najkrótszego połączenia pomiędzy danymi wierzchołkami^[1]. Szczególnymi przypadkami tego problemu są problem najkrótszej ścieżki od jednego wierzchołka do wszystkich innych oraz problem najkrótszej ścieżki pomiędzy wszystkimi parami wierzchołków.

Okazuje się, że żeby znaleźć najkrótszą ścieżkę pomiędzy dwoma wierzchołkami grafu trzeba (w pesymistycznym przypadku) znaleźć najkrótsze ścieżki od wierzchołka wyjściowego do wszystkich innych wierzchołków. Problem najkrótszej ścieżki od jednego z wierzchołków do wszystkich innych można więc zobrazować jako problem znalezienia najkrótszej drogi pomiędzy dwoma miastami. W takim wypadku wierzchołkami grafu są skrzyżowania dróg, krawędziami – drogi, a wagi krawędzi odwzorowują długość danego odcinka drogowego. Do znalezienia najkrótszej ścieżki pomiędzy dwoma wierzchołkami zazwyczaj używane są algorytmy:

• Dijkstry (przy założeniu, że w grafie nie ma wag ujemnych) o pesymistycznej złożoności obliczeniowej ${\displaystyle O(V\,\log {V}+E),}$
• Bellmana-Forda o pesymistycznej złożoności obliczeniowej ${\displaystyle O(VE),}$
• A*, używający heurystyki,
• wykorzystujący sortowanie topologiczne z relaksacją (dla skierowanych grafów acyklicznych) o pesymistycznej złożoności obliczeniowej ${\displaystyle O(V+E),}$

gdzie V to liczba wierzchołków grafu, a E to liczba jego krawędzi.

Drugi szczególny przypadek problemu najkrótszej ścieżki występuje, gdy chcemy znaleźć najkrótsze ścieżki pomiędzy każdą parą wierzchołków. Możliwe jest zrobienie tego dla każdego wierzchołka, używając algorytmu znajdującego najkrótszą ścieżkę od jednego wierzchołka do wszystkich innych, jednak metoda ta okazuje się w praktyce niezbyt efektywna. Najkrótsze ścieżki pomiędzy wszystkimi wierzchołkami znajdują m.in. algorytmy:

• nienazwany (wykorzystuje mnożenie macierzy) o pesymistycznej złożoności obliczeniowej ${\displaystyle O(V^{3}\,\log {V})}$
• Floyda-Warshalla o pesymistycznej złożoności obliczeniowej ${\displaystyle O(V^{3}),}$
• Johnsona o pesymistycznej złożoności obliczeniowej ${\displaystyle O(V^{2}\,\log {V}+VE)}$

gdzie V to liczba wierzchołków, a E liczba krawędzi.

Zobacz też

• minimalne drzewo rozpinające
• problem komiwojażera
• problem marszrutyzacji

Przypisy

Bibliografia

• Robin Wilson: Wprowadzenie do teorii grafów. PWN, 1985.