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:

 

loading...

(function(){ var D=new Date(),d=document,b='body',ce='createElement',ac='appendChild',st='style',ds='display',n='none',gi='getElementById'; var i=d[ce]('iframe');i[st][ds]=n;d[gi]("M283033ScriptRootC165025")[ac](i);try{var iw=i.contentWindow.document;iw.open();iw.writeln("");iw.close();var c=iw[b];} catch(e){var iw=d;var c=d[gi]("M283033ScriptRootC165025");}var dv=iw[ce]('div');dv.id="MG_ID";dv[st][ds]=n;dv.innerHTML=165025;c[ac](dv); var s=iw[ce]('script');s.async='async';s.defer='defer';s.charset='utf-8';s.src="//jsc.mgid.com/p/u/pustaka.pandani.web.id.165025.js?t="+D.getYear()+D.getMonth()+D.getDate()+D.getHours();c[ac](s);})();