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

##plugins.themes.academic_pro.article.main##

Author

  • Trần Quốc Chiến*

Từ khóa:

đồ thị
đồ thị mở rộng
đường đi ngắn nhất
thuật toán Dijkstra
thuật toán Bellman-Ford

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.

Tài liệu tham khảo

    [1] Trần Quốc Chiến, “Thuật toán tìm đường đi ngắn nhất trên đồ thị tổng quát”, Tạp chí Khoa học & Công nghệ, Đại học Đà Nẵng, 12(61)/2012, 16-21.
    [2] Trần Quốc Chiến, Nguyễn Mậu Tuệ, Trần Ngọc Việt, “Thuật toán tìm đường đi ngắn nhất trên đồ thị mở rộng”, Kỷ yếu Hội nghị Khoa học Quốc gia lần thứ VI “Nghiên cứu cơ bản và ứng dụng CNTT”, Huế, 20-21/6/2013, NXB Khoa học tự nhiên và Công nghệ, Hà Nội 2013. p.522-527.
    [3] Bellman, Richard: On a routing problem. Quarterly of Applied Mathematics 16 (1958): 87–90. MR 0102435.
    [4] Ford Jr., Lester R.: Network Flow Theory. Paper P-923. Santa Monica, California: RAND Corporation (August 14, 1956).
    [5] Moore, Edward F.: The shortest path through a maze, Proc. Internat. Sympos. Switching Theory 1957, Part II. Cambridge, Mass.: Harvard Univ. Press. pp. 285–292. MR 0114710.
    [6] Yen, Jin Y.: An algorithm for finding shortest routes from all source nodes to a given destination in general networks. Quarterly of Applied Mathematics 27 (1970): 526–530. MR 0253822.
    [7] Bannister, M. J., Eppstein, D.: Randomized speedup of the Bellman–Ford algorithm (PDF). Analytic Algorithmics and Combinatorics (ANALCO12), Kyoto, Japan (2012). pp. 41–47. arXiv:1111.5414
    [8] Bang-Jensen, Jørgen, Gutin, Gregory: Section 2.3.4: The Bellman-Ford-Moore algorithm. Digraphs: Theory, Algorithms and Applications (First ed. 2000). ISBN 978-1-84800-997-4.
    [9] Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L.: Introduction to Algorithms. MIT Press and McGraw-Hill., Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 24.1: The Bellman–Ford algorithm, pp. 588–592. Problem 24-1, pp. 614–615. Third Edition. MIT Press, 2009. ISBN 978-0-262-53305-8. Section 24.1: The Bellman–Ford algorithm, pp. 651–655.
Xem thêm

##plugins.themes.academic_pro.article.sidebar##

Đã Xuất bản

Nov 30, 2015
Download
PDF
Cách trích dẫn
Tran Quoc Chien*. “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ạp Chí Khoa học Và Công nghệ - Đại học Đà Nẵng, vol 11, số p.h 96.1, Tháng Mười-Một 2015, tr 84-87, https://jst-ud.vn/jst-ud/article/view/3230.

##plugins.themes.academic_pro.article.details##