Pengertian dan Teori Algoritma Dijkstra

Pengertian dan Teori Algoritma Dijkstra

Algoritma Dijkstra, (dinamai menurut penemunya, seorang ilmuwan komputer, Edsger Dijkstra), adalah sebuah algoritma rakus (greedy algorithm) yang dipakai dalam memecahkan permasalahan jarak terpendek (shortest path problem) untuk sebuah graf berarah (directed graph) dengan bobot-bobot sisi (edge weights) yang bernilai tak-negatif.
Misalnya, bila vertices dari sebuah graf melambangkan kota-kota dan bobot sisi (edge weights) melambangkan jarak antara kota-kota tersebut, maka algoritma Dijkstra dapat digunakan untuk menemukan jarak terpendek antara dua kota.

Input algoritma ini adalah sebuah graf berarah yang berbobot (weighted directed graph) G dan sebuah sumber vertex s dalam G dan V adalah himpunan semua vertices dalam graph G.

Setiap sisi dari graf ini adalah pasangan vertices (u,v) yang melambangkan hubungan darivertex u ke vertex v. Himpunan semua tepi disebut E.
Bobot (weights) dari semua sisi dihitung dengan fungs

w: E → [0, ∞)

Jadi w(u,v) adalah jarak tak-negatif dari vertex u ke vertex v.
Ongkos (cost) dari sebuah sisi dapat dianggap sebagai jarak antara dua vertex, yaitu jumlah jarak semua sisi dalam jalur tersebut. Untuk sepasang vertex s dan t dalam V, algoritma ini menghitung jarak terpendek dari s ke t.

Tujan Algoritma Dijkstra

Ø  Tujuan Algoritma Dijkstra yaitu untuk menemukan jalur terpendek berdasarkan bobot terkecil dari satu titik ke titik lainnya.

Ø  Kelemahan algoritma ini adalah semakin banyak titik akan semakin memakan waktu proses.

Ø  Jumlah titik menentukan tingkat efektifitas dari algoritma djikstra.

Urutan Logika Algoritma Dijkstra

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

2.      Set semua node “Belum terjamah” dan set node awal sebagai “Node keberangkatan”.

3.      Dari node keberangkatan, pertimbangkan node tetangga yang belum terjamah dan hitung jaraknya dari titik keberangkatan.

4.      Setelah selesai mempertimbangkan setiap jarak terhadap node tetangga, tandai node yang telah terjamah sebagai “Node terjamah”. Node terjamah tidak akan pernah di cek kembali, jarak yang disimpan adalah jarak terakhir dan yang paling minimal bobotnya.

5.      Set “Node belum terjamah” dengan jarak terkecil (dari node keberangkatan) sebagai “Node Keberangkatan” selanjutnya dan lanjutkan dengan kembali ke step 3.

Contoh :

Titik mengambarkan lokasi dan garis menggambarkan jalan, maka algoritma Dijkstra melakukan kalkulasi terhadap semua kemungkinan bobot terkecil dari setiap titik.

Pertama tentukan titik yang akan menjadi nomor kode (node) awal, lalu beri bobot jarak pada node pertama ke node terdekat satu per satu, lalu akan dilakukan pengembangan pencarian dari satu titik ke titik selanjutnya (tahap demi tahap).

1.    Node awal 1, Node tujuan 5. Setiap edge yang terhubung antar node telah diberi nilai.

2.    Dijkstra melakukan kalkulasi terhadap node tetangga yang terhubung langsung dengan node keberangkatan (node 1), dan hasil yang didapat adalah node 2 karena bobot nilai node 2 paling kecil dibandingkan nilai pada node lain, nilai = 7 (0+7).

3.    Node 2 diset menjadi node keberangkatan dan ditandai sebagi node yang telah terdatangi. Dijkstra melakukan kalkulasi kembali terhadap node-node tetangga yang terhubung langsung dengan node yang telah terdatangi. Dan kalkulasi dijkstra menunjukan bahwa node 3 yang menjadi node keberangkatan selanjutnya karena bobotnya yang paling kecil dari hasil kalkulasi terakhir, nilai 9 (0+9).

4.    Perhitungan berlanjut dengan node 3 ditandai menjadi node yang telah terjamah. Dari semua node tetangga belum terjamah yang terhubung langsung dengan node terjamah, node selanjutnya yang ditandai menjadi node terjamah adalah node 6 karena nilai bobot yang terkecil, nilai 11 (9+2).

5.    Node 6 menjadi node terjamah, dijkstra melakukan kalkulasi kembali, dan menemukan bahwa node 5 (node tujuan ) telah tercapai lewat node 6. Jalur terpendeknya adalah 1-3-6-5, dan niilai bobot yang didapat adalah 20 (11+9). Bila node tujuan telah tercapai maka kalkulasi dijkstra dinyatakan selesai.

6.                 

Contoh soal : 

Mari kita pakai contoh jaringan yang sama dengan yang ada pada postingan Bellman-Ford yang lalu:

Misalnya kita akan menggunakan algoritma Dijkstra untuk mencari path terpendek dari node untuk mempermudah, buatlah tabel seperti berikut ini:

(Notasi dalam tabel algoritma Dijkstra memiliki format (s-j,D), dimana s-j menunjukkan rute dari node s menuju node j, sementara D menunjukkan jarak total antara kedua node tersebut)

Baris pertama masih berupa inisialisasi, yaitu Dj akan memiliki nilai jika tersambung langsung dan tidak memiliki nilai jika tidak tersambung langsung.

Karena node 1 kebetulan hanya memiliki 1 tetangga yaitu node 2, maka i = 2 dimasukkan pada himpunan N.

Node 2 sudah berperan sebagai "perpanjangan" node sumber (node 1), sehingga sekarang node-node yang terhubung dengan node 2 sudah bisa "dijangkau" oleh node 1 via node 2. Diketahui node 3 dan node 4 terhubung langsung dengan node 2, sehingga rutenya ditulis (1-2-3) dan (1-2-4).

Untuk langkah selanjutnya dipilih node i yang telah tersambung dengan node s namun belum masuk dalam himpunan N. Diketahui yaitu node 3 dan node 4. Node yang dipilih adalah yang memiliki jumlah jarak yang paling minimum, yaitu node 4. Sehingga didapat baris tabel berikutnya seperti berikut.

Seperti langkah yang sebelumnya, sekarang node 4 ikut berperan sebagai "perpanjangan" dari node 1 sehingga node 5 dan node 7 yang terhubung langsung dengan node 4 sudah bisa "dijangkau" oleh node 1 dengan rute yang tertampil.

Sebenarnya disini mulai terjadi perbandingan nilai jarak. Dengan dimasukkannya node 4 dalam himpunan N, maka node 4 berlaku sebagai "penembak sementara" (maafkan saya kalau istilahnya alay -_-). Maksudnya adalah node 4 dapat melakukan perhitungan minimum menuju node tertentu meskipun node tersebut telah diketahui rute dan jaraknya.

Dalam kasus ini dapat diambil node 3. Node 3 sudah diketahui rute dan jaraknya pada baris ke-2. Dengan masuknya node 4 pada himpunan N, maka node 4 akan menghitung jarak minimum antara entry D3 yang terdahulu dengan yang baru. (Perbandingan via node 2 dengan via node 4):

Via node 2 --> D2 + C23 = 2 + 3 = 5

Via node 4 --> D4 + C43 = 3 + 7 = 10

Maka entry yang dipertahankan adalah via node 2 dengan jarak 5.

Sebelumnya telah dipilih node 4 sebagai anggota N karena bertetangga dengan node 2. Sekarang dipilih tetangga node 2 yang lainya yaitu node 3.

Perbandingan yang terjadi:

Pada D4

Via node 2 --> D2 + C24 = 2 + 1 = 3

Via node 3 --> D3 + C34 = 5 + 7 = 12

Maka entry yang dipertahankan adalah via node 2 dengan jarak 3.

Pada D5

Via node 4 --> D4 + C45 = 3 + 4 = 7

Via node 3 --> D3 + C35 = 5 + 3 = 8

Maka entry yang dipertahankan adalah via node 4 dengan jarak 7.

Singkat cerita, tabel hasil akhirnya adalah sebagai berikut.

RELATED POSTS: