Bellman-Ford & Floyd-Warshall

Bạn sẽ học được gì

Dijkstra nhanh nhưng "sợ" cạnh âm. Hai thuật toán ở bài này lấp khoảng trống đó: Bellman-Ford tìm đường ngắn nhất một nguồn kể cả khi có cạnh âm, và còn phát hiện chu trình âm trong O(VE). Floyd-Warshall tìm đường ngắn nhất mọi cặp đỉnh bằng quy hoạch động O(V^3).

1. Trực quan: Bellman-Ford — giãn lặp đi lặp lại

Dijkstra chốt mỗi đỉnh đúng một lần. Bellman-Ford "an toàn" hơn: nó giãn TẤT CẢ các cạnh, lặp lại như vậy V-1 lần. Mỗi vòng, thông tin về đường ngắn nhất lan thêm được một cạnh nữa.

   Vi sao V-1 vong?
   Mot duong ngan nhat khong lap dinh co toi da V-1 canh.
   Sau V-1 vong gian toan bo, moi dist deu da on dinh.

   Vong them (vong thu V): neu con gian duoc nua
   => co CHU TRINH AM (di vong vo han de giam chi phi).

Vì cạnh u -> v được kiểm tra ở mọi vòng, cạnh âm cũng được xử lý đúng — không cần giả định tham lam như Dijkstra.

2. Bellman-Ford — cơ chế

Bước	Hành động
Khởi tạo	dist[src] = 0, các đỉnh khác là vô cực
Lặp V-1 lần	Với MỌI cạnh u -> v trọng số w: nếu dist[u] + w < dist[v] thì cập nhật
Kiểm tra vòng V	Nếu vẫn còn cạnh giãn được → có chu trình âm

3. Chạy debug: Bellman-Ford

🐞 Bellman-Ford (có cạnh âm) từ ABước 1/7

1edges = [("A","B",4), ("A","C",5), ("B","C",-3), ("C","D",2)]
2dist = {"A":0, "B":9e9, "C":9e9, "D":9e9}
3for i in range(3):          # V-1 = 3 vong
4  for u, v, w in edges:
5      if dist[u] + w < dist[v]:
6          dist[v] = dist[u] + w

Biến tại bước này

dist	A:0 B:inf C:inf D:inf

👉 Khởi tạo: chỉ nguồn A = 0.

4. Code chạy được

Đang tải trình chạy code…

5. Floyd-Warshall — mọi cặp đỉnh

Khi cần khoảng cách giữa mọi cặp đỉnh, chạy Bellman-Ford từ mỗi nguồn khá tốn. Floyd-Warshall giải gọn bằng quy hoạch động trên một ma trận D.

Ý tưởng: lần lượt cho phép dùng từng đỉnh k làm đỉnh trung gian. Với mỗi cặp (i, j), hỏi: đi qua k có rẻ hơn không?

   D[i][j] = min( D[i][j],  D[i][k] + D[k][j] )
                   |             |
              khong qua k    di vong qua k

   Ba vong long nhau: k ngoai cung, roi i, roi j  => O(V^3)

Đang tải trình chạy code…

Lưu ý thứ tự vòng lặp

Đỉnh trung gian k phải là vòng ngoài cùng. Đảo k vào trong sẽ cho kết quả sai vì khi xét cặp (i,j) ta cần D[i][k] và D[k][j] đã tính với mọi trung gian nhỏ hơn k.

6. Phân tích & so sánh

Thuật toán	Bài toán	Thời gian	Cạnh âm?
Dijkstra	1 nguồn	O(E log V)	Không
Bellman-Ford	1 nguồn	O(VE)	Có (+ phát hiện chu trình âm)
Floyd-Warshall	Mọi cặp	O(V^3)	Có (không có chu trình âm)

Bẫy thường gặp:

• Bellman-Ford: quên kiểm tra dist[u] != INF → cộng vô cực sai.
• Floyd-Warshall: đặt k không ở vòng ngoài cùng → kết quả sai.

7. Mẫu nhận diện

• "Cạnh có trọng số âm", "phát hiện chu trình âm", chênh lệch tỉ giá → Bellman-Ford.
• "Khoảng cách giữa mọi cặp đỉnh", đồ thị nhỏ (V vài trăm) → Floyd-Warshall.
• Đồ thị lớn, cạnh không âm, một nguồn → vẫn dùng Dijkstra cho nhanh.

8. 🎮 Trò chơi: Đường đi ngắn nhất nâng cao

🎮 Bellman-Ford & Floyd-WarshallCâu 1/4· Điểm 0· 🔥 0

Bellman-Ford: 1 nguồn, chịu cạnh âm, O(VE). Floyd-Warshall: mọi cặp, O(V^3).

Vòng giãn thứ V (vòng thêm) còn cải thiện được nghĩa là?

9. Quiz kiểm tra nhanh

📝 Quiz kiểm tra nhanh

1. Ưu thế của Bellman-Ford so với Dijkstra là?

2. Độ phức tạp của Floyd-Warshall là?

3. Công thức cập nhật của Floyd-Warshall cho cặp (i, j) qua k là?

10. Hoàn thành

…

☑️ Tiếp theo: 3.3.6 — Cây khung nhỏ nhất: Prim & Kruskal.