Algoritma Djikstra

Selain Algoritma Bellman-Ford, terdapat algoritma lainnya untuk menentukan jalur terpendek dalam suatu jaringan, yaitu menggunakan Algoritma Dijkstra.

Algoritma Dijkstra adalah suatu algoritma untuk menentukan jalur terpendek antar node dengan berdasar pada basis penghitungan "dari satu node menuju seluruh node". Algoritma Dijkstra termasuk dalam jenis algoritma Link State, yaitu memperhatikan total jarak dan rute yang akan dilalui.

Keywords: jaringan komputer node shortest path jalur terpendek algoritma dijkstra cara step langkah tabel gambar how to mudah singkat

Pada dasarnya, terdapat beberapa notasi utama dalam pengerjaan Algoritma Dijkstra ini:

Inisialisasi

Untuk proses inisialisasi, dibentuk suatu array/himpunan N dengan anggota s (s adalah lambang untuk suatu node sumber). Nilai D adalah jarak yang akan tersedia pada tabel hasil algoritma, sementara C adalah nilai jarak pada map yang tersedia. Maka pada tahap inisialisasi ini nilai Dj (jarak pada hasil tabel antara node s dengan node j, dengan j tidak sama dengan s) dimasukkan nilai yang sebenarnya. Jika tidak tersambung secara langsung maka akan dianggap tak terdefinisi. Untuk jarak Ds tentu saja bernilai 0.

Temukan simpul tetangga (node selain sumber)

Kalau notasi ini apa artinya yaa... -_- saya lupa. Pokoknya nanti untuk perulangan tiap baris dimasukkan node i yang belum termasuk pada array/himpunan N untuk nanti node i tersebut dijadikan sebagai "perpanjangan" dari node s, dengan node i juga merupakan node tetangga dari node s. Node i yang dimasukkan pada himpunan N berdasarkan pada jarak terkecil dengan node s. Dan jika seluruh node sudah masuk dalam himpunan N, maka iterasi akan berhenti.

Update untuk setiap j ϵ N

Untuk setiap node j (dalam tabel hasil: tiap kolom) diperbaharui nilainya yang paling kecil yaitu membandingkan antara nilai Dj sebelumnya dengan hasil penjumlahan (Di+Cij), yaitu penjumlahan jarak node s ke node i dengan jarak sebenarnya dari node i ke node j.

Mungkin kalau hanya baca teorinya saja pasti pusing ya. Mending langsung kita terapkan ke contoh soal saja ya biar lebih gampang ^^.

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 1.

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.