ALGORITMA PENENTUAN LINTASAN TERPENDEK UNTUK SEMUA PASANGAN SIMPUL
SYAMSUL BARRI
JURUSAN MA TEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETARUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 1997
Jifift.Jlffafi menowng I(amu, mal(a titfal(aaa orang yang aapat mengaCafil(an I(amu; jil(a.Jlffafi mem6iarl(att I(amu (titfal(mem6eri pertoumgatt) malig siapal(afi geratlgatt yang aapat menounlg I(amu (seCain) aari.Jlffafi sesuaafi itu? 'Kflrena itu, fienaal(Cafi I(;paaa.Jlffafi saja orattg-orang mu'min 6ertawal(l(a{ (~. .JlEi 'Imr01I: 160) Sesunggufinya orang-orang 6eriman itu aaaCafi merel(a yang apa6iCa tllSe6ut nama.Jlffafi, gemetarCafi fiati merel(a aan apa6iCa tfi6aeal(an I(;paaa merel(a ayat-ayat-Jfya, 6ertam6afiCafi iman merel(a (I(arenatlya) aan I(;paaa 'TufiannyaCafi merel(a 6ertawal(l(a{ (~. .Jl{.Jlttfaa{: 2) CBerangl(at pagi-pagiCafi I(amu se6agai pengajar iCmu, atau se6agai peeneari i(ml~ atau se6agai pentfengariCmu, atau se6agai pencinta ifinu, (j)an JanganCafi menjaai orang yang I(;Eima (6ul(an pellgajar, 6ul(att peneari, 6ul(an pentfengar aan 6ul(an peneinta ifinu) I(arena I(amu al(an eeCal(a / fianeur (.Jl{- :J{aalts)
'Kflrya I(;ciC ini'Kfl persem6afil(an untul(: !J3apa~ 16u, 'Kfll(a~ .Jlail( aan 'lVponal(anl(u yang tercinta
RINGKASAN SYAMSUL BAHRI. Aigoritma Penentuan Lintasan Terpendek untuk Semua Pasangan SimpuI (The Shortest Path Determination Algorithm for All-Pairs Vertex). Dibimbing oleh AMRIL AMAN dan PRAPTO 1RI SUPRIYO. Graf merupakan pasangan terurut (V,E), dimana V adalah himpunan tak kosong dan terbatas yang anggotanya disebut simpul (vertex) dan E adalah himpunan sisi (edge). Hubungan antara simpul dan sisi tersebut membentuk suatu jaringan (network). Selanjutnya, dari jaringan tersebut dapat ditentukan lintasan(path) yang dilalui untuk suatu pasangan simpul, tetapi masalah yang penting dalam hal ini adalah menentukan Iintasan terpendek (shortest path) di antara Iintasan-Iintasan yang mungkin dari pasangan simpuI tersebut. Hal ini menarik, karena berkaitan dengan masalah pengoptimuman, antara lain meminimumkan biaya dan efisiensi waktu yang digunakan. Ada dua kelas permasalahan lintasan terpendek, yaitu masalah Iintasan terpendek satu pasangan simpuI dan masalah lintasan terpendek untuk semua pasangan simpul. Beberapa algoritma telah dikembangkan untuk menyelesaikan masalah ini ; masing-masing algoritma memiliki penampiJan yang berbeda dalam menyelesaikan suatu permasalahan tertentu. Kelebihan suatu algoritma dibandingkan dengan algoritma lainnya, antara lain ditentukan oleh struktur dan efisiensi dari algoritma tersebut. Salah satu penentu efisiensi dari suatu algoritma adalah banyaknya langkah yang dibutuhkan oleh suatu program yang menggunakan algoritma tersebut dalam menyelesaikan suatu masalah yang berukuran n. Masalah Iintasan terpendek untuk semua pasangan simpul dapat diselesaikan antara lain dengan menggunakan a1goritma Floyd atau algoritma Dijkstra secara berulang-ulang untuk setiap simpul sebagai sumber. Pada kasus terburuk (worst case), algoritma Dijkstra dapat menyelesaikan masalah Iintasan terpendek untuk semua pasangan simpul dengan waktu eksekusi O(n'), dimana n adalah banyaknya simpuI pada suatu jaringan. Untuk masalah yang sarna algoritma Floyd hanya membutuhkan waktu eksekusi O(n'). OIeh karena itu, a1goritma Floyd lebih efisien dibandingkan a1goritma Dijkstra dalam menyelesaikan masalah lintasan terpendek untuk semua pasangan simpuI, jika ditinjau pada kasus terburuk.
ALGORITMA PENENTUAN LINTASAN TERPENDEK UNTUK SEMUA PASANGAN SIMPUL
SYAMSUL BAHRI
Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarj ana Sains pada Program Studi Matematika
JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 1997
Judul Nama NIM
Algoritma Penentuan Lintasan Terpendek untuk Semua Pasangan Simpul Syamsul Bahri G30.0326
Menyetujui, Komisi Pembimbing
~
Dr.
Drs. Prapto Tri Supriyo Pembimbing II
Program Studi
Tanggal Lu Ius
29 NOV 1997
RIWAYAT HIDUP Penulis dilahirkan di Bima pada tanggal 8 Pebruari 1975 sebagai anak ketiga dari enam bersaudara, anak dari pasangan M. Said Yusuf dengan Uneng. Tahun 1993 penulis lulus dari SMA Negeri Sila dan pada tahun yang sama diterima pada Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Aiam, Institut Pertanian Bogor melalui Jalur Seleksi Masuk IPB (USMI). Selama mengikuti perkuliahan di IPB, penulis selain aktif kuliah juga aktif pada organisasi kemahasiswaan di IPB antara lain Senat Mahasiswa FMIPA, Badan Perwakilan Mahasiswa (BPM) FMIPA dan Himpunan Mahasiswa Jurusan Matematika (GUMATIKA) serta Keluarga Muslim Matematika (KAMUSTIKA). Penulis juga pernah menjadi Asisten Pendidikan Agama Islam (PAI) pada tahun ajaran 199611997.
Selain kuliah, penulis juga belajar di
Pesantren Mahasiswadan SaIjana Ulil Albaab - Bogor (1995-1997). Pada akhir masa perkuliahan, penulis melaksanakan Praktek KeIja Lapang (PKL) pada PT. UNINET BHAKTINUSA yaitu pada UniINTERNET Service Provider, dengan judul "Penerapan Aigoritma Dijkstra untuk Menentukan Rute Terpendek pada Jaringan Internet".
PRAKATA AJhamdulillah, puji syukur kehadirat Allah SWT, atas segala rahmat dan karunia-Nya sehingga penulis dapat menyelesaikan karya ilmiah ini. Karya ihniah ini beIjudul "Algoritma Penentuan Lintasan Terpendek untuk Semua Pasangan Simpul". Terima kasih penulis ucapkan kepada berbagai pihak yang telah membantu dalam penyelesaian karya ilmiah ini, antara lain Bapak Dr. Ir. Arnril Arnan, MSc dan Bapak Drs. Prapto Tri Supriyo selaku dosen pembimbing serta Ibu Ir. Sri Nurdiati, MSc. sebagai dosen penguji. Disamping itu, terima kasih juga kepada Bapak Drs. KH. Didin Hafidhuddin, MSc. dan semua Ustadz serta Rochmadi, Asep, Yayat, Agus, Didin, OP dan rekan-rekan santri di PP. UIil Albaab, yang telah memberikan motivasi selama penulis di pesantren UIil Albaab khususnya. T ak lupa pula, penulis mengucapkan terima kasih kepada Fauzy, Dede, Ardi, Djoni dan rekan-rekan angkatan 30 khususnya serta semua pihak yang telah membantu dalam penyelesaian karya ihniah ini baik secara langsung ataupun tidak langsung. Ucapan terima kasih dan penghargaan yang setinggi-tingginya kepada Bapak, Ibu, Kakak, Adik dan semua keluarga yang telah memberikan do' a dan restunya kepada penulis selama masa perkuliahan hingga selesainya karya ihniah ini. Akhimya semoga karya ihniah ini bermanfaat bagi pengembangan ilmu pengetahuan pada umumnya dan penerapan teori graf pada masalah lintasan terpendek pada khususnya.
Bogor, November 1997
Penulis
DAFTAR lSI Halaman DAFfAR TABEL
vi
DAFfAR GAMBAR
vi
PENDAHULUAN
I
Latar Belakang Tujnan Penelitian
1 1
TINJAUAN PUSTAKA
1
Graf Teorema Lintasan Terpendek ............................................................................ . Analisis Algoritma .......... " ......................... " .......................... , ..................... .
1 2 3
PERUMUSAN MASALAH
4
ALGORlTMA FLOYD
4
Struktur dan Solusi RekursifLintasan Terpendek .. , ... ... ... ... ... ... ... ... ... ... ... ...... ... ... .... Penentuan Bobot Lintasan Terpendek ................. ' .......................... ' ... ... ... ... ... ... .... Penentnan Lintasan Terpendek .................................................... " ... ....... ... ... ..... Langkah-Langkah Algoritma Floyd ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ........ ...... ... ... Contoh Kasus ... ... ... ... ... ... ... ... ... ... ... . . . ... . .. ... ... ... ... ... ... ... ... ... ... ... .... ... ... ... ..... Analisis Algoritma Floyd ... ... ... ... ... ... . .. . .. ... ... ... ... ... ... . .. ... ... . .. ... ... ... . .. .. ... ... ... . ... ALGORlTMA DlJKSTRA
5 6 6 7
7
Proses Pelabelan Algoritma Dijkstra ........................................... " ... ... ... . .. ... ...... Langkah-Langkah Algoritma Dijkstra .............. ' .......................... ' ... ... ... ... ... ... .... Penentuan Lintasan Terpendek ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..... Contoh Kasus ................ ,...................................................... ' ... ... ... ... ... . ...... Analisis Algoritma Dijkstra PENERAPAN ALGORlTMA FLOYD KESlMPULAN DAN SARAN
4 5
8 8 8 8 9
9
........ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ....... ... ... ...... ... ... ... ... 11
Kesimpulan ................................................. " ......................... ' . ... ... . .. ... ... .. . . .. Saran ............... ............ ......... ...... ......... ... ......... ......... ............... .................... DAFfARPUSTAKA LAMPIRAN
Program untuk Menentukan Lintasan Terpendek untuk Semua Pasangan Simpul Berdasarkan Algoritma Floyd
II 11
12
DAFTAR TABEL Halaman I. 2. 3.
Jarak antar Kota-Kola di Polau Jawa (dalam km) ..... , .......... ,. ... ... ... ... ... ...... ... ... ...... 10 Jarak Tetpendek antar Setiap Pasangan Kota (dalam km) HasiI Aigoritma Floyd .. , ...... ... ... 10 Kola Kedua yang DiIalui oleh Lintasan dari Kola i ke Kola j ................" ........... ' ...........' . 11
DAFTAR GAMBAR I. 2. 3. 4. 5.
Halaman Graf dengan 6 Simpul ................ , ..................... , .......... " ............................... " 1 Digraf dengan 6 Simpul ............................................................................... " 1 D igraf dengan VI sebagai Sumber ............. , ................................ , ........... ' . .. . ... ..... 2 Lintasan Tetpendek dari Vike Vj dengan Vk sebagai Simpul Antara .................... ' ... ......... 5 Digraf dengan 5 Simpul ......................... ,. ... ... ... ...... ... ...... ... ...... ... ... ... ... ...... .... 6
1
PENDAHULUAN Latar Belakang Hubungan antara objek yang ada di sekitar kita merupakan hal yang sering kita amati, seperti hubungan antara kota-kota dalam atlas, struktur organisasi pada suatu lembaga, hubungan antara komputer-komputer pada suatu jaringan (LANfWAN) dan sebagainya. Fenomena tersebut secara abstrak dapat digambarkan dengan suatu graf (graph), dimana kota-kota, unit dalam organisasi, komputer pada suatu jaringan atau yang sejenisnya digambarkan sebagai simpul (vertex). Sedangkan jalan yang menghubungkan antar kota, kabel/media yang menghubungkan antar komputer atau yang sejenisnya digambarkan sebagai sisi (edges). Masalah lintasan terpendek (shortest path) merupakan masalah kIasik yang sering kita jumpai dalam kehidupan sehari-hari di bemagai sektor kehidupan, antara lain di bidang transportasi, komunikasi dan komputasi. Masalah ini menjadi masalah yang penting, karena berkaitan dengan masalah meminimumkan biaya atau efisiensi waktu yang dibutuhkan. Masalah lintasan terpendek untuk semua pasangan simpul (the all-pairs shortest path) adalah masalah menentukan lintasan terpendek
atau jarak terpendek untuk setiap pasangan simpul yang ada, sehingga tercapai optimalitas fungsi tujuan (objektif) tertentu. Untuk menyelesaikan masalah ini, ada beberapa algoritma yang dapat digunakan seperti algoritrna Dijkstra, aigoritma Bellman-Ford, algoritma Johnson, algoritma Floyd dan lain sebagainya. Pada prakteknya tidak semua algoritrna itu efektif untuk diterapkan atau diimplementasikan pada suatu masalah tertentu. Hal ini disebabkan karena setiap algoritrna mempunyai penampilan yang beIbeda dalam menyelesaikan suatu masalah. Kelebihan suatu algoritma dibandingkan dengan algoritrna lainnya, antara lain ditentukan oleh struktur dan efisiensi dati algoritrna tersebut. Tujuan Penelitian Penelitian ini bertujuan untuk mempelajari dan membandingkan efisiensi antara algoritrna Floyd dan Dijkstra dalam menentukan lintasan terpendek semua pasangan simpul pada suatu graf berarah terbobot berdasarkan banyaknya langkah yang diperJukan untuk menyelesaikan suatu masalah pada kasu. terburuk.
TlNJAUAN PUSTAKA Teori graf (graph theory) merupakan salah satu topik dalam matematika yang peneraparmya dapat menyelesaikan berbagai masalah nyata di berbagai bidang seperti ekonomi, industri, transportasi, sains dan lain sebagainya. Beriknt akan dijelaskan teori-teori dasar graf yang mendasari masalah lintasan terpendek Graf Suatu graf G adalall suatu pasangan terurut (V,E), dimana V adalah suatu himpunan tak kosong dan terbatas yang anggotanya disebut simpul (vertex) dan E adalah himpnnan sisi (edge) [Foulds, 1992]. Gambar la beriknt menunjukkan sebuah graf dengan 6 simpul dan IO sisi.
Gambar lao Graf dengan 6 simpul Pada Gambar la di atas, graf G terdiri atas 6 simpuI yaitu VI • V2 , V3 , V4 , Vs , V6 dan 10 sisi yaitu el ,e2 • e3 , ., • elO_
Gambar lb. Digraf dengan 6 simpul
