„To świetny algorytm” – powiedział Erika Demaine’ainformatyk w Massachusetts Institute of Technology. „Jest to bardzo szybkie, proste i łatwe do wdrożenia.”
Aby zastosować tę procedurę w praktyce, musisz wybrać system organizowania notatek – strukturę danych, w żargonie informatyki. Może to brzmieć jak drobny szczegół techniczny, ale czas spędzony na przeszukiwaniu notatek za każdym razem, gdy trzeba edytować lub usunąć wpis, może mieć duży wpływ na ogólny czas działania algorytmu.
W artykule Dijkstry wykorzystano prostą strukturę danych, która pozostawiła pole do ulepszeń. W następnych dziesięcioleciach badacze opracowali lepsze, pieszczotliwie nazwane „stertami”, w których pewne przedmioty łatwiej znaleźć niż inne. Wykorzystują fakt, że algorytm Dijkstry musi zawsze usunąć wpis dotyczący najbliższego pozostałego wierzchołka. „Sterta to w zasadzie struktura danych, która pozwala zrobić to bardzo szybko” – powiedział Václav Rozhoňbadacz w Instytucie Informatyki, Sztucznej Inteligencji i Technologii (INSAIT) w Sofii w Bułgarii.
W 1984 roku dwóch informatyków opracowało sprytny projekt sterty umożliwiło to algorytmowi Dijkstry osiągnięcie teoretycznej granicy, czyli „dolnej granicy”, czasu wymaganego do rozwiązania problemu najkrótszych ścieżek z jednego źródła. W pewnym sensie ta wersja algorytmu Dijkstry jest najlepsza z możliwych. To było ostatnie słowo w sprawie standardowej wersji problemu przez prawie 40 lat. Sytuacja zmieniła się dopiero, gdy kilku badaczy przyjrzało się bliżej, co to znaczy być „najlepszym”.
Najlepsze zachowanie
Naukowcy zazwyczaj porównują algorytmy, badając, jak radzą sobie w najgorszych scenariuszach. Wyobraź sobie najbardziej zagmatwaną siatkę ulic na świecie, a następnie dodaj kilka szczególnie kłopotliwych wzorców ruchu. Jeśli upierasz się przy znajdowaniu najszybszych tras w tych ekstremalnych okolicznościach, wersja algorytmu Dijkstry z 1984 roku jest prawdopodobnie nie do pobicia.
Miejmy jednak nadzieję, że Twoje miasto nie ma najgorszej siatki ulic na świecie. Możesz więc zapytać: czy istnieje algorytm, który jest nie do pokonania w każdej sieci drogowej? Pierwszym krokiem do odpowiedzi na to pytanie jest przyjęcie konserwatywnego założenia, że w każdej sieci występują najgorsze wzorce ruchu. Następnie chcesz, aby Twój algorytm znalazł najszybsze ścieżki w dowolnym możliwym układzie wykresu, zakładając najgorsze możliwe wagi. Naukowcy nazywają ten warunek „uniwersalną optymalnością”. Gdybyś miał uniwersalnie optymalny algorytm rozwiązujący prostszy problem polegający na przechodzeniu z jednego punktu na wykresie do drugiego, mógłby on pomóc w pokonaniu korków w godzinach szczytu w każdym mieście na świecie.
