Contoh Program Algortima Dijkstra. Kali ini saya akan membahas algoritma untuk menentukan jalur terpendek dengan menggunakan Algoritma Djikstra. Sebelumnya saya juga telah membahas Menentukan Jalur Terpendek menggunakan Algoritma Greedy. Algoritma Djikstra berbeda dengan greedy, karna djikstra kita akan menemukan jalur yang benar-benar paling optimum. Dan saya telah membuat sebuah source code PHP untuk menyelesaikan algoritma djikstra secara otomatis.
Cek di sini Program Algoritma Dijkstra.
Cek di sini Program Algoritma Dijkstra.
Pertama mari kita bahas bagaimana cara kerja algoritma djikstra :
- Buat tabel yang terdiri dari Node, status, Bobot, Total_bobot dan Predecessor (node terpilih)
- Set semua node dengan status =0 dan set node sumber dengan status = 1
- Dari node yang status =1, tentukan semua node tetangga yang status = 0 yang terhubung langsung dengan node tersebut, cek bobot dan hitung total bobot dari node yang statusnya 1 ke node yang berstatus = 0 tersebut. Sebagai contoh, jika node A ke B memiliki bobot jarak 6 dan dari B ke node C berjarak 2, maka jarak ke C melewati B menjadi 6+2=8.
- Jika total bobot ini lebih kecil dari total bobot sebelumnya (yang telah terekam sebelumnya) hapus data lama, simpan ulang data total bobot dengan total yang baru dan tetapkan predecessornya.
