Song_song_hoá thuật_toán Dijkstra trên đồ_thị includeonly includeonly Bối_cảnh thực_tế Bài_toán tìm đường đi ngắn nhất giữa hai đỉnh của đồ_thị liên_thông có nhiều ứng_dụng thực_tế như BULLET Bài_toán chọn hành_trình tiết_kiệm nhất theo tiêu_chuẩn khoảng_cách thời_gian hoặc chi_phí trên mạng giao_thông BULLET Bài_toán chọn phương_pháp tiết_kiệm nhất để đưa một hệ_thống động_lực từ trạng_thái xuất_phát đến trạng_thái đích BULLET Bài_toán lập lịch thi_công các công_đoạn trong một công_trình thi_công lớn BULLET Bài_toán lựa_chọn đường truyền tin chi_phí nhỏ nhất trong mạng thông_tin Bài_toán trở_nên phức_tạp khi số_lượng đối_tượng cần xét_duyệt tăng lên hàng triệu lần đòi_hỏi khối_lượng tính_toán lớn độ_chính_xác cao trong thời_gian_thực như dự_báo thời_tiết xử_lý thông_tin gen điều_khiển tàu_vũ_trụ điều_khiển lò phản_ứng hạt_nhân Với những bài_toán dạng này việc tính_toán xử_lý chỉ trên một bộ_vi_xử_lý hoặc trên một máy_tính không_thể đáp_ứng được yêu_cầu đặt ra Vì_vậy nhu_cầu thực_hiện tính_toán song_song để có_thể tính_toán giải quết một vấn_đề nào đó cùng lúc tại nhiều máy_tính khác nhau trở_nên cấp_thiết Do_đó việc ứng_dụng công_nghệ tính_toán song_song để tăng_tốc thời_gian xử_lý đã được nhiều nhà_khoa_học nghiên_cứu Thuật_toán khảo_sát Bài_toán tìm đường đi ngắn nhất từ một đỉnh đến tất_cả các đỉnh là một trong số các bài_toán tối_ưu trên đồ_thị từ bài_toán thực_tế trên Được nhà_khoa_học máy_tính Hà_Lan Edsger_Dijkstra đề_xuất và giải_quyết gọi là thuật_toán Dijkstra_Thuật toán có độ phức_tạp là O n Do độ phức_tạp tính_toán cao việc giải bài_toán này với tính_chất tuần_tự gặp phải bất_lợi lớn về thời_gian thực_hiện chương_trình tốc_độ xử_lý khả_năng lưu_trữ đặc_biệt là trên đồ_thị có hàng ngàn đỉnh mà thời_gian chạy phải được rút_gọn thì thuật_toán tuần_tự không thực_hiện được Điều này đặt ra yêu_cầu phải chia đồ_thị cho nhiều bộ_xử_lý tham_gia tính_toán đồng_thời điều đó có nghĩa là phải cải_tiến thuật_toán từ tuần_tự nghiên_cứu tìm ra các tiến_trình cần xử_lý song_song trên đa bộ_xử_lý để tăng tốc_độ và hiệu_quả của giải_thuật Nội_dung thuật_toán Thuật_toán tìm đường đi ngắn nhất từ đỉnh i đến đỉnh j Xét đồ_thị G V E với các cạnh có trọng_số không âm BULLET Dữ_liệu nhập Cho thuật_toán là ma_trận trọng_số L với quy_ước L nếu không có cạnh nối từ đỉnh v đến đỉnh k và hai đỉnh i j cho trước BULLET Dữ_liệu xuất Đường đi ngắn nhất từ i đến j Thực_nghiệm thuật_toán Cho đồ_thị được biểu_diễn như sau sau khi thuật_toán thực_hiện xong thì kết_quả được ghi_nhớ lên các nhãn đỉnh tương_ứng Song_song_hoá thuật_toán Thực_nghiệm thuật_toán Tìm đường đi ngắn nhất từ đỉnh nguồn i 1 đến tất_cả các đỉnh theo thuật_toán song_song trên đồ_thị n 12 đỉnh dưới đây cho m 2 bộ_xử_lý P P trong đó P là bộ_xử_lý chính và P là bộ_xử_lý phụ
Song_song_hoá thuật_toán Dijkstra trên đồ_thị