Analisa Kombinasi Algoritma Djikstra dan Depth First Search untuk Shortest Path dan Availability Path Planning

Abstract

Path Planning in Graph Technology still a hot discussion topic. The designed Algorithm expected can find path Availability path and shortest path in a Graph. Dijkstra Algorithm has been applied to find shortest path, and Depth First Search Algorithm applied to find available path to destination node, which has been set. The first process is finding the overall path to the destination node. The second process is finding the shortest path, this process can be executed because every edge has a value between nodes. The result from the finding shortest be the path to reach the destination node. The third process will be executed when the first shortest path having obstacles to reach the destination node. This proses is pre – path planning generates the less number of route and travel load to reach the destination point. The result of Time Complexity in this research is O((e + v) log V).

Perencanaan rute pada pada teknologi Graf masih menjadi sebuah topik yang sedang hangat diperbincangkan. Algoritma yang dirancang diharapkan dapat menyelesaikan masalah pencarian rute – rute yang tersedia dan pencarian rute terpendek didalam Graf. Penelitian ini menerapkan Algoritma Dijkstra untuk mendapatkan rute terpedek dan Algoritma Depth First Search untuk mendapatkan semua jalur yang tersedia menuju titik destinasi yang telah ditetapkan. Proses pertama yang dilakukan mencari semua jalur yang ada didalam Graf, setelah itu maka didapatkan semua jalur yang ada menuju titik tuju. Proses kedua dilakukan pencarian rute terpendek, proses dapat dilakukan karena semua jalur didalam Graf memliki nilai antar simpul. Hasil dari pencarian rute terpendek menjadi rute yang akan dipakai untuk mencapai titik tuju. Proses ketiga dilakukan Ketika rute tercepat pertama mengalami gangguan atau hambatan. Proses ini adalah pra perencanaan jalur dan dapat meminimalisir jumlah rute yang tersedia dan beban tempuh menuju titik tuju. Hasil Pada penghitungan kompleksitas waktu dalam penelitian ini bernilai O((e + v) log V).