Algoritma Dijkstra

Algoritma Dijkstra merupakan algoritma lintasan terpendek yang paling terkenal. Algoritma ini diterapkan untuk mencari lintasan terpendek (shortest path) pada graf berarah. Algoritma Dijkstra menyelesaikan permasalahan jalur terpendek dengan sumber tunggal (the single-source shortest-path problem) apabila semua simpul tidak negatif (≥ 0). Algoritma ini adalah algoritma Greedy yang mirip dengan algoritma Prim. Algoritma berawal dari simpul sumber S untuk membangun pohon T, dan semua simpul dapat dicapai dari S. Nilai simpul ditambahkan ke T (nilai jalur), kemudian ditambah nilai simpul berikutnya, dan begitu seterusnya.

Secara umum kriteria yang harus dipenuhi untuk mendapatkan  solusi optimum dari jalur terpendek (shortest path) hampir sama dengan kriteria permasalahan pada pohon merentang minimum. Perbedaan mendasar adalah pada jalur terpendek berupa graf berarah, sehingga kriteria yang harus dipenuhi adalah:

1.   Setiap sisi pada graf harus mempunyai nilai (bobot).

2.   Setiap sisi pada graf tidak harus terhubung.

3.   Setiap sisi pada graf harus mempunyai arah.

Proses untuk mendapatkan solusi optimum jalur terpendek adalah dengan menghitung jarak satu per satu sesuai dengan arah yang ditunjukkan oleh tiap-tiap sisi. Perhitungan dilakukan terhadap sisi graf yang memiliki jalur awal dan jalur akhir. Contoh pada gambar di bawah ini akan memberikan gambaran yang lebih mudah dipahami. Misalkan akan ditentukan jalur terpendek dari graf dibawah ini.

Langkah-langkah penyelesaiannya adalah sebagai berikut:

1.   Perhatikan terlebih dahulu proses simpul yang mempunyai awal dan mempunyai simpul akhir atau simpul tujuan. Dalam kasus ini simpul A sebagai simpul awal dan berdasarkan graf di atas maka gambaran jalur yang bisa ditempuh adalah: A – B, A – C, A – D, dan A – E.

2.   Mencari jalur terpendek tiap-tiap proses dari keempat jalur tersebut dengan menghitung panjang tiap-tiap jalurnya.

3.   Dengan demikian dapat diketahui jalur terpendek dari simpul awal ke simpul tujuan adalah: A – C = 10, A – C – D = 25, A – C – D – B = 45, dan A – E = 45.

DAFTAR PUSTAKA / REFERENSI

Gloor, P. A., Johnson, D. B., Makedon, F., Metaxas, P., (1993), A Visualization System for Correctness Proofs of Graph Algorithms, http://www.wellesley.edu/CS/pmetaxas/visual_proofs.pdf, Computer Science Education, [19 Maret 2010].

Greenberg, H. J., (1998), Greedy Algorithm for Minimum Spanning Tree, http://glossary.computing.society.informs.org/notes/spanningtree.pdf, University of Colorado, Denver, [19 Maret 2010].

Kristanto, A., (2008), Perancangan Sistem Informasi dan Aplikasinya, Gava Media, Yogyakarta.

Mehta, D. P., Sahni, S., (2005), Handbook of Data Structures and Applications, Chapman & Hall/CRC Computer and Information Science Series, United States of America.

Munir, R., (2009), Matematika Diskrit, Edisi 3, Informatika, Bandung.

Oetomo, B. S., (2002), Perencanaan dan Pembangunan Sistem Informasi, Andi, Yogyakarta.

Purbasari, I. Y., (2007), Desain Dan Analisis Algoritma, Edisi 1, Graha Ilmu, Yogyakarta.

Purwanto, E. B., (2008), Perancangan Dan Analisis Algoritma, Edisi 1, Graha Ilmu, Yogyakarta.

Zakaria, T. M., Prijono, A., (2006), Konsep Dan Implementasi Struktur Data, Informatika, Bandung.