PENENTUAN LINTASAN TERPENDEK UNTUK TEMPAT WISATA DI PALEMBANGLiza Fatimah06111408017liza_fatimah@yahoo.com

AbstrakPalembang merupakan salah satu kota besar yang ada di Indonesia. Terdapat banyak tempat wisata di kota Palembang, baik wisata tempat maupun wisata kuliner khas Palembang. Dari tempat satu ke tempat yang lain, dihubungkan dengan fasilitas jalan raya. Jadi secara matematis, kondisi ini dapat direpresentasikan sebagai sebuah graf yang bisa diterapkan untuk mencari lintasan terpendek. Pada makalah ini akan dicari lintasan terpendek jika ingin berwisata dari tempat satu ke tempat yang lain di kota Palembang menggunakan algoritma Djikstra.

Kata kunci : Graf, Algoritma Djikstra, lintasan terpendek

BAB IPENDAHULUANPalembang adalah ibu kota provinsi Sumatera Selatan. Palembang merupakan kota terbesar kedua di Sumatera setelah Medan. Kota Palembang memiliki luas wilayah 358,55 km yang dihuni 1,7 juta orang dengan kepadatan penduduk 4.800 per km. Kota Palembang memiliki banyak tempat wisata baik wisata tempat maupun wisata kuliner. Apabila ingin mengunjungi semua tempat wisata di Palembang tanpa mengetahui rute terpendek dari semua tempat wisata tersebut maka akan memakan waktu yang lebih lama. Dari satu tempat ke tempat lain dihubungkan dengan fasilitas jalan raya. Maka dapat digunakan graf untuk mengetahui lintasan terpendek jika ingin mengunjungi semua tempat wisata di Palembang. Algoritma Djikstra merupakan salah satu algoritma untuk menyelesaikan masalah ini.

BAB IIMATERI PENUNJANG

2.1. Teori GrafGraf G didefinisikan sebagai pasangan himpunan (V, E) ditulis dengan notasi G = (V, E), dalam hal ini V adalah himpunan tak kosong dari simpul-simpul dan E adalah himpunan sisi yang menghubungkan sepasang simpul.Graf G(V, E) terdiri atas himpunan simpul yang dinyatakan dengan V = {v1,v2, v3, ..., vn} dan himpunan busur yang dinyatakan dengan E = {e1, e2, e3, ..., en} dengan ei = (vi, vj) merupakan busur yang menghubungkan simpul vi dan simpul vj.Setiap sisi berhubungan dengan satu atau dua simpul. Dua buah simpul dikatakan berhubungan atau bertetangga (adjacent) jika ada sisi yang menghubungkan keduanya. Sisi pada graf dapat mempunyai orientasi arah. Berdasarkan orientasi arah pada sisi, maka secara umum graf dapat dibedakan menjadi 2 jenis, yaitu:1. Graf tak-berarahGraf yang sisinya tidak mempunyai orientasi arah disebut graf tak berarah. Pada graf tak-berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan. Jadi, (u,v) = (v,u) adalah sisi yang sama. Tiga buah graf pada gambar di bawah ini adalah graf tidak berarah.

2. Graf berarahGraf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah. Kita lebih suka menyebut sisi berarah dengan sebutan busur (arc). Pada graf berarah, (u,v) dan (v,u) menyatakan dua busur yang berbeda, dengan kata lain (u,v) (v,u). Untuk simpul u dinamakan simpul asal dan simpul v dinamakan simpul terminal. Gambar di bawah ini merupakan graf berarah.

2.2. Matriks Ketetanggaan (Adjacent 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

2.3. Masalah Lintasan TerpendekGraf yang digunakan dalam pencarian lintasan terpendek adalah graf berbobot, yaitu graf yang setiap sisinya diberikan nilai atau bobot. Bobot pada sisi graf dapat menyatakan jarak antar kota, waktu pengiriman pesan, dan sebagainya. Asumsi yang kita gunakan disini adalah bahwa semua bobot bernilai positif. Secara umum, kata terpendek berarti meminimalisasi bobot pada suatu lintasan pada graf.

2.4. Algoritma DjikstraSampai saat ini, sudah banyak algoritma mencari lintasan terpendek. Algoritma lintasan terpendek yang paling terkenal adalah algoritma Djikstra (sesuai dengan nama penemunya, Edsger W. Djikstra). Dalam naskah aslinya, algoritma Djikstra diterapkan untuk mencari lintasan terpendek pada graf berarah. Namun, algoritma ini juga benar utuk graf tak-berarah.Algoritma Djikstra mencari lintasan terpendek dalam sejumlah langkah. Algoritma ini menggunakan prinsip greedy. Prinsip greedy pada algoritma Djikstra menyatakan bahwa pada setiap langkah kita memilih sisi yang berbobot minimum dan memasukkannya ke dalam himpunan solusi.(Munir : 2009Selain 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)

BAB IIIMATERI POKOK

Data yang digunakan dalam penelitian ini yaitu berupa jarak antar semua tempat wisata di Kota Palembang yang diperoleh berdasarkan pengukuran pada peta Kota Palembang (Google Map). Peta kemudian direpresentasikan dalam sebuah graf lalu dibuat matriks ketetanggaannya dan selanjutnya menentukan lintasan terpendek dari antar tempat wisata dengan menggunakan algoritma Djikstra.

Berdasarkan peta tempat Wisata di Kota Palembang dapat dibuat graf seperti pada gambar di atas. Gambar tersebut merupakan graf berbobot tak berarah yang terdiri atas 12 simpul dimana simpul 1 mewakili Bandara Sultan Mahmud Badarudin dan simpul 2 sampai 12 berturut-turut. Setiap sisi menyatakan jalan roda dua dan roda empat penghubung antar tempat. 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 bandara Sultan Mahmud Badarudin ke tempat lainnya 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 di bawah ini.

Tabel 1 lintasan terpendek dari simpul awal Bandara Sultan Mahmud Badarudin

Tabel 2 Matriks Ketetanggaan Untuk Graf Tempat Wisata Di Palembang

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.

BAB IVKESIMPULANUntuk menentukan lintasan terpendek jika ingin mengunjungi tempat wisata di Kota Palembang dapat menggunakan graf. Dengan menggunakan graf kita dapat menghemat waktu dalam melakukan perjalanan.

DAFTAR PUSTAKA

Google Map. 2014. Peta kota Palembang.

Munir, Rinaldi. 2012. Matematika Diskrit. Bandung: InformatikaSalaki, Deiby T. Penentuan Lintasan Terpendek Dari Fmipa Ke Rektorat Dan Fakultas Lain Di Unsrat Manado Menggunakan Algoritma Djikstra. Universitas Sam Ratulangi.