SONG SONG HÓA THUẬT TOÁN DIJKSTRA TÌM ĐƯỜNG ĐI NGẮN NHẤT TỪ MỘT ĐỈNH ĐẾN TẤT CẢ CÁC ĐỈNH
Abstract
Nội dung chính của bài báo tập trung xây dựng thuật toán song song tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh của đồ thị liên thông dựa trên thuật toán tuần tự Dijkstra. Ý tưởng của thuật toán là sử dụng m bộ xử lý tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh trên đồ thị. Trong m bộ xử lý chọn một bộ xử lý đóng vai trò trung tâm thực hiện việc quản lý dữ liệu, chia n đỉnh và ma trận trọng số của đồ thị cho m bộ xử lý để tìm đường đi ngắn nhất.
References
. Trần Quốc Chiến, Hồ Xuân Bình, Thuật toán song song tìm luồng cực đại, Tạp chí Khoa học & Công nghệ, Đại học Đà Nẵng, 5(22), (2007), 37-42.
. Trần Quốc Chiến, Trần Thị Mỹ Dung, Ứng dụng thuật toán tìm đường đi ngắn nhất Đa nguồn đích tìm luồng cực đại đa hàng hóa đồng thời, Kỷ yếu hội thảo khoa học Công nghệ Thông tin, Trường Đại học Sư Phạm Đà Nẵng, 11/2011.
. Tom Wilson, Nicholas Hofbauer, Dijkstra’s Algorithm in Parallel, team report 2008 (http://www.cs.rit.edu/~ark/winter2008/531/team/u8/TeamReport.pdf).
. A. Grama, A.Gupta, G.Karypis, V.Kumar, Introduction to Parallel Computing, 2003.
. Seyed H. Roosta, Parallel Processing and Parallel Algorithms, Theory and Computation, Springer 1999.
. Joseph JáJá, An Introduction to Parallel Algrithms, Addison - Wesley, 1992.
. Alistair K Phipps, Parallel algorithms for geometric shortest path problems, Master of Science Computer Science School of Informatics University of Edinburgh, 2004.
. Behrooz Parhami, Introduction to Parallel Processing (Algorithms and Architectures), University of California at Santa Barbara Santa Barbara, California, 2002.
