W tej implementacji dla każdego wierzchołka w grafie pamiętamy listę jego sąsiadów zwaną listą sąsiedztwa. Innymi słowy, graf jest pamiętany w tablicy list \( L[1..n] \), gdzie \( L[i] \) jest listą sasiedztwa wierzchołka \( i \). W przypadku grafu z wagami, jeśli wierzchołek \( j \) występuje na liście wierzchołka \( i \), to z wystąpieniem wierzchołka \( j \) związana jest waga krawędzi \( i-j \). Kolejność wierzchołków na liście może być dowolna. Zauważmy, że suma długości list sąsiedztw wynosi \( 2m \), a zatem rozmiar struktury danych reprezentującej graf wynosi \( O(n+m) \) i jest on liniowy ze względu na rozmiar danych. Listy \( L \) można łatwo zbudować w czasie liniowym. Jeśli więc chcemy uzyskiwać algorytmy, których złożoności jak najlepiej zależą od rozmiaru grafu, a w szczególności są liniowe ze względu na ten rozmiar, należy reprezentować graf przez listy sąsiedztw.
Możemy teraz powrócić do problemu najlżejszych ścieżek i zająć się implementacją schematu Dijkstry.