Implementasi graf banyak digunakan pada berbagai bidang, misalnya otomotif, lalu-lintas, image processing dan sebagainya. Biasanya graf yang dihasilkan memiliki ukuran dimensi yang sangat besar, sehingga dalam pemrosesan grafnya dalam bidang tersebut diperlukan superkomputer. Dalam penetilian ini pemrosesan graf yang dilakukan adalah dengan mencari jalur terpendek antara dua vertex dengan algoritma Breadt-First Search dengan problem single destination shortest path. Penelusuran jalur pada graf diimplementasikan pada cluster superkomputer Inspur pada laboratorium High Performance Computing Ilmu Komputasi, Universitas Telkom. Data graf yang digunakan adalah berbentuk adjacency list dengan tipe data berarah dan tidak berbobot. Penelitian diuji dengan data graf berbagai ukuran dan dianalisis berdasarkan speed up dan waktu eksekusi. Hasil dari penelitian ini menunjukkan performansi dari cluster superkomputer Inspur dengan data graf yang diberikan lebih cepat hingga 90 kali dengan dieksekusi secara paralel dibandingkan serial pada eksekusi dengan jumlah 96 thread