Song song hóa thuật toán Dijkstra trên đồ thị
<includeonly></includeonly>

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ư: 

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.

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.

Xét đồ thị G(V,E) với các cạnh có trọng số không âm.

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.

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ụ.
