Для взвешенного графа с разными весами рёбер нужен другой инструмент: BFS считает рёбра, а не веса. Алгоритм Дейкстры находит кратчайшие пути от одной стартовой вершины ко всем остальным, когда все веса неотрицательны. Графы хранятся как в теме Представление графов: graph[u] — список пар (v, w).

Взвешенный граф и трассировка Дейкстры из A
Взвешенный граф и трассировка Дейкстры из A

Идея

Для каждой вершины dist хранит лучшее известное расстояние: 0 у старта, ∞ у остальных. На каждом шаге алгоритм берёт ещё не окончательную вершину u с наименьшим dist. Веса неотрицательны, поэтому более короткий путь к u позже не найдётся: dist[u] окончателен. Затем каждое ребро u -> v релаксируется: если dist[u] + w < dist[v], обновляем dist[v]. Min-куча быстро находит наименьший dist.

Реализация на heapq

В куче лежат пары (расстояние, вершина). В heapq нет операции decrease-key, поэтому при улучшении мы просто кладём новую пару, а устаревшую пару отбрасываем при извлечении проверкой d > dist[u].

python
INF = float("inf")
graph = {
    "A": [("B", 7), ("C", 9), ("F", 14)],
    "B": [("A", 7), ("C", 10), ("D", 15)],
    "C": [("A", 9), ("B", 10), ("D", 11), ("F", 2)],
    "D": [("B", 15), ("C", 11), ("E", 6)],
    "E": [("D", 6), ("F", 9)],
    "F": [("A", 14), ("C", 2), ("E", 9)],
}

import heapq