Müxtəlif tilçəkili çəkili qraf üçün başqa alət lazımdır: BFS tilləri sayır, çəkiləri yox. Deykstra alqoritmi bütün çəkilər mənfi olmayanda bir başlanğıc təpədən qalan hamıya ən qısa yolları tapır. Qraflar Qrafların təsviri mövzusundakı kimi saxlanır: graph[u] (v, w) cütlərinin siyahısıdır.

Çəkili qraf və A-dan Deykstranın izi
Çəkili qraf və A-dan Deykstranın izi

İdeya

Hər təpə üçün dist indiyədək məlum ən yaxşı məsafəni saxlayır: başlanğıc üçün 0, qalanlar üçün ∞. Hər addımda alqoritm hələ qəti olmayan və ən kiçik dist-li u təpəsini götürür. Çəkilər mənfi deyil, ona görə u-ya daha qısa yol sonradan tapılmaz: dist[u] qətidir. Sonra hər u -> v tili relaksasiya olunur: dist[u] + w < dist[v] olarsa, dist[v]-ni yeniləyirik. Min-yığın ən kiçik dist-i tez tapır.

heapq ilə həyata keçirmə

Yığında (məsafə, təpə) cütləri var. heapq-da decrease-key əməliyyatı yoxdur, ona görə yaxşılaşma olanda sadəcə yeni cüt əlavə edirik, köhnəlmiş cütü isə çıxaranda d > dist[u] yoxlaması ilə atırıq.

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