Penentuan Lintasan Terpendek dari FMIPA ke Rektorat dan fakultas lain di Universitas Sam Ratulangi Manado dengan Menggunakan Algoritma Djikstra

Oleh: Deiby T. Salaki

ABSTRAK

Universitas Sam Ratulangi Manado adalah salah satu perguruan tinggi di Sulawesi Utara yang terdiri atas 11 fakultas dan satu gedung rektorat. Setiap fakultas dan rektorat terhubung dengan fasilitas jalan raya. Secara matematis kondisi seperti ini dapat direpresentasikan sebagai sebuah graf yang bisa diterapkan untuk mencari lintasan terpendek. Pada penelitian ini akan dicari lintasan terpendek dari FMIPA ke rektorat dan fakultas lainnya. Dengan menggunakan algoritma Djikstra, lintasan terpendek dari FMIPA diperoleh dengan memilih minimum lokal atau akses dengan jarak terdekat dari setiap lokasi yang kemudian digabungkan menjadi sebuah kumpulan lintasan dari satu lokasi ke lokasi lainnya dengan jarak terpendek.

Kata Kunci: algoritma djikstra, graf, masalah lintasan terpendek

DETERMINATION OF SHORTEST PATH FROM FMIPA TO RECTORATE AND OTHER FACULTIES AT SAM RATULANGI UNIVERSITY USING DJIKSTRA ALGORITHM

ABSTRACT

Sam Ratulangi University is one of the colleges in North Sulawesi consisting of 11 faculties and one rectorate building. Every faculty and rectorate connected by highway facilities. Mathemathically this condition can be represented as an undirected weighted graph that can be applied to find the shortest path. By using the Djikstra algorithm, the shortest paths are obtained by setting the FMIPA as the initial vertex and then select the local minimum or access to the closest distance from each location, then combined the collection of path from one location to another with the shortest distance.

Keywords: djikstra algorithm, graph, shortest path problem

PENDAHULUAN

Universitas Sam Ratulangi (Unsrat) Manado merupakan salah satu perguruan tinggi di Sulawesi Utara dengan luas area sekitar 1.320.816 m2. Unsrat terdiri atas 11 fakultas dan satu gedung rektorat yang letaknya relatif terpisah satu dengan yang lain. Setiap fakultas dan rektorat terhubung dengan fasilitas jalan raya, yang juga merupakan sarana untuk mengakses antara satu fakultas dengan fakultas lainnya. Secara matematis kondisi seperti ini dapat direpresentasikan sebagai sebuah graf. Graf adalah pasangan himpunan vertex/simpul dan edges/sisi, dimana setiap sisi berhubungan dengan satu atau dua buah simpul. Dalam graf dapat merepresentasikan jalan dan simpul dapat merepresentasikan tempat atau lokasi.

Salah satu masalah umum yang dapat diselesaikan dengan menggunakan teori graf yaitu Masalah Lintasan Terpendek (Shortest Path Problem/SPP) yang mencari lintasan dengan jumlah bobot paling minimum. Algoritma Djikstra merupakan salah satu algoritma untuk menyelesaikan masalah ini.

Download