- Hiện tại
- Đã có khoảng cách
- Cạnh đã dùng
- Đường đi
- Chu trình âm
Thuật toán Bellman–Ford
Thuật toán Dijkstra thất bại khi có cạnh mang độ dài âm, giống như một con đường trả tiền cho bạn thay vì thu phí. Thuật toán Bellman–Ford thì không: nó chỉ đơn giản xét đi xét lại mọi cạnh cho đến khi không còn gì cải thiện, và thậm chí còn biết khi nào một chu trình khiến khoảng cách giảm mãi. Nhấp vào một đỉnh để bắt đầu từ đó và đi qua từng lượt. Nhấn Phát để xem quá trình tìm kiếm, hoặc dùng Bước và Lùi để đi từng bước. Kéo thanh trượt bước để nhảy đến bất kỳ đâu. Mọi cạnh đều là cạnh một chiều, như mũi tên cho thấy, và số trên cạnh là độ dài của nó, có thể âm. Nhấp vào một đỉnh để chọn làm điểm xuất phát; chuyển thao tác nhấp sang Đích rồi nhấp vào đỉnh khác để xem đường đi ngắn nhất đến đó khi kết thúc. Số trên mỗi đỉnh là khoảng cách tìm được đến lúc đó. Đánh dấu Thêm chu trình âm để xem Bellman–Ford tìm ra nó thế nào. Đồ thị mới tạo một đồ thị khác; chọn số đỉnh và số cạnh. Khi bảng đang được chọn, phím mũi tên đi từng bước, phím cách phát và tạm dừng, còn Home và End nhảy về đầu và cuối.
Cách nó hoạt động
- Nhấp vào một đỉnh để chọn làm điểm xuất phát. Để xem đường đi khi kết thúc, chuyển thao tác nhấp sang Đích rồi nhấp vào đỉnh khác.
- Nhấn Phát, hoặc dùng Bước và Lùi để đi từng bước. Kéo thanh trượt bước để nhảy đến bất kỳ đâu.
- Đánh dấu Thêm chu trình âm để xem Bellman–Ford tìm ra nó. Đồ thị mới tạo một đồ thị khác để thử.
Bellman–Ford hoạt động thế nào
Gán cho điểm xuất phát khoảng cách 0 và mọi đỉnh khác vô cùng. Rồi chạy từng lượt: trong mỗi lượt, xét mỗi cạnh u → v một lần. Nếu u có khoảng cách và dist(u) cộng độ dài cạnh ngắn hơn dist(v), giảm dist(v) và ghi nhớ u là đường đến đó. Sau lượt k, mọi đường đi ngắn nhất dùng tối đa k cạnh đều đã biết. Một đường đi ngắn nhất đi qua mỗi đỉnh tối đa một lần, nên có tối đa n − 1 cạnh, và n − 1 lượt luôn đủ. Nếu cả một lượt không thay đổi gì, quá trình tìm kiếm có thể dừng sớm.
Tìm chu trình âm
Nếu các cạnh của một chu trình cộng lại nhỏ hơn không, đi thêm một vòng luôn làm đường đi ngắn hơn, nên hoàn toàn không có đường đi ngắn nhất. Bellman–Ford nhận ra điều này: sau n − 1 lượt, thêm một lượt nữa lẽ ra không thay đổi gì. Nếu vẫn còn cạnh nới lỏng được, có một chu trình âm đến được từ điểm xuất phát, và lần ngược theo các đỉnh đã ghi nhớ từ cạnh đó sẽ dẫn vào chu trình. Trong ứng dụng, chu trình được vẽ màu đỏ.
Câu hỏi thường gặp
Thuật toán Bellman–Ford là gì?
Một thuật toán tìm đường đi ngắn nhất từ một điểm xuất phát đến mọi đỉnh khác trong đồ thị mà các cạnh có thể có độ dài âm. Nó nới lỏng mọi cạnh qua nhiều lượt lặp lại, và báo cáo chu trình âm nếu có một chu trình như vậy đến được từ điểm xuất phát.
Vì sao thuật toán Dijkstra thất bại với cạnh âm?
Dijkstra cố định khoảng cách của một đỉnh ngay khi nó là đỉnh gần nhất trong hàng đợi. Một cạnh âm tìm thấy sau đó vẫn có thể dẫn quay lại đỉnh đó bằng đường ngắn hơn, nên khoảng cách đã cố định có thể sai. Bellman–Ford không bao giờ cố định khoảng cách quá sớm; nó cứ tiếp tục xét mọi cạnh.
Vì sao là n − 1 lượt?
Một đường đi ngắn nhất không bao giờ cần đi qua một đỉnh hai lần, nên có tối đa n − 1 cạnh. Mỗi lượt kéo dài các đường đi ngắn nhất đã biết thêm ít nhất một cạnh, nên sau n − 1 lượt tất cả đều được tìm ra.
Bellman–Ford nhanh đến mức nào?
Mỗi lượt xét cả E cạnh và có tối đa V − 1 lượt, nên khối lượng công việc tăng theo V × E. Như vậy chậm hơn thuật toán Dijkstra, đó là lý do Bellman–Ford được dùng khi cạnh có thể âm.
Đồ thị của tôi có bị gửi đi đâu không?
Không. Đồ thị được tạo và tìm kiếm ngay trong trình duyệt của bạn, và cài đặt gần nhất được lưu trong bộ nhớ cục bộ của trình duyệt này.
Sẵn sàng thử chưa?
Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.
Tới trình chỉnh sửa