Module 1 — Bellman-Ford: relax tất cả cạnh, V−1 vòng
Nguồn = đỉnh 0 (xanh lá). Mỗi vòng relax toàn bộ danh sách cạnh;
cạnh đang xét tô vàng, đỉnh được cập nhật dist nhấp nháy. Bảng dist bên dưới cập nhật trực tiếp.
nguồn
vừa cập nhật
cạnh âm (đỏ)
Bấm Chạy từng bước để relax cạnh tiếp theo.
Module 2 — Floyd-Warshall: ma trận qua từng trung gian k
Ma trận dist[i][j]. Bấm k tiếp theo để cho phép đi qua đỉnh trung gian k:
ô dist[i][j] = min(cũ, dist[i][k]+dist[k][j]). Hàng/cột k tô xanh, ô vừa giảm tô vàng.
hàng/cột k (trung gian)
ô vừa giảm
Bấm k tiếp theo để thêm đỉnh trung gian.
Module 3 — Phát hiện chu trình âm / arbitrage
Đồ thị có chu trình âm 1→2→3→1 (tổng = −3).
Bellman-Ford chạy V vòng; ở vòng thứ V còn relax được → phát hiện chu trình âm
(đường ngắn nhất = −∞). Cùng cơ chế dùng cho phát hiện arbitrage tỷ giá.
đang giảm
chu trình âm
Bấm Chạy phát hiện.