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 Bellmana-Forda o pesymistycznej złożoności obliczeniowej A*, używający heurystyki, wykorzystujący sortowanie topologiczne z relaksacją (dla skierowanych grafów acyklicznych) o pesymistycznej złożoności obliczeniowej 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 Floyda-Warshalla o pesymistycznej złożoności obliczeniowej Johnsona o pesymistycznej złożoności obliczeniowej 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
N