Algorytm Dijkstry nie działa, o ile w grafie występują krawędzie z ujemnymi wagami - w tym wypadku używa się wolniejszego, lecz z większym natężeniem ogólnego algorytmu Bellmana-Forda. o ile graf nie jest ważony (wszystkie wagi mają wielkość 1), w miejsce algorytmu Dijkstry basta model przeszukiwania grafu wszerz. model A* jest pewnym uogólnieniem algorytmu Dijkstry, które pozwala przekopywać tylko stosunek grafu, tymczasem wymaga dodatkowej wstępnej informacji (heurystyki) o odległościach wierzchołków.
Algorytm Prima znajdowania minimalnego drzewa rozpinającego wzmacniany jest o wielce podobny pomysł, co model Dijkstry.