Алгоритм Дейкстры

Алгоритм Дейкстры находит кратчайшие пути от одной вершины до всех остальных во взвешенном графе с неотрицательными весами. На каждом шаге выбирается ближайшая ещё не обработанная вершина — для этого используется приоритетная очередь (куча).

Сложность: время O((V + E) log V) с двоичной кучей; память: O(V). Не работает с отрицательными рёбрами — там нужен алгоритм Беллмана-Форда.

import heapq

def dijkstra(graph, start):
    dist = {v: float("inf") for v in graph}
    dist[start] = 0
    pq = [(0, start)]
    while pq:
        d, v = heapq.heappop(pq)
        if d > dist[v]:
            continue
        for nb, w in graph[v]:
            if d + w < dist[nb]:
                dist[nb] = d + w
                heapq.heappush(pq, (dist[nb], nb))
    return dist