## PENENTUAN LINTASAN TERPENDEK DARI FMIPA KE REKTORAT DAN FAKULTAS LAIN DI UNSRAT MANADO MENGGUNAKAN ALGORITMA DJIKSTRA
Deiby T. Salaki 1)
1) Program Studi Matematika FMIPA Universitas Sam Ratulangi, Manado 95115

## 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  m 2 .  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.
Penelitian ini ditujukan untuk membuat  lintasan  terpendek  yang  dapat dilalui kendaraan roda empat dari FMIPA ke fakultas lainnya di Unsrat dengan menggunakan Algoritma Djikstra.

## TINJAUAN PUSTAKA
Teori Graf
Suatu  Graf G= ( V,E )  didefinisikan sebagai  pasangan  himpunan  sisi  dan  simpul dengan V(G) = Himpunan simpul { v 1 , v 2 , ... , v n } dan E(G) = Himpunan sisi { e 1 , e 2 , ... , e n }. Setiap  sisi  berhubungan  dengan  satu atau dua simpul.  Dua buah simpul dikatakan berhubungan atau bertetangga ( adjacent ) jika ada  sisi  yang  menghubungkan  keduanya. Berdasarkan  orientasi  yang  ada  pada  sisinya, graf dapat dikelompokkan menjadi dua yaitu: Graf    berarah  ( direct  graf )  yaitu  graf  yang setiap  sisinya  diberikan  arah  sehingga  untuk dua  simpul v i dan v j ,  maka  ( v i, v j v j ,v i ) dan graf tak berarah ( undirect graf ) yaitu graf yang sisinya tidak mengandung arah sehingga untuk  dua  simpul v i dan v j ,  maka  ( v i ,v j ) ( v j ,v i ).    Selain itu juga  dikenal  graf  berbobot yaitu  graf  yang  sisinya  memiliki  bobot  atau (Ahuja et al , 1993)..
Matriks Ketetanggaan ( adjacency matrix)
Misalkan  sebuah  graf G  = ( V,E ) dengan jumlah simpul n . Matriks ketetanggaan G adalah  matriks  bujursangkar dengan  ukuran n × n .  atau M= [ m ij ],  dengan m ij = 1  jika  simpul i dan j bertetangga, sebaliknya m ij = 0  jika  simpul i dan j tidak bertetangga (Munir, 2005).

## Masalah Lintasan Terpendek (SPP)
SPP  adalah  suatu  persoalan  untuk mencari lintasan antara dua atau lebih simpul pada graf berbobot yang gabungan bobot sisi graf yang dilalui berjumlah paling minimum. Persoalan ini juga merupakan suatu persoalan optimasi  yang  menggunakan  graf  berbobot, dimana  bobot  dapat  menyatakan  jarak  antar kota,  waktu  pengiriman  pesan,  ongkos pembangunan,  dan  sebagainya  (Pradana, 2009).

## Algoritma Djikstra
Algoritma  Djikstra  merupakan  salah satu metode untuk mencari lintasan terpendek dari  sebuah  simpul  ke  semua  simpul  lainnya dalam  graf  yang  hanya  memiliki  bobot positif.    Secara  formal,  masalah  lintasan terpendek  semua  pasangan  simpul  adalah untuk  mencari  lintasan  terpendek  di  antara semua  pasang  simpul v i ,  v i  V sedemikian sehingga i  j (Sarwoko, 2003)
Dalam  mencari  lintasan  terpendek  dari  suatu simpul  ke  semua  pasangan  simpul  algoritma Djikstra  melalui  sejumlah  langkah  yang menggunakan  prinsip greedy. Prinsip greedy pada  algoritma  Djikstra  menyatakan  bahwa pada  setiap  langkah  kita  memilih  sisi  yang berbobot  minimum  dan  memasukkannya dalam himpunan solusi (Munir, 2005).
Selain  matriks  ketetanggaan M , algoritma  ini  menggunakan  tabel S =  [ s i ], dengan s i = 1,    jika  simpul i termasuk  ke dalam  lintasan terpendek  dan  sebaliknya s i = 0,    jika  simpul i tidak  termasuk  ke  dalam lintasan  terpendek  dan  juga  tabel D  = [ d i ], dengan d i = panjang lintasan dari simpul awal a ke simpul i
Langkah-langkah  penentuan  lintasan terpendek  dari  graf G dengan n -buah  simpul dengan simpul awal a menggunakan algoritma Djikstra adalah sebagai berikut: 1. Langkah  0  (inisialisasi): s i = 0    dan d i = m ai untuk i = 1, 2,…, n 2. Langkah  1:  isi s a dengan  1  dan  isi d a dengan 3. Langkah 2: untuk setiap s i = 0 dengan i = 1,  2 ,  …  ,  n ,  pilih d j =  min{ d 1 , d 2 ,  ..., d n } lalu isi s j dengan  1  dan  perbarui d i , dengan: d i (baru) = min{ d i (lama), d j + m ji }.  Pada  lintasan,  tambahkan  simpul j sebagai  simpul  terpilih  untuk  lintasan selanjutnya.
4. Langkah 3: mengulangi langkah 2 sampai s j = 1, untuk j = 1, 2 , … , n 5. Membuat  himpunan  simpul  berdasarkan urutan  yang  diperoleh  yang  merupakan lintasan  terpendek  dengan  bobot d i (Munir, 2009)

## METODOLOGI PENELITIAN
Data yang digunakan dalam penelitian ini yaitu berupa jarak antar fakultas dan  rektorat  yang  diperoleh  berdasarkan pengukuran  pada  peta  kampus  Universitas Sam  Ratulangi Manado (Google  Map).    Peta
200 610 420 250 450 520 740 440 200 150 350 620 450 110 250 150 100 310 2 1 3 4 10 11 9 12 7 8 5 6
kemudian  direpresentasikan  dalam  sebuah graf lalu dibuat matriks ketetanggaannya dan selanjutnya  menentukan  lintasan  terpendek dari  FMIPA  ke  fakultas  lain  dan  gedung
rektorat  dengan  menggunakan  algoritma Djikstra.    Perhitungan  dilakukan  dengan bantuan software Pascal.
Gambar 1. Graf Universitas Sam Ratulangi Manado

## HASIL DAN PEMBAHASAN
Berdasarkan peta Unsrat dapat dibuat graf  seperti  pada  gambar  1.    Gambar  1 merupakan  graf  berbobot  tak  berarah  yang terdiri  atas  12  simpul  dimana  simpul  1 mewakili kantor rektorat dan simpul 2 sampai 12 berturut-turut mewakili Fakultas
Kedokteran,  Fakultas  Perikanan,  Fakultas
Teknik,  FISIP,  Fakultas  Ekonomi,  Fakultas Hukum,  Fakultas  Sastra,  Fakultas  Pertanian, Fakultas  Peternakan,  FMIPA  dan  Fakultas Kesehatan Masyarakat. Setiap sisi menyatakan  jalan  roda  empat  penghubung antar  fakultas  dan  rektorat.  Angka-angka yang  terdapat  pada  setiap  sisi  merupakan bobot  graf  yang  mewakili  panjang  jalan dengan  satuan  meter.    Jarak-jarak  ini  dapat dilihat pada Tabel 1.
Penentuan  lintasan  terpendek  dari simpul  awal  FMIPA  ke  gedung  rektorat  dan setiap  fakultas  lain  di  Unsrat  delakukan dengan  bantuan  pemrograman  Pascal.    Data yang  dimasukkan  adalah  entri  dari  matriks ketetanggaan.  Untuk  elemen  matriks  yang bernilai dimasukkan dengan nilai “99999”. Hasil Perhitungan dapat dilihat pada Tabel 2.
Tabel 2. Lintasan Terpendek dari Simpul
Awal Fakultas MIPA Simpul tujuan  Lintasan Jarak (meter) 1 11,2,1 670 2 11,2 420 3 11,2,1,3 870 4 11,2,1,3,4 1020 5 11,12,8,5 1150 6 11,12,8,5,6 1250 7 11,12,8,7 1010 8 11,12,8 900 9 11,9 310 10 11,2,1,10 870 12 11,12 450
Tabel 1. Matriks Ketetanggaan Untuk Graf Universitas Sam Ratulangi Manado
1 2 3 4 5 6 7 8 9 10 11 12 1 0 250 200 200 2 250 0 520 420 440 3 200 0 150 4 150 0 350 5 0 100 150 250 6 100 0 7 350 150 0 110 620 8 250 110 0 450 9 520 0 610 310 740 10 200 610 0 11 420 310 0 450 12 440 620 450 740 450 0
Berdasarkan  tabel  2  dapat  dilihat  bahwa simpul  yang  dapat  diakses  langsung  adalah simpul  2,  9  dan  simpul  12  dengan  jarak masing-masing  420,  310  dan  450  meter. Melalui  perantara  simpul  2  dapat  diakses simpul  1  dengan  jarak  670  meter  yang menjadi perantara untuk mengakses simpul 3 dan  10  dengan  jarak  870  meter,  sedangkan melalui  simpul  12  dapat  diakses  simpul  8 dengan jarak 900
meter yang menghubungkan  lintasan  ke  simpul  5  dan  7 dengan  jarak  masing-masing  1150  dan  1010 meter,  kemudian  melalui  simpul  5  lintasan terhubung  dengan  simpul  6  dengan  jarak 1250 meter.

## KESIMPULAN DAN SARAN
Berdasarkan hasil penelitian diperoleh bahwa lintasan  terpendek  dari  FMIPA  ke  rektorat adalah  melaui  F.  Kedokteran  dengan  jarak 670 meter yang selanjutnya dapat dilanjutkan ke  F.  Perikanan  dan  F.  Peternakan  dengan jarak  masing-masing  870  m.    Melalui  FKM dapat  diakses  Fakultas  Sastra  dengan  jarak 900 m.  Fakultas Teknik dapat diakses melaui F. Perikanan dengan jarak 1020 m sedangkan F.  Ekonomi  dan  ISIP  diakses  melalui  F. Sastra  dengan  jarak  masing-masing  1250  m
dan  1150  m.    Fakultas  Hukum  diakses melalui F. Sastra dengan jarak 1010 m.

## DAFTAR PUSTAKA
Ahuja, R.K., T.L.  Magnanti ,  J.B. Orlin. 1993. Network Flow: Theory, Algorithms and Applications. Prentice Hall, New Jersey.
Google Map. 2010. Peta Universitas Sam
Ratulangi Manado. Munir,  R.    2008.  Matematika  Diskrit. Penerbit Informatika. Bandung Pradhana, B.A. 2009. Studi Dan Implementasi Persoalan Lintasan Terpendek Suatu Graf Dengan Algoritma  Dijkstra  Dan  Algoritma Bellman-Ford.
http://www.informatika.org/~rinaldi/Matdis/2 006-2007/Makalah/Makalah0607-
26.pdf  [1 Februari 2011 ].
Sarwoko, E. A. 2003. Perancangan Arsitektur Pemaralelan  untuk  mencari  Shortest Path dengan Algoritma Djikstra. Jurnal  Matematika  dan  Komputer . 6: 137-143.