Algoritma Djikstra

 Algoritma Dijkstra adalah salah satu metode untuk memecahkan masalah pencarian rute terpendek. Algoritma ini biasanya diterapkan pada sebuah aplikasi pencarian rute jalan yang terdekat dari suatu daerah kedaerah lainnya.

Algoritma ini bertujuan untuk menemukan jalur terpendek berdasarkan bobot terkecil dari satu titik ketitik lainnya. Misalkan titik mengambarkan gedung dan garis menggambarkanjalan, makaalgoritma Dijkstra melakukan kalkulasi terhadap semua kemungkinan bobot terkecil dari setiap titik. 

Untuk bisa menerapkan algoritma in idibutuhkan beberapa data yang harus disiapkan, yaitu :
x

1.     BeberapaTitik/ simpul/ daerah, titik/ simpul/ daerah yang bisa dijangkau secara langsung, dan juga jarak antara mereka.

2.     Titik/simpul/daerahawal.

3.     Titik/simpul/daerahtujuan.

Jika dicontohkan dengan gambar grafik akan sepert iini :

contoh algoritma dijkstra

Titik A adalah titik awal dan titik F adalah titik tujuan. Kemudian kita akan mencari rute manakah yang harus dilewati dan memilik total jarak yang paling dekat. Untuk bisa mendapatkan rute tu, maka grafik diatas ditambahkan beberapa kotak untuk mengisi beberapa label. Seperti ini :

contoh algoritma dijkstra

Penjelasannya adalah : 

contoh algoritma dijkstra

Setelah itu ada beberapa langkah yang harus dilakukan untuk mentukan algoritma djikstra, yaitu :

1.     Mengisikotak label pada titik awal dengan label urutan 1 dan label jarak 0.

2.     Menetapkan label jarak sementara untuk semua titik yang dapat dihubungi langsung dari awal.

3.     Pilih titik dengan label jarak sementara terkecil dan menuliskan nilainya di label jarak, serta tambahkan label urutan-nya.

4.     Masukan label jarak sementara pada setiap titik yang belum memiliki label urutan dan label jarak dan dapat dihubungi langsung dari titik yang baru saja ditulis label jarak dan label urutan-nya. nilainya diisi dengan total dari label jarak dari titik sebelumnya dan jarak dari titik tersebut. Jika label jarak sementara di titik tersebut sudah memiliki nilai, maka harus diganti hanya jika nilai yang baru lebih kecil.

5.     Pilih titik dengan label jarak sementara terkecil dan menggunakan label jarak sementara-nya sebagai label jarak dari titik tersebut, serta tambahkan label urutan-nya.

6.     Ulangi langkah 4 dan 5 hingga titik tujuan memiliki label jarak dan label urutan.

Maka pada langkah pertamaa dalah Mengisikotak label pada titik awal dengan label urutan 1 dan label jarak 0.

contoh algoritma dijkstra

Kemudian mengisi label jarak sementara titik yang dapat dihubungkan langsung dari titik A yakni titik B, C, dan E.

contoh algoritma dijkstra

Maka yang terpilih adalah titik B karena memiliki label jaraks ementara terkecil, dan mengisi nilai label jarak-nya sama dengan label jarak sementara serta memberikan label urutan-nya.

contoh algoritma dijkstra

Selanjutnya mengisi label jarak sementara titik yang belum memiliki label jarak dan dapat dihubungkan langsung dari titik B yakni hanya titik C. Label jarak sementara titik C diisi dengan total jarak dari titik A sampai ke titik C yang melalui titik B, yakni 4 + 2 = 6. Namun sebelumnya nilai label jarak sementara-nya titik C sudah ada dan lebih kecil (5), jadi label jaraks ementara-nya tidak diganti dan tetap bernilai 5.

Langkah selanjutnya adalah memilih label jarak sementara terkecil. Karena titik E dan titik C memiliki label jarak sementara yang sama yakni 5, maka bisa memilih salah satu dari kedua titik tersebut. Misal kan titik C yang dipilih, maka berikan label jarak dan label urutan-nya.

contoh algoritma dijkstra

Kemudian titik yang dapat dihubungi secara langsung dari titik C dan belum memilik label jarak adalah titik E dan D. Titik E => 5 + 1 = 6, lebih besar jika dibandingkan dengan nilai label jarak sementara yang dimiliki oleh titik E sebelumnya (5), maka nilai 6 diabaikan dan tetap diisi 5. Titik D => 5 + 2 = 7, maka langsung saja label jarak sementara titik D diisi dengan 7.

contoh algoritma dijkstra

Selanjutnya titik E terpilih karena memiliki label jarak sementara terkecil. Berikan label jarak dan label urutan-nya.

contoh algoritma dijkstra

Dan titik F dan G adalah titik yang dapat dihubungi secara langsung dari titik E dan belum memilik label jarak. Titik F => 5 + 3 = 8 dan langsung diisikan kedalam label jarak sementara-nya. sedangkan titik D => 5 + 1 = 6 dan lebih kecil dari pada nilai sebelumnya yaitu 7, maka nilai label jarak sementara-nya diganti dengan 6.

contoh algoritma dijkstra

Makatitik D terpilih karena memiliki label jarak sementara terkecil. Berikan label jarak dan label urutan-nya.

contoh algoritma dijkstra

Titik F adalah titik terakhir yang dapat dihubungi secara langsung dari titik D dan belum memilik label jarak serta merupakan titik tujuan. Titik F => 6 + 1 = 7  dan lebih kecil  dari pada nilai sebelumnya yaitu 8, maka nilai label jarak sementara-nya diganti dengan 7.

contoh algoritma dijkstra

Karena titik F adalah satuu-satunya titik terakhir yang belum mempunyai label jarak dan label urutan. maka lansung saja berikan nilai label jarak dan label urutan-nya. Dengan begitu titiktujuan sudah memiliki label jarak dan label jarak sementara.

contoh algoritma dijkstra

1. Trimakasih Semoga Contoh Algoritma Djikstra ini dapat membatu