Algoritma djikstra merupakan sebuah algoritma yang diciptakan oleh Edsger W. Djikstra untuk menentukan jalur terbaik untuk menuju suatu tempat.
Algoritma ini tidak hanya digunakan pada konsep routing protocol saja, melainkan dapat juga kita gunakan untuk menentukan jalur terbaik untuk menuju suatu tempat dalam peta dunia.
Algoritma Djikstra
Untuk memahami bagaimana algoritma djikstra bekerja, perhatikan ilustrasi berikut.
Dari ilustrasi diatas kita bisa melihat bahwa ada empat titik dimana setiap titik terhubung dengan titik lainnya menggunakan sebuah garis.
Dalam setiap garis terdapat sebuah angka yang menunjukan cost dari garis tersebut.
Tujuan kita disini adalah mencari jalur terpendek yang dapat digunakan oleh titik A untuk menuju ke titik B, C, dan D menggunakan algoritma djikstra.
Karena algoritma djikstra bukanlah hal yang mudah untuk dipahami, kami akan menjelaskan menggunakan beberapa tahap.
Tahap 1
Pada tahap pertama ini, kita akan menghitung cost yang harus digunakan oleh titik A untuk menuju titik-titik yang terhubung langsung dengannya. Perhatikan ilustrasi berikut
Karena kita melakukan penghitungan dengan titik A sebagai acuan, maka cost pada titik A adalah 0. Selanjutnya titik A terhubung langsung dengan titik B dan C.
Cost pada titik B adalah 4A Huruf A menujukan bahwa cost ini diperoleh dari titi A. Selanjutnya cost pada titik C adalah 2. Sedangkan cost pada titik D adalah unknown (~). Hal ini dikarenakan titik A tidak terhubung langsung dengan titik D.
Pada tahap ini kita bisa melihat bahwa yang memiliki cost terkecil adalah titik C, yaitu dengan cost 2. Titik A tidak masuk hitungan karena titik A merupakan titik yang menjadi acuan pada perhitungan tahap ini.
Titik C memiliki cost terkecil, sehingga titik C akan menjadi acuan dalam tahap berikutnya.
Tahap 2
Seperti yang telah dijelaskan sebelumnya, bahwa pada tahap ini yang akan menjadi acuan pada titik C. Sehingga pada tahp ini kita akan menghitung cost untuk titik-titik yang terhubung langsung dengan titik C.
Perhatikan bahwa titik C terhubung langsung dengan titik B. Dari tabel diatas kita bisa melihat bahwa cost pada titik B adalah 3. Nilai ini diperoleh dari penjumlahan antara pada cost pada titik C (2) dengan cost pada garis antara titik C dengan B (1).
Selanjutnya karena cost ini (3) lebih kecil dari pada cost pada titik B sebelumnya (4), maka cost ini akan mengganti cost yang sebelumnya. Perhatikan bahwa saat ini cost pada titik B berubah menjadi 3C yang menunjukan bahwa titik B mempunyai cost yang didapat dari titik C.
Cost pada titik C akan memiliki nilai yang tetap, hal ini dikarenakan titik C merupakan acuan pada perhitungan tahap ini. Selanjutnya titik C juga terhubung langsung dengan titik D.
Cost pada titik C (2) dijumlahkan dengan cost pada garis antarat titik C dengan D (7). Sehingga cost pada titik D adalah 9c. Perhatikan huruf c yang menunjukan cost tersebut diperoleh dari titik C.
Dari perhitungan pada tahap ini, kita bisa melihat bahwa titik yang memiliki cost terkecil adalah titik B dengan cost 3. Adapun titik C tidak akan masuk hitungan karena titik C menjadi acuan pada perhitungan tahap ini. Selanjutnya titik B akan menjadi acuan pada tahap berikutnya.
Tahap 3
Pada tahap ini kita akan menghitung cost pada titik-titik yang terhubung langsung dengan titik B.
Perhatikan bahwa titik B terhubung langsung dengan titik D. Dari tabel diatas kita bisa melihat bahwa cost pada titik D adalah 5a. Angka ini didapat dari penjumlahan cost pada titik B (3) dengan cost pada garis antara titik B dengan titik D (2).
Karena cost baru ini lebih kecil dari cosy yang sebelumnya, maka cost pada titik D akan diganti dengan cost terbaru yang lebih kecil.
Hasil Algoritma Djikstra
Sampai tahap 3 diatas, kita sudah bisa mengetahui jalur terpendek yang dapat digunakan oleh titik A untuk menuju ketiga titik lainnya. Perhatikan ilustrasi berikut.
Dari ilustrasi diatas dapat kita lihat bahwa saat titik A ingin menuju titik B, maka jalur dengan nilai cost terendah yang bisa dilewati adalah jalur A-C-B dengan cost 3. Jika ingin menuju titik C, maka titik A bisa langsung menuju titik C melewati jalur A-C dengan cost 2.
Sedangkan jika titik A ingin menuju titik D, maka jalur dengan cost terkecil yang dapat dilewati adalah jalur A-C-D dengan cost 5.
