Algoritma Dijkstra

Assalamu’alaikum

Salam Sejahtera bagi kita semua,

Hai Sobat Mahir, kali ini mari KitaMahir akan membahas “Algoritma Dijkstra”,

Teruslah menuntut membaca dan manfaatkan ilmu sebaik mungkin.

Mungkin diantara kalian sudah ada yang sudah pernah mendengar atau bahkan sudah ada yang memahami algoritma dijkstra, untuk lebih jelasnya, mari kita bahas.

Algoritma Dijkstra atau algoritme rakus (greedy algorithm) merupakan algoritma pemecahan masalah dengan menggunakan jarak terpendek (shortest path problem) pada sebuah graf berarah dengan bobot - bobot garis bernilai nonnegative [0,∞), Input algoritme ini adalah sebuah graf berarah yang berbobot (G) dan sebuah titik asal (s) dalam himpunan garis (V). Misalnya, bila titik dari sebuah graf melambangkan kota-kota dan bobot garis melambangkan jarak antara kota-kota tersebut, algoritme Dijkstra dapat digunakan untuk menemukan jarak terpendek antara dua kota. Biaya (cost) dari sebuah garis dapat dianggap sebagai jarak antara dua simpul, yaitu jumlah jarak semua garis dalam jalur tersebut. Untuk sepasang titik s dan titik t dalam V, algoritme ini menghitung jarak terpendek dari titik s ke titik t.

Algoritma yang ditemukan oleh ilmuan computer bernama Edsger Dijkstra ini dipublikasikan pada tahun 1959  jurnal Numerische Mathematik yang berjudul “A Note on Two Problems in Connexion with Graphs” dan dianggap sebagai algoritma greedy.

Permasalahan rute terpendek dari sebuah titik ke akhir titik lain adalah sebuah masalah klasik optimasi yang banyak digunakan untuk menguji sebuah algoritma yang diusulkan. Permasalahan rute terpendek dianggap cukup baik untuk mewakili masalah optimisasi, karena permasalahannya mudah dimengerti (hanya menjumlahkan seluruh edge yang dilalui) namun memiliki banyak pilihan solusi.

Menurut Andrew Goldberg peneliti Microsoft Research Silicon Valley, mengatakan ada banyak alasan mengapa peneliti terus mempelajari masalah pencarian jalan terpendek. “Jalan terpendek adalah masalah optimasi yang relevan untuk berbagai macam aplikasi, seperti jaringan routing, game, desain sirkuit, dan pemetaan”.

Diskripsi matematis untuk grafik dapat diwakili G = {V. E}, yang berarti sebuah grafik (G) didefenisikan oleh satu set simpul (Vertex = V) dan koleksi Edge (E).

Algoritma Dijkstra bekerja dengan membuat jalur ke satu simpul optimal pada setiap langkah. Jadi pada langkah ke n, setidaknya ada n node yang sudah kita tahu jalur terpendek. Langkah-langkah algoritma Dijkstra dapat dilakukan dengan  langkah-langkah berikut:

1.      Tentukan titik mana yang akan menjadi node awal, lalu beri bobot jarak pada node pertama ke node terdekat satu per satu, Dijkstra akan melakukan pengembangan pencarian dari satu titik ke titik lain dan ke titik selanjutnya tahap demi tahap;

2.      Beri nilai bobot (jarak) untuk setiap titik ke titik lainnya, lalu set nilai 0 pada node awal dan nilai tak hingga terhadap node lain (belum terisi) 2;

3.      Set semua node yang belum dilalui  dan set node awal sebagai “Node keberangkatan”;

4.      Dari node keberangkatan, pertimbangkan node tetangga yang belum dilalui dan hitung jaraknya dari titik keberangkatan. Jika jarak ini lebih kecil dari jarak sebelumnya (yang telah terekam sebelumnya) hapus data lama, simpan ulang data jarak dengan jarak yang baru;

5.      Saat kita selesai mempertimbangkan setiap jarak terhadap node tetangga, tandai node yang telah dilalui sebagai “Node dilewati”. Node yang dilewati tidak akan pernah di cek kembali, jarak yang disimpan adalah jarak terakhir dan yang paling minimal bobotnya;

6.      Set “Node belum dilewati” dengan jarak terkecil (dari node keberangkatan) sebagai “Node Keberangkatan” selanjutnya dan ulangi langkah e .

Sebagai contoh hitunglah Jarak terdekat dari V1 ke V7 pada gambar berikut ini :

Hasil setiap stepnya dapat dilihat pada tabel berikut ini :

Dengan demikian jarak terpendek dari V1 ke V7 adalah 16 dengan jalur V1->V2->V3->V5->V6->V7.

Mungkin sekian dari KitaMahir, Semoga penjelasan tentang Algoritma Dijkstra kali ini dapat bermanfaat bagi kita Semua, Syukran.

Wassaalamu'alaikum

Daftar Pustaka

https://mti.binus.ac.id/2017/11/28/algoritma-dijkstra/

https://id.wikipedia.org/wiki/Algoritme_Dijkstra

https://id.wikipedia.org/wiki/Masalah_jarak_terpendek

.