Penentuan lintasan terpendek dengan Algoritma Dijkstra

ABSTRAK

Terdapat banyak aplikasi yang berkaitan dengan graph. Didalam aplikasi tersebut graph digunakan sebagai alat untuk merepresikan atau memodelkan persoalan. Berdasarkan graph yang dibentuk, barulah persoalan tersebut dapat di selesaikan. Aplikasi yang berkaitan dengan lintasan di dalam graph yaitu menentukan lintasan terpendek. Misalnya kepadatan lalu lintas dari STAIN Malang ke Tugu Malang yang sering mengalami kemacetan dan memiliki banyak lintasan atau jalur. Dengan adanya banyak lintasan, untuk menuju suatu tujuan tertentu, maka kita dapat menentukan jarak terpendek atau lintasan terpendek.

Suatu lintasan terpendek sangat penting untuk menghubungkan beberapa persimpangan jalan disuatu daerah. Jika setiap dua persimpangan dapat dihubungkan oleh sebuah lintasan, maka untuk beberapa persimpangan jalan ada banyak lintasan yang bisa dihubungkan.

Jika menentukan lintasan terpendek itu pada jarak ١ - 0اعه) dengan 0رع adalah titik awal dan V adalah titik akhir, berarti bahwa kita mulai bergerak dari UQ menuju ke suatu tujuan tertentu V dengan dihubungkan oleh suatu kintasan, maka bagaimanakah cara menentukan lintasan terpendek dari STAIN Malang untuk menuju ke Tugu Malang yang mempunyai banyak jalur atau lintasan dengan jarak terdekat.

Persoalan tersebut dapat diselesaikan dengan menggunakan Algoritma Dijkstra pada teori graph. Dengan pebdekatan ini, sebuah persimpangan jalan diwakili oleh sebuah titik dan sebuah jalan diwakili oleh sebuah sisi. Muatan sisi graph menyatakan panjang lintasan atau jarak lintasan antara dua persimpangan jalan. Jika setiap lintasan terpendek tergantung pada jarak atau panjang lintasan, maka dapat ditemukan sebuah lintasan terpendek atau jarak terdekat.