Algoritma Dijkstra dan Contoh
Link video di atas, memberikan contoh bagaimana algoritma Dijkstra bekerja untuk menyelesaikan permasalahan pencarian jalur terpendek. Atau anda dapat mengikuti contoh cara menggunakan algoritmaDijkstra disini.
Seperti dijelaskan dalam video kuliah sebelumnya, bahwa algortima Dijkstra merupakan salah satu algoritma dalam graf untuk menyelesaikan masalah pencarian jalur terpendek diantara titik-titik dalam graf. Salah satu contoh masalah jarak terpendek dalam kehidupan sehari-hari adalah bagaimana menentukan jalur/rute terpendek, jika anda diberikan beberapa posisi (misalkan kota) untuk dikunjungi. Masih banyak lagi contoh permasalahan sehari-hari yang dapat dipandang sebagai masalah jalur terpendek, diantaranya :
- Jalur mengemudi yang direkomendasikan/dipetakan seperti pada websiteweb mapping. Misalnya,MapQuestatauGoogle Maps;
- Di bidang jaringan dan komunikasi, dikenal istilah the min-delay path problem. Contohnya bagaimana menemukan jalur min-delay terpendek.
- Permasahan jalur terpendek juga banyak diaplikasikan dalam permainan. Contohnya anda dapat melihat permainan di linkhttp://www.dumb.com/sixdegrees/movies/. Permainan ini disebut Six Degrees of Separation Movie, yaitu menemukan bagaimana 2 aktor/akris Holywood terhubung berdasarkan film yang dibintangi bersama.
- Dalam operations research, pencarian jalur tependek banyak diaplikasikan untuk masalah robotic, transportasi, dan desainVLSI.
- travelling salesman problem, yaitu masalah menentukan jalur terpendek untuk pergi ke semua titik yang diberikan tepat satu kali dan kembali ke tempat asal.