Problem najkrótszej ścieżki

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

1. Problem najkrótszej ścieżki. www.mini.pw.edu.pl. [dostęp 2016-06-24].

Bibliografia

• Robin Wilson: Wprowadzenie do teorii grafów. PWN, 1985. Brak numerów stron w książce

Kontrola autorytatywna (problem obliczeniowy):

• GND: 4138403-9

Encyklopedie internetowe:

• Britannica: topic/shortest-path-problem