Как найти кратчайший путь (Dijkstra)?

Dijkstra — кратчайший путь от одной вершины во weighted graph с неотрицательными весами. Greedy: всегда выбираем ближайшую непосещённую вершину через min-priority queue.

import heapq

def dijkstra(graph, start):
    dist = {v: float('inf') for v in graph}
    dist[start] = 0
    heap = [(0, start)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:       # устаревшая запись
            continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist

Сложность O((V+E) log V) с binary heap, O(V²) с array. Не работает с отрицательными весами — нужен Bellman-Ford O(VE), который также detect negative cycle. Все пары — Floyd-Warshall O(V³). A* — с heuristic для конкретного endpoint. Оптимизация: lazy deletion (d > dist[u]), а не удаление из heap.