Contoh Program Algortima Dijkstra

Contoh Program Algortima Dijkstra. Kali ini saya akan membahas algoritma untuk menentukan jalur terpendek dengan menggunakan Algoritma Djikstra. Sebelumnya saya juga telah membahas Menentukan Jalur Terpendek menggunakan Algoritma Greedy. Algoritma Djikstra berbeda dengan greedy, karna djikstra kita akan menemukan jalur yang benar-benar paling optimum. Dan saya telah membuat sebuah source code PHP untuk menyelesaikan algoritma djikstra secara otomatis.
Cek di sini Program Algoritma Dijkstra.

Pertama mari kita bahas bagaimana cara kerja algoritma djikstra :

1. Buat tabel yang terdiri dari Node, status, Bobot, Total_bobot dan Predecessor (node terpilih)
2. Set semua node  dengan status =0 dan set node sumber  dengan status = 1
3. Dari node yang status =1, tentukan semua node tetangga yang status = 0 yang terhubung langsung dengan node tersebut, cek bobot dan hitung total bobot dari node yang statusnya 1  ke node yang berstatus = 0 tersebut. Sebagai contoh, jika node A ke B memiliki bobot jarak 6 dan dari B ke node C berjarak 2, maka jarak ke C melewati B menjadi 6+2=8.
4. Jika total bobot ini lebih kecil dari total bobot sebelumnya (yang telah terekam sebelumnya) hapus data lama, simpan ulang data total bobot dengan total yang baru dan tetapkan predecessornya.
5. Kemudian cek semua node yang status = 0, dan pilih node yang memiliki total bobot paling kecil. Set nilai status node tersebut dengan nilai 1. selanjutnya ulangi langkah no.3 dan 4.
6. Lakukan proses tersebut terus menerus hingga semua node memiliki status = 1.

Baiklah kita akan contohkan bagaimana cara nya.

Contoh Program Algortima Djikstra

Gambar diatas adalah graph yang akan kita gunakan. Kita akan mencari dari kota 'A' ke kota 'J' :

1. Node A merupakan node sumber maka status Node A diset dengan nilai 1, sedangkan node yang lain diset = 0
2. Dari node  “A” yang status =1, periksa semua node tetangganya. Maka terpilih : B, C, D. cek bobot dan hitung total bobot dari node “A”  tersebut.  Tetapkan Precessor untuk node B, C, D adalah node A 

1. Kemudian cek semua node yang status = 0, dan pilih node yang memiliki total bobot paling kecil. Set nilai status node tersebut dengan nilai 1. Berdasarkan hasil iterasi 1, terlihat node B memiliki total bobot paling kecil sehingga status B = 1
2. Dari node  “B” yang status =1, periksa semua node tetangganya. Maka terpilih : C, E, G. Maka bobot dan hitung total bobot untuk node tetangga tersebut. Tetapkan Precessor untuk node C, E, G adalah node B. Predecessor untuk C berubah ke Node B, karena total bobot terkecilnya pada node B. (A - C = 8,  A – B – C = 7)

1. Kemudian cek semua node yang status = 0, dan pilih node yang memiliki total bobot paling kecil. Terlihat node D memiliki total bobot paling kecil sehingga status D = 1
2. Dari node  “D” yang status =1, periksa semua node tetangganya. Maka terpilih node: E, G. Cek Bobot dan hitung total bobot untuk node tetangga tersebut. Bandingkan total bobot dari B-E = 4 dgn D-E = 9 , maka terpilih yang paling kecil ada pada B-E. Bandingkan total bobot dari B-G = 6 dgn D-G = 11 maka terpilih yang paling kecil ada pada B-G. 
3. Kesimpulannya: pada kolom E dan G tidak terjadi perubahan nilai untuk total bobot dan predecessor .

Untuk langkah selanjutnya, anda tinggal mengulangi langkah-langkah seperti sebelumnya. Hingga semua node status = 1. Saya lampirkan langkah selanjutnya hingga akhir.

Kesimpulan akhir :
Setelah semua Node statusnya berubah “1”, maka iterasi selesai. Dan node yang terpilih menjadi predecessor akan dirangkai menjadi sebuah pohon keputusan. Dengan hasil sebagai berikut:

Baiklah itulah yang dapat saya jelaskan tentang Algoritma Djikstra, Jika ada yang minat dengan source code program pembuatan algoritma, silahkan kirim permintaan melalui email saya.
Contoh Program Algortima Dijkstra.

Terima kasih telah membaca Artikel Contoh Program Algortima Dijkstra . Jika Anda ingin Copy Paste Artikel ini, Harap cantumkan Link Contoh Program Algortima Dijkstra sebagai sumbernya.
<a href="http://akbartn.blogspot.com/2015/11/contoh-program-algortima-djikstra.html">Contoh Program Algortima Dijkstra</a>

Artikel Terkait