Dijkstra zakłada, że gdy wierzchołek ma najmniejszy znany dystans, to później już się nie poprawi — ujemne wagi łamią to założenie. Dla ujemnych wag użyj Bellman–Forda (potrafi też wykryć ujemne cykle).