Реализация алгоритма Дейкстры

Кратчайшие пути от одной вершины s: поддерживаем dist[v] (расстояние от s), prev[v] (предыдущая вершина), приоритетную очередь (min-heap по dist). Алгоритм: dist[s]=0, остальные ∞, добавляем s в PQ. Извлекаем u с минимальным dist, для каждого соседа v релаксируем ребро (если dist[u]+w(u,v) < dist[v], обновляем dist[v] и prev[v], добавляем v в PQ). Сложность: O((V+E) log V) с бинарной кучей, O(V²) с массивом (лучше для плотных графов), O(V log V + E) с Fibonacci heap (теоретически, практически медленнее)