Time and Space Complexity

Временная сложность:

• O(V² + V*E) в данном виде (каждый из V раундов сканирует вершины для поиска минимума и сканирует ребра для релаксации). С использованием бинарной кучи и списка смежности сложность улучшается до O((V + E) log V).

Пространственная сложность:

• O(V) для массивов distance и visited (плюс входные ребра).

Резюме:

• Алгоритм Dijkstra находит кратчайшие расстояния от одного источника для неотрицательных весов, жадно фиксируя ближайшую вершину и релаксируя её ребра.
• Он не работает с отрицательными ребрами; для них используйте Bellman-Ford.