MAKALAH MATEMATIKA DISKRIT

PENENTUAN LINTASAN TERPENDEK DARI BAGIAN AKADEMIK DAN BAGIAN LAIN KE RUANG DOSEN UTAMA DI STMIK BUMIGORA MATARAM MENGGUNAKAN ALGORITMA DJIKSTRA

ABSTRAK

STMIK Bumigora Mataram adalah salah satu perguruan tinggi swasta di Kota Mataram yang terdiri atas 3 gedung utama. Setiap setiap gedung terhubung dengan fasilitas jalan atau gang menuju gedung  atau ruang dosen utama. 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 ruangan bagian akademik ke ruang dosen utama dan lainnya. Dengan menggunakan algoritma Djikstra, lintasan terpendek dari ruang akademik 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

BAB I

PENDAHULUAN

1.1. Latar belakang

 STMIK Bumigora Mataram merupakan salah satu perguruan tinggi di kota mataram dengan luas area sekitar 1.320 m2. STMIK Bumigora terdiri atas 3 gedung utama dan satu gedung mushalla yang letaknya relatif terpisah satu dengan yang lain. Setiap bagian dan ruang dosen utama terhubung dengan fasilitas lorong dan tangga, yang juga merupakan sarana untuk mengakses antara satu gedung dengan gedung 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 mahasiswa dan dosen dari bagian akademik ke ruand dosen utama dan lainnya di STMIK Bumigora dengan menggunakan Algoritma Djikstra.

1.2.            Tujuan

Tujuan dari pembuatan makalah matematika diskrit ini adalah sebagai berikut:

a.       Mahasiswa memahami dan mengerti konsep graph dan algoritma djikstra.

b.      Untuk mempermudah akses mahasiswa dikampus dari gedung satu ke gedung lainnya di stmik bumigora mataram.

c.       untuk memenuhi tugas mata kuliah matematika diskrit yang diberikan oleh Bapak Dosen.

1.3.            Manfaat

Manfaat yang dapat diambil dari penulisan  makalah ini adalah mahasiswa biasa mengerti dan memahami konsep graph dan pengimplementasiannya dalam menyelesaikan masalah dalam kehidupan sehari- hari.

Manfaat yang lain juga membiasakan mahasiswa untuk menulis terutama makalah dan karya- karya ilmiah lainnya.

BAB II

PEMBAHASAN

     2.1. Teori Graf

Suatu Graf G=(V,E) didefinisikan sebagai pasangan himpunan sisi dan simpul dengan V(G) = Himpunan simpul {v1, v2, ... , vn} dan E(G) = Himpunan sisi {e1, e2, ... , en}.

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 vi dan vj, maka (vi,vj vj,vi) dan graf tak berarah (undirect graf) yaitu graf yang sisinya tidak mengandung arah sehingga untuk dua simpul vi dan vj, maka (vi,vj) (vj,vi). Selain itu juga dikenal graf berbobot yaitu graf yang sisinya memiliki bobot atau (Ahuja et al, 1993)..

2.2.            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= [mij], dengan mij = 1 jika simpul i dan j bertetangga, sebaliknya mij = 0 jika simpul i dan j tidak bertetangga (Munir, 2005).

2.3.            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).

2.4.            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 vi , vi  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 = [si], dengan si = 1, jika simpul i termasuk ke dalam lintasan terpendek dan sebaliknya si = 0, jika simpul i tidak termasuk ke dalam lintasan terpendek dan juga tabel D = [di], dengan di = 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): si = 0 dan di = mai untuk i = 1, 2,…, n

2.      Langkah 1: isi sa dengan 1 dan isi da dengan

3.      Langkah 2: untuk setiap si = 0 dengan i = 1, 2, … , n, pilih dj = min{d1, d2, ..., dn} lalu isi        sj dengan 1 dan perbarui di, dengan: di (baru) = min{di (lama), dj + mji }. Pada lintasan, tambahkan simpul j sebagai simpul terpilih untuk lintasan selanjutnya.

4.      Langkah 3: mengulangi langkah 2 sampai sj = 1, untuk j = 1, 2, … , n

5.      Membuat himpunan simpul berdasarkan urutan yang diperoleh yang merupakan lintasan terpendek dengan bobot di (Munir, 2009)

2.2.            PEMBAHASAN KASUS

Berdasarkan peta STMIK dapat dibuat graf seperti pada gambar 1.

 Gambar 1 merupakan graf berbobot tak berarah yang terdiri atas 10 simpul dimana simpul 1 mewakili ruang dosen utama dan simpul 2 sampai 10 berturut-turut mewakili ruang akademik, ruang jurusan, ruang perpustakaan, laboraturium jaringan, laboraturium computer 1, klinik, laboraturium 2 dan multimedia,PMB, pos jaga satpam.. Setiap sisi menyatakan jalan beruba gang penghubung antar gedung ( bagian ) dan ruang dosen utama. 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 akademik ke gedung dosen utama dan setiap bagian lain di STMIK dilakukan 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

Simpul Tujuan	Lintasan	Jarak ( Meter )
1	10, 9, 2, 1	65
2	10, 9, 2	15
3	10, 9, 2, 4, 3	66
4	10, 9, 2, 7, 5	60
5	10, 9, 2, 7, 5	25
6	10, 9, 2, 6	25
7	10, 9, 2, 7	25
8	10, 9, 8	10
9	10, 9	5
10	10, 9	5

Berdasarkan tabel 2 dapat dilihat bahwa simpul yang dapat diakses langsung adalah simpul 10, 9, 2, 1 dan simpul 3 dengan jarak masing-masing 5, 10, 50 dan 6  meter. Melalui perantara simpul 2 dapat diakses simpul 1 dengan jarak 65 meter yang menjadi perantara untuk mengakses simpul 3  dengan jarak 71 meter, sedangkan melalui simpul 4 dapat diakses simpul 1 dengan jarak 15 meter yang menghubungkan lintasan ke simpul 5 dan 8 dengan jarak masing-masing 5 dan 10 meter, kemudian melalui simpul 5 lintasan terhubung dengan simpul 6 dengan jarak 15 meter.

BAB II

PENUTUP

3.1. Kesimpulan Dan Saran

Berdasarkan hasil penelitian diperoleh bahwa lintasan terpendek dari bagian akademik ke ruandg dosen utama  adalah melaui lorong ruang dosen dengan jarak 50 meter yang selanjutnya dapat dilanjutkan ke ruang jurusan dan perpustakaan dengan jarak masing-masing 6 dan 10 m. Melalui ruang jurusan dapat diakses ruang dosen utama dengan jarak 6 m. perpustakaan dapat diakses melaui ruang jurusan dan dosen utama dengan jarak masing- masing 10 dan 6 m sedangkan lab. jaringan dapat diakses melalui ruang jurusan dan perpustakaan  dengan masing- masing jarak 4 dan 6 m. ruang akademik dapat diakses melalui ruang PMB dengan jarak 10 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/2006-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.

Buat temen- temen kelas 3A yg belum copy materi komdat presentasi kelompok 9 silahkan download disini..