dijkstra_editorial

Khoi tao: dat $d[A] = 0$ (dinh nguon), cac dinh con lai $d = \infty$. Dua $A$ vao priority queue.

Settle $A$. Relax canh $A \to B$ (trong so $4$): $d[B] = \min(\infty, 0 + 4) = 4$.

Relax canh $A \to C$ (trong so $2$): $d[C] = \min(\infty, 0 + 2) = 2$. Hoan tat xu ly $A$. Dinh co $d$ nho nhat trong queue la $C$ voi $d[C] = 2$.

Pop $C$ (key $= 2$) tu priority queue. Settle $C$ – day la khoang cach ngan nhat chinh xac vi moi trong so deu khong am.

Relax canh $C \to B$ (trong so $1$): $d[B] = \min(4, 2 + 1) = 3$. Duong vong $A \to C \to B$ ngan hon canh truc tiep $A \to B$.

Relax canh $C \to D$ (trong so $3$): $d[D] = \min(\infty, 2 + 3) = 5$. Tam thoi – co the tim duong ngan hon qua $B$.

Relax canh $C \to E$ (trong so $5$): $d[E] = \min(\infty, 2 + 5) = 7$. Tam thoi. Hoan tat xu ly $C$.

Pop $B$ (key $= 3$). Settle $B$. Queue con lai: $D = 5$, $E = 7$.

Relax canh $B \to D$ (trong so $7$): $d[D] = \min(5, 3 + 7) = 5$. Khong cap nhat – duong qua $C$ van ngan hon. Hoan tat xu ly $B$.

Pop $D$ (key $= 5$). Settle $D$. Queue con lai: $E = 7$.

Relax canh $D \to E$ (trong so $1$): $d[E] = \min(7, 5 + 1) = 6$. Cap nhat! Duong $A \to C \to D \to E$ ngan hon $A \to C \to E$.

Pop $E$ (key $= 6$). Settle $E$. Priority queue rong – tat ca dinh da duoc xu ly.

Hoan tat! Khoang cach ngan nhat: $d = [0, 3, 2, 5, 6]$. Cay duong di ngan nhat: $A \to C$, $C \to B$, $C \to D$, $D \to E$. Cac canh dim khong thuoc cay SPT.