Dengan melakukan algoritma secara paralel didapatkan efektifitas dan kecepatan yang
lebih tinggi daripada algoritma serial. Masalah pencarian rute terpendek untuk graf statis
berskala besar dapat dilakukan dengan menggunakan algoritma yang dijalankan secara
paralel. Dua algoritma yang dapat digunakan adalah algoritma Dijkstra yang bersifat
greedy dan algoritma Bellman-Ford yang menggunakan dynamic programming. Dijkstra
lebih sulit diparalelkan namun memiliki waktu eksekusi yang relatif lebih cepat
dibandingkan Bellman-Ford yang mudah diparalelkan namun waktu eksekusinya lebih
panjang. Optimasi kedua algoritma dilakukan dengan menyimpan data graf dalam bentu
Compact Spare Row, dan mendesain algoritma agar membagi data antar prosesor dengan
efisien dan meminimalisir komunikasi antar prosesor.
Kata Kunci: paralel, shortest path, graf, algoritma Dijkstra, algoritma Bellman-Ford,
performansi,Compact Sparse Row.