PENERAPAN IMPROVED ALGORITMA DIJKSTRA UNTUK MENYELESAIKAN PERMASALAHAN LINTASAN TERPENDEK

• Main Author: LATIFATUL MAMNUNAH, 081211231002
• Format: Theses and Dissertations NonPeerReviewed
• Language: Indonesian; Indonesian
• Published: 2017
• Subjects: QA Mathematics
• Online Access: http://repository.unair.ac.id/62224/1/MPM.17-17%20Mam%20p%20Abstrak.pdf; http://repository.unair.ac.id/62224/2/MPM.17-17%20Mam%20p%20Sec.pdf; http://repository.unair.ac.id/62224/; http://lib.unair.ac.id
• Institution: Universitas Airlangga

Lintasan terpendek adalah suatu permasalahan dalam menentukan jarak yang minimal dari sejumlah rute perjalanan dari kota sumber menuju kota tujuan. Oleh karena itu, tujuan dari penulisan skripsi ini adalah menyelesaikan permasalahan lintasan terpendek dengan Improved Algoritma Dijkstra. Improved Algoritma Dijkstra merupakan modifikasi dari Algoritma Dijkstra untuk memperbaiki solusi. Algoritma Dijkstra diterapkan untuk mencari jarak terpendek dalam sejumlah langkah. Algoritma ini menggunakan prinsip greedy. Prinsip greedy pada Algoritma Dijkstra menyatakan bahwa memilih sisi yang berbobot minimum pada setiap langkah dan memasukkannya dalam himpunan solusi. Improved Algoritma Dijkstra mencakup tiga langkah dasar, yaitu langkah inisialisasi, menemukan titik himpunan solusi (p-label) selanjutnya, memperbarui himpunan bukan solusi. Data yang digunakan adalah data 8 kota di Cina dan data 31 kota di Cina diselesaikan dengan bahasa pemrograman C++ Borland 5.02. Fungsi tujuan (jarak) minimum terbaik berdasarkan dari Improved Algoritma Dijkstra didapatkan untuk data 8 kota di Cina sebesar 867, sedangkan untuk data 31 kota di Cina diperoleh jarak minimum sebesar 2026.