Abstrak
Tugas akhir ini membahas mengenai Pembentukan Algoritma Parallel untuk menyelesaikan Masalah Jalur Terpendek. Secara umum, masalah jalur terpendek dapat dibedakan menjadi dua jenis masalah, yaitu single sourcedan all pairs, dengan ukuran masalah n (banyaknya vertex). Metode yang dipakai untuk menyelesaikan masalah jalur terpendek, yaitu metode Dijkstra dan Floyd. Metode Dijkstra dan Floyd dapat diinterpretasikan sebagai algoritma parallel yang menggunakan model Shared Memory (SM) SIMD (Single Instruction, Multiple Data), dengan N processor. Algoritma parallel Dijkstra dalam menyelesaikan masalah jalur terpendek single source menggunakan jenis akses memori EREW/CREW, memiliki kompleksitas waktu O(n log2 n), untuk N 2- n/log2 n dan O(n2/N), untuk N < n/log2 n. Dan algoritma Floyd untuk menyeselesaikan masalah jalur terpendek all pairs menggunakan jenis akses memori CREW, dalam O(n3IN) waktu, untuk N < n.
