Cara Kerja Algoritma Dijkstra

Contributor Cecilia




Step By Step Cara Kerja Algoritma Dijkstra

Algoritma Dijkstra dapat digunakan untuk menyelesaikan permasalah rute terpendek dari sebuah titik asal menuju titik tujuan dalam sebuah grafik berbobot. Rute terpendek diperoleh dari dua buah titik yang total bobotnya paling mimum atau paling kecil jika ditotalkan dari semua titik dalam jaringan grafik.

Ide dari algoritma ini sangat sederhana. Algoritma Dijkstra memilih titik (sumber) dan menetapkan kemungkinan biaya optimum (yaitu tak terhingga) ke setiap titik lainnya. Langkah berikutnya akan mencoba untuk meminimalkan biaya untuk setiap titik. Biaya yang dimaksud disini adalah jarak atau waktu yang diambil untuk mencapai titik tujuan dari titik sumber.

Berikut merupakan beberapa notasi yang digunakan dalam Algoritma Dijkstra (Dharam, 2015), yaitu: 
a. Grafik G
b. Satu set simpul atau titik V (Vertex)
c. Seperangkat sisi E (dimana setiap sisi memiliki berat non-negatif)
d. Titik awal V

Perlu diperhatikan bahwa simbol “elemen”, , menunjukkan bahwa elemen di sisi kiri simbol terkandung dalam sisi lain simbol. Misalnya, V menjelaskan bahwa s adalah elemen dari V. Berarti, dalam hal ini s adalah titik yang terdapat di dalam grafik.

Secara umum, cara kerja Algorithma Dijkstra adalah sebagai berikut:
  1. Berilah nilai bobot (jarak) dari satu titik ke titik lainnya, kemudian tentukan nilai 0 pada titik awal dan nilai tak hingga (∞) pada titik yang lain atau titik yang belum terisi.
  2. Tentukan semua titik yang belum dilewati dan aturlah titik awal sebagai titik keberangkatan.
  3.  Dari titik keberangkatan, pertimbangkan titik lain yang belum terlewati dan hitung jaraknya dari titik keberangkatan. Pada langkah ke-3 ini, misalnya titik A ke titik B memiliki nilai (jarak) 5 dan dari titik B ke titik C bernilai 2. Maka, jarak ke titik C melewati titik B adalah 5 + 2 = 7. Jika jarak ini lebih kecil dari sebelumnya yang telah dicatat, hapus data lama dan simpan ulang nilai (jarak) yang baru.
  4. Ketika setiap jarak terhadap titik lain telah dipertimbangkan, tandai titik yang telah dilewati sebagai ‘titik terlewati’. Titik terlewati tidak akan pernah diperiksa kembali, dan jarak yang disimpan adalah jarak terakhir dari titik keberangkatan dan yang paling minimal nilainya (jaraknya).
  5. Tentukan titik belum terlewati dengan nilai (jarak) terkecil dari titik keberangkatan, sebagai titik keberangkatan selanjutnya, dan lanjutkan dengan mengulang kembali langkah ke-3.


Step 1 : Pengambilan Data

          Ketika menyelesaikan Algorithma Dijkstra, dibutuhkan data untuk melakukan perhitungan nilai (jarak) minimum. Dalam hal ini, data diambil berdasarkan nilai (jarak) atau biaya yang dapat diperoleh melalui posisi koordinat suatu wilayah. Posisi koordinat dapat diambil melalui Google Maps atau layanan serupa yang memiliki pemetaan suatu wilayah.

Untuk pengambilan data ini, perlu dicatat bahwa setiap koordinat yang ambil harus bernilai positif. Jika koordinat tersebut bernilai negative, maka algorithma ini tidak dapat dilakukan. Setelah mendapatkan titik koordinat tersebut, dilakukan pencarian nilai (jarak) atau biaya antar titik yang berhubungan atau yang ada di sekitarnya.

Step 2 : Membuat Skema

           Skema merupakan suatu bentuk rancangan atau kerangka secara garis besar yang memuat gambaran umum dari apa yang akan diperhitungkan. Skema yang dibuat berupa gambar antar titik yang saling terhubung oleh garis sesuai dengan posisi koordinat yang telah didapat sebelumnya.


Gambar diatas merupakan contoh dari sebuah skema yang menggambarkan nilai (jarak) antar titik yang berhubungan. Skema diatas juga memberikan informasi bahwa nilai (jarak) tiap titik bernilai positif dan titik awal keberangkatan dimulai dari titik 1.

contoh skema


Step 3 : Membuat Tabel Perhitungan

          Langkah berikutnya adalah membuat tabel perhitungan, dimana langkah ini sangat penting karena tabel ini akan menentukan proses perhitungan secara keseluruhan. Proses perhitungan dengan tabel dapat dikatakan benar apabila jumlah step yang dilakukan berjumlah seluruh titik ditambah satu. Misal ada 6 titik, maka step yang dilakukan ada 7.

Contohnya dalam tabel ini (Girsang, 2017), yang pertama dilakukan adalah memberikan nilai awal titik keberangkatan (V1) yaitu 0, dan nilai tak hingga (∞) kepada titik yang lain. Kemudian membandingkan titik dengan nilai (jarak) terkecil dengan titik lain yang terhubung dengan melakukan perhitungan nilainya. Proses atau langkah tersebut terus berlanjut hingga ditemukan nilai (jarak) terkecil atau minimum dari titik awal hingga ke titik tujuan.



Step 4 : Menentukan Nilai (Jarak) Tiap Titik

          Setelah selesai membuat tabel, maka didapatkan nilai (jarak) semua titik yang terhubung dan telah dilewati dari titik awal hingga ke titik tujuan.
1. V1 memiliki jalur terpendek menuju V2 tanpa perantara dengan nilai (jarak) 3
2. V1 memiliki jalur terpendek menuju V3 tanpa perantara dengan nilai (jarak) 4
3. V1 memiliki jalur terpendek menuju V4 tanpa perantara dengan nilai (jarak) 2
4. V1 memiliki jalur terpendek menuju V5 melalui V4 dengan nilai (jarak) 3
5. V1 memiliki jalur terpendek menuju V6 melalui V5 dengan nilai (jarak) 5

Step 5 : Kesimpulan

                Pada langkah terakhir ini, dapat disimpulkan bahwa nilai (jarak) terpendek dari titik awal (V1) menuju titik tujuan (V6) adalah 5, dengan lintasan melalui V1 V4 V5 V6. 

1 comment: