Perbandingan Hasil Perhitungan Jarak Terpendek antara Alogritma Dijkstra dengan Pemograman Linier

Abstract

Abstrak

Perhitungan jarak terpendek suatu jaringan, misalnya jaringan jalan raya yang menghubungkan satu tempat ke tempat lain, dapat dilakukan dengan berbagai cara. Salah satu cara yang terkenal adalah dengan algoritma. Algoritma yang banyak digunakan adalah Algoritma Dijkstra. Namun, apakah Algoritma Dijkstra memang sudah benar-benar dapat diandalkan untuk menghitung jarak terpendek dari satu tempat ke tempat lain dari suatu jaringan jalan yang memiliki banyak jalur jalan. Untuk mengetahui hal tersebut, hasil perhitungan jarak terpendek dari Algoritma Dijkstra akan dibandingkan dengan cara perhitungan lain, yakni dengan pemrograman linier. Hasil yang diperoleh adalah pemrograman linier mampu menghitung jarak terpendek yang lebih pendek dibandingkan dengan jarak terpendek yang dihitung dengan algoritma Dijkstra.

Kata Kunci: jaringan, Algoritma Dijkstra, pemrograman linier, jarak terpendek

Abstract

Calculating the shortest distance of a network, such as the road network, which connects one place to another, can be performed in various ways. One well-known way is to use algorithm and the most applied one is Dijkstra's algorithm. The problem is whether or not Dijkstra's algorithm is completely reliable to calculate the shortest distance from one place to another on a road network that has a lot of trails. For this purpose, the calculation of the shortest distance applying algorithm Dijkstra will be compared to another calculation method, i.e., linear programming. The finding showed that applying linear programming resulted in the shortest distance than applying the Dijkstra's algorithm.

Keywords: Network, Dijkstra Algorithm, Linear Programming, Shortest Route