Thuật toán Bellman-Ford cải biên tìm đường đi ngắn nhất trên mạng mở rộng

Tóm tắt

Đồ thị là công cụ toán học hữu ích ứng dụng trong nhiều lĩnh vực như giao thông, truyền thông, công nghệ thông tin, kinh tế, …. Cho đến nay, trong đồ thị mới chỉ xét đến trọng số của các cạnh, các đỉnh một cách độc lập, trong đó độ dài đường đi chỉ đơn thuần là tổng trọng số các cạnh và các đỉnh trên đường đi đó. Tuy nhiên, trong nhiều bài toán thực tế, trọng số tại một đỉnh không giống nhau với mọi đường đi qua đỉnh đó, mà còn phụ thuộc vào cạnh đi đến và cạnh đi khỏi đỉnh đó. Trong báo cáo, mô hình đồ thị mở rộng được định nghĩa.. Thuật toán Bellman-Ford là thuật toán chính tìm đường đi ngắn nhất từ một đỉnh đến các đỉnh khác, trong đó trọng số cạnh có thể âm. Trên cơ sở thuật toán Bellman-Ford tìm đường đi ngắn nhất trên đồ thị truyền thống, tác giả xây dựng và chứng minh thuật toán Bellman-Ford cải biên tìm đường đi ngắn nhất từ một đỉnh đến các đỉnh khác trên mạng đồ thị mở rộng.