Lesson 33 — Dijkstra

Đường đi ngắn nhất từ một nguồn trên đồ thị trọng số không âm. Ba module: animator (pop-min từ heap + relax cạnh, bảng dist cập nhật), BFS vs Dijkstra (vì sao BFS sai trên đồ thị weighted), và Negative edge fail (phản ví dụ cạnh âm).

1. Dijkstra animator — pop min + relax greedy + min-heap

Đồ thị 6 đỉnh (mục 4 README), nguồn = 0. Bấm Bước để pop đỉnh dist nhỏ nhất từ heap, chốt nó (finalize), rồi relax các cạnh ra. Entry stale (cũ) bị skip.

nguồn đang pop đã chốt (finalized) vừa relax chưa thăm

Bấm "Bước" để bắt đầu.

Heap: {(0, 0)}

2. BFS vs Dijkstra — vì sao BFS sai trên đồ thị weighted cạnh ≠ 1

Cùng đồ thị có trọng số. BFS đếm số cạnh (lan theo lớp) → sai khi cạnh dài khác nhau. Dijkstra đếm tổng trọng số → đúng. Bấm để chạy cả hai và so sánh dist.

BFS (đếm số cạnh)

Dijkstra (đếm trọng số)

Bấm "Chạy cả hai".

3. Negative edge fail — Dijkstra sai với cạnh âm w < 0 → SAI

Đồ thị có cạnh âm 2→1 (-2). Dijkstra-với-visited chốt đỉnh 1 quá sớm (dist=1) rồi từ chối relax lại → bỏ lỡ đường 0→2→1 = 0. Bấm để xem từng bước và đáp án đúng (Bellman-Ford).

Bấm "Bước" để chạy Dijkstra-visited.