MENENTUKAN LINTASAN TERPENDEK MENGGUNAKAN ALGORITMA DIJKSTRA DARI KAMPUS UNIB KE SIMPANG RS M YUNUS JALAN RAYA KOTA BENGKULU

Oleh : Dra Hanifah, M.Kom *)

Program Studi : Teknik Informatika FT UNIB

ABSTRAK

            Penelitian dengan judul Menentukan Lintasan Terpendek Menggunakan Algoritma Dijkstra dari Kampus UNIB ke Simpang RS M YUNUS Jalan Raya Kota Bengkulu bertujuan untuk  mengetahui jalan-jalan apa saja yang akan dilewati agar jarak yang ditempuh dari Kampus UNIB ke Simpang RS M YUNUS sekecil mungkin. Sebelum menentukan lintasan terpendek jalan raya di kota Bengkulu, maka jalan-jalan raya yang ada dikota Bengkulu dimodelkan atau digambarkan terlebih dahulu ke dalam  graf . Persimpangan jalan dijadikan simpul, jalan antara simpang dijadikan busur / sisi, dengan jarak antar simpang sebagai bobotnya. Untuk menentukan lintasan terpendek jalan raya dikota Bengkulu digunakan Algoritma Dijkstra dengan langkah sebagai berikut:

Langkah 0 (inisialisasi):  inisialisasi S_i = 0 dan d_i = m_v1i untuk i = 1,2, …, n

Langkah 1: isi S_v1 dengan 1 (karena simpul v₁ adalah simpul asal lintasan terpendek, jadi sudah pasti terpilih).isi d_v1 dengan  ∞ (tidak ada lintasan terpendek dari simpul v₁ ke v₁)

Langkah 2,3, …, n-1:-cari j sedemikian sehingga S_j = 0 dan d_j = min { d₁, d₂, …, d_n). Isi Si_j dengan 1.Perbarui d_i, untuk I = 1,2,3,…,n dengan: d_i(baru) = min {d,(lama), d_j + m_ji. m_ij = bobot busur (i,j), m_ii = 0, m_ij = ∞ jika tidak ada busur dari simpul i ke simpul j.

 S_i = 1, jika simpul i termasuk ke dalam lintasan terpendek

 S_i = 0, jika simpul i tidak termasuk ke dalam lintasan terpendek

 D = [_di] , dimana d_i = panjang lintasan dari simpul awal ke simpul i

Dari hasil perhitungan dengan menggunakan Algoritma Dijsktra di dapat jarak terpendek dari Kampus UNIB ke Simpang RS M YUNUS adalah 11600 m dengan lintasan sebagai berikut (Pada gambar 2 graf hasilnya adalah lintasan yang busurnya ditebalkan):

Kampus UNIB → Simpang Kampung Bali → Simpang Suka Merindu → Simpang  Jam → Simpang GOR → Simpang Panorama → Simpang Terminal Panorama → Simpang SLB  →  simpang RS M Yunus

Link:

 

Tweet