penerapan metode graf dan algoritma floyd-warshall …
TRANSCRIPT
PENERAPAN METODE GRAF DAN ALGORITMA
FLOYD-WARSHALL DALAM MENENTUKAN
LINTASAN TERPENDEK
Yudo Komarullah
107094003059
PROGRAM STUDI MATEMATIKA
FAKULTAS SAINS DAN TEKNOLOGI
UNIVERSITAS ISLAM NEGERI SYARIF HIDAYATULLAH
JAKARTA
2013M / 1434H
i
PENERAPAN METODE GRAF
DAN ALGORITMA FLOYD-WARSHALL
DALAM MENENTUKAN LINTASAN TERPENDEK
Skripsi
Sebagai Salah Satu Syarat Untuk Memperoleh
Gelar Sarjana Sains
Fakultas Sains dan Teknologi
Universitas Islam Negeri Syarif Hidayatullah Jakarta
Oleh:
Yudo Komarullah
107094003059
PROGRAM STUDI MATEMATIKA
FAKULTAS SAINS DAN TEKNOLOGI
UNIVERSITAS ISLAM NEGERI
SYARIF HIDAYATULLAH
JAKARTA
2013 M /1434 H
iii
PERNYATAAN
DENGAN INI SAYA MENYATAKAN BAHWA SKRIPSI INI BENAR-BENAR
HASIL KARYA SENDIRI YANG BELUM PERNAH DIAJUKAN SEBAGAI
SKRIPSI ATAU KARYA ILMIAH PADA PERGURUAN TINGGI ATAU
LEMBAGA MANAPUN.
Jakarta, 25 September 2013
Yudo Komarullah
NIM. 107094003059
iv
PERSEMBAHAN
Skripsi ini aku persembahkan untuk
Orang-orang yang kusayang dan juga menyayangiku,
Bapakku Syahrul Halim, Ibuku Murtinah,
kakak dan adikku, saudara-saudaraku, sahabat-sahabatku
dan kepada seluruh keluarga besar Prodi Matematika,
terimakasih atas segalanya.
Semoga kita selalu diridoi Allah SWT
dan selalu dalam lindungan-Nya,
serta selalu dibukakan pintu rahmat,
kasih sayang dan hidayah-Nya kepada kita semua.
Amin.
MOTTO
“Sukses itu Pasti, Bahagia adalah Pilihan”
“Maka nikmat Tuhan kamu yang manakah yang kamu dustakan?”
(Qs. Ar-Rahmaan)
“Berusahalah dengan keras bukan untuk menjadi sukses,
tapi untuk menjadi lebih berharga.”
(Albert Einstein)
“Jangan ikuti kemana jalan menuju,
tetapi buatlah jalan sendiri dan tinggalkan jejak”
(Anonim, Matematika Diskrit Edisi Ketiga : Rinaldi Munir)
v
ABSTRAK
Pemrograman dinamis merupakan sebuah metode penyelesaian masalah
yang memanfaatkan Prinsip Optimalitas. Algoritma Floyd-Warshall merupakan
salah satu jenis dari pemrogaman dinamis. Metode yang dilakukan dalam
memecahkan masalah dengan memandang solusi yang akan diperoleh sebagai
suatu keputusan yang saling terkait. Algoritma Floyd-Warshall yang menerapkan
pemrograman dinamis lebih menjamin keberhasilan penemuan solusi optimum
untuk kasus penentuan lintasan terpendek. Pada skripsi ini akan dibahas mengenai
penentuan bobot lintasan terpendek antar semua pasang simpul dengan
menggunakan metode Graf dan Algoritma Floyd-Warshall.
Kata Kunci : graf, pemrograman dinamis, floyd-warshall, lintasan terpendek,
semua pasang simpul.
vi
ABSTRACT
Dynamic programming is a method of problem solving that utilizes
Principle of Optimality. Floyd-Warshall algorithm is a form of dynamic
programming. The method used to solve the problem by looking at a solution that
would be obtained as an inter-related decisions. Floyd-Warshall algorithm that
applying dynamic programming over the success of the invention ensures
optimum solution for the case of the determination of the shortest path. In this
paper we will discuss the determination of the weight of the all pair shortest path
of edges using the Graf method and Floyd-Warshall algorithm.
Keywords : graphs, dynamic programming, Floyd-Warshall, the shortest path, all
pair shortest path.
vii
KATA PENGANTAR
Segala puja dan puji syukur Alhamdulillah kami panjatkan kehadirat Allah
SWT atas nikmat dan karunianya sehingga penulis dapat menyusun Skripsi
dengan judul “Penerapan Metode Graf dan Algoritma Floyd-Warshall dalam
Menentukan Lintasan Terpendek” dan harapan kami penyusunan skripsi ini
dapat berjalan dengan baik dan lancar.
Penulis menyadari keterbatasan pengetahuan yang penulis miliki, karena
itu tanpa keterlibatan dan sumbangsih dari berbagai pihak, sulit bagi penulis untuk
menyelesaikan penyusunan skripsi ini. Maka dari itu dengan segenap kerendahan
hati patutlah penulis ucapkan terima kasih kepada:
1. Bapak Prof. Dr. Komaruddin Hidayat, selaku Rektor Universitas Islam
Negeri (UIN) Syarif Hidayatullah Jakarta.
2. Bapak Dr. Agus Salim, M. Si, selaku Dekan Fakultas Sains dan Teknologi
UIN Syarif Hidayatullah Jakarta.
3. Ibu Yanne Irene, M.Si, selaku Ketua Prodi Matematika Fakultas Sains dan
Teknologi UIN Syarif Hidayatullah Jakarta.
4. Suma’inna, M.Si, Sekertaris Program Studi Matematika yang selalu
memberikan semangat dan pengorbanannya kepada mahasiswa.
5. Hata Maulana M.T.I, sebagai pembimbing I yang telah banyak membantu
penulis dalam menyelesaikan skripsi ini sampai selesai. Terima kasih
banyak atas semangat, motivasi, ketulusan serta kesabarannya selama
penulis menyelesaikan skripsi ini.
6. Drs. Slamet Aji Pamungkas, M.Eng, sebagai pembimbing II penulis yang
telah banyak membantu penulis memberikan pengarahan, semangat dan
motivasi dalam menyelesaikan skripsi ini sampai selesai.
viii
7. Kepada keluarga besar, Ayah, Ibu dan saudara-saudaraku yang telah
banyak memberikan inspirasi dan motivasi serta dukungannya baik dari
segi materi maupun fisik.
8. Seluruh Dosen prodi Matematika Fakultas Sains dan Teknologi UIN
Jakarta yang telah mengalirkan ilmu, pengetahuan, pengalaman, wacana
dan wawasannya, sebagai pedoman dan bekal bagi penulis.
9. Ika Istiani yang telah menularkan semangatnya, meluangkan waktunya
untuk menjadi tempat mencari inspirasi dan motivasi. Terima kasih atas
segalanya.
10. Sahabat-sahabatku, Ari Pahlevi S.Si, Danang Suyoko S.Si, Gerdyandanu
Nilanto S.Si, yang telah banyak membantuku menyelesaikan skripsi ini.
Dan seluruh teman-teman Matematika 2007. Terima kasih atas
kebersamaannya.
11. Seluruh keluarga besar Prodi Matematika FST UIN Jakarta yang tidak bisa
aku sebutkan satu persatu. Terima kasih banyak, dan tetap SEMANGAT !!
Doa dan harapan penulis atas apa yang telah mereka berikan kepada
penulis, mendapatkan balasan yang lebih besar dari Allah SWT. Amin.
Akhirnya, atas segala kekurangan penulis dalam penulisan skripsi ini
sangat diharapkan saran dan kritik yang bersifat konstruktif dari para pembaca
demi kesempurnaan dari skripsi ini. Semoga skripsi ini dapat memberikan
manfaat dan kontribusi yang berarti, baik bagi para pembaca pada umumnya dan
bagi penulis pada khususnya. Semoga kita semua senantiasa diridlhoi Allah SWT
dan mendapatkan rahmat dan hidayah-Nya serta selalu berada di jalan yang lurus.
Amin.
Jakarta, September 2013
Penulis
ix
DAFTAR ISI
HALAMAN JUDUL ......................................................................................... i
PENGESAHAN UJIAN .................................................................................... ii
PERNYATAAN ................................................................................................. iii
PERSEMBAHAN DAN MOTTO .................................................................... iv
ABSTRAK ......................................................................................................... v
ABSTRACT ....................................................................................................... vi
KATA PENGANTAR ....................................................................................... vii
DAFTAR ISI ...................................................................................................... ix
DAFTAR GAMBAR ......................................................................................... xi
DAFTAR TABEL ............................................................................................. xii
BAB I. PENDAHULIAN .................................................................................. 1
1.1 Latar Belakang .................................................................................. 1
1.2 Permasalahan .................................................................................... 2
1.3 Pembatasan Masalah ......................................................................... 2
1.4 Tujuan Penulisan ............................................................................... 3
1.5 Manfaat Penulisan ............................................................................. 3
BAB II. LANDASAN TEORI .......................................................................... 4
2.1 Konsep Dasar Graf ............................................................................ 4
2.1.1 Jenis-jenis Graf .................................................................. 5
2.1.2 Istilah Dasar ....................................................................... 7
2.2 Lintasan Terpendek ........................................................................... 11
2.3 Algoritma .......................................................................................... 12
2.3.1 Definisi Algoritma ............................................................. 12
x
2.3.2 Konsep Dasar Algoritma ................................................... 13
2.4 Pemrograman Dinamis ..................................................................... 14
2.5 Algoritma Floyd-Warshall ................................................................ 16
BAB III. PENENTUAN LINTASAN TERPENDEK .................................... 18
3.1 Representasi Matriks Bobot .............................................................. 18
3.2 Teorema Lintasan Terpendek ........................................................... 19
3.2.1 Teorema Cormen ............................................................... 20
3.3 Struktur Lintasan Terpendek ............................................................ 21
3.3.1 Langkah-langkah Algoritma Floyd-Warshall .................... 22
3.3.2 Penentuan Lintasan Terpendek .......................................... 23
3.4 Contoh Kasus .................................................................................... 26
BAB VI. ANALISIS HASIL DAN PEMBAHASAN ...................................... 36
4.1 Analisis ............................................................................................. 37
4.1.1 Data masukan (Input) ........................................................ 37
4.1.2 Data Proses ........................................................................ 38
4.1.3 Data Keluaran (Output) ..................................................... 38
BAB V. KESIMPULAN DAN SARAN ........................................................... 42
5.1 Kesimpulan ....................................................................................... 42
5.2 Saran ................................................................................................. 42
DAFTAR PUSTAKA ........................................................................................ 41
LAMPIRAN
xi
DAFTAR GAMBAR
Gambar 2.1 : Tiga buah graf (a) graf sederhana,
(b) graf ganda, (c) graf semu ....................................................... 4
Gambar 2.2 : (a) Graf Berarah, (b) Graf-Ganda Berarah .................................. 7
Gambar 2.3 : Tiga buah graf, , , ........................................................... 8
Gambar 2.4 : Graf Tak-Berarah Tidak Terhubung............................................ 10
Gambar 2.5 : Graf Tak-Berarah dan Berbobot .................................................. 11
Gambar 3.1 : Digraf berbobot dengan 6 simpul ................................................ 19
Gambar 3.2 : Lintasan terpendek dari ke
dengan sebagai simpul perantara ............................................ 21
Gambar 3.3 : Flowchart Sistem ......................................................................... 25
Gambar 3.4 : Digraf berbobot dengan 6 simpul ................................................ 26
Gambar 4.2 : Tampilan Output Program ........................................................... 39
xii
DAFTAR TABEL
Tabel 2 : Jenis-jenis Graf [1] .......................................................................... 8
Tabel 3.1 : Iterasi untuk k = 1 ........................................................................... 28
Tabel 3.2 : Iterasi untuk k = 2 ............................................................................ 29
Tabel 3.3 : Iterasi untuk k = 3 ............................................................................ 30
Tabel 3.4 : Iterasi untuk k = 4 ............................................................................ 31
Tabel 3.5 : Iterasi untuk k = 5 ............................................................................ 33
Tabel 3.6 : Iterasi untuk k = 6 ............................................................................ 34
Tabel 4.1 : Jarak antar Terminal Bus di Jakarta (dalam km)............................ 34
Tabel 4.2 : Jarak terpendek antara setiap pasang Terminal Bus (dalam km) ... 37
Tabel 4.3 : Terminal yang dilalui oleh lintasan dari terminal i ke terminal j ... 37
1
BAB I
PENDAHULUAN
1.1 Latar Belakang
Menurut [2] teori graf adalah ilmu yang berkembang sangat pesat, bahkan
dalam perkembangannya dapat disejajarkan dengan ilmu aljabar yang lebih
dahulu berkembang. Graf digambarkan sebagai kumpulan simpul-simpul yang
dihubungkan oleh sisi. Keunikkan dari teori graf adalah terletak pada
kesederhanaan pokok pembahasan yang dipelajarinya. Secara kasar, graf adalah
suatu diagram yang memuat informasi tertentu jika diinterpretasikan secara tepat
[3].
Optimasi merupakan salah satu topik dalam teori graf. Salah satu
persoalan optimasi yang sering ditemui dalam kehidupan sehari-hari adalah
pencarian lintasan terpendek. Persoalan ini bisa dimodelkan ke dalam suatu graf
berbobot dengan nilai pada masing-masing sisi yang merepresentasikan persoalan
yang akan dipecahkan.
Penentuan lintasan terpendek dari satu titik ke titik yang lain adalah
masalah yang sering ditemui dalam kehidupan sehari-hari. Berbagai kalangan
menemui permasalahan serupa dengan variasi yang berbeda. Contohnya: Seorang
pengantar makanan cepat saji mencari jalur terpendek untuk mengantarkan
makanannya kepada pemesan, pengendara dan penumpang angkutan umum
mencari lintasan terpendek untuk mencapai lokasi yang ingin dituju.
Seiring dengan waktu yang berjalan dan juga perkembangan ilmu
pengetahuan dan teknologi, permasalahan pencarian lintasan terpendek ini telah
terpecahkan dengan berbagai algoritma. Algoritma merupakan urutan langkah-
langkah untuk menyelesaikan masalah secara sistematis. Langkah-langkah
tersebut dapat diterjemahkan secara bertahap dari awal hingga akhir. Beberapa
2
algoritma populer yang memecahkan persoalan, salah satunya adalah Algoritma
Pemrograman Dinamis.
Pemrograman dinamis adalah metode penyelesaian masalah dengan
memecah permasalahan menjadi sub-permasalahan yang berkaitan sehingga
menghasilkan solusi optimal [6]. Hasil solusi optimal ini adalah informasi yang
akan digunakan sebagai penyelesaian permasalahan. Dan salah satu dari bentuk
Algoritma Pemrograman dinamis adalah Algoritma Floyd-Warshall.
Algoritma Floyd-Warshall adalah suatu metode yang melakukan
pemecahan masalah dengan memandang solusi yang akan diperoleh sebagai suatu
keputusan yang saling terkait. Artinya solusi-solusi tersebut dibentuk dari solusi
yang berasal dari tahap sebelumnya dan ada kemungkinan solusi lebih dari satu.
Algoritma Floyd-Warshall yang menerapkan pemrograman dinamis lebih
menjamin keberhasilan penemuan solusi optimum untuk kasus penentuan lintasan
terpendek.
Maka berdasarkan latar belakang tersebut, penulis membuat skripsi
dengan judul “Penerapan Metode Graf dan Algoritma Floyd-Warshall dalam
Menentukan Lintasan Terpendek”.
1.2 Permasalahan
Permasalahan yang akan dibahas pada skripsi ini bagaimana penerapan
Metode Graf dan Algoritma Floyd-Warshall dalam menemukan solusi optimal
pada lintasan terpendek untuk semua pasang simpul (all pair shortest path).
1.3 Pembatasan Masalah
Pembatasan masalah skripsi ini hanya dikhususkan mengkaji penerapan
pencarian lintasan terpendek untuk semua pasang simpul (all pair shortest path)
dengan menerapkan Metode Graf dan Algoritma Floyd-Warshall. Dimana D
didefinisikan sebagai sebuah graf berarah yang memiliki bobot bilangan bulat
positif.
3
1.4 Tujuan Penulisan
Sebagai materi analisa untuk mengetahi, memahami, dan mengkaji kasus
pencarian lintasan dari semua pasang simpul (all pair shortest path) menggunakan
Metode Graf dan Algoritma Floyd-Warshall untuk menemukan solusi optimum.
1.5 Manfaat Penulisan
Adapun manfaat dari penulisan ini secara umum adalah untuk memahami
kajian mengenai Metode Graf dalam permasalahan optimasi penentuan lintasan
terpendek menggunakan Algoritma Floyd-Warshall. Bagi penulis sendiri,
penulisan skiripsi ini menambah ilmu pengetahuan bagi penulis mengenai
Algoritma pencarian lintasan terpendek dengan menggunakan metode ini
nantinya. Bagi peneliti lainnya, penulis berharap skripsi ini bisa menjadi referensi
baik untuk diimplementasikan maupun dikaji lebih jauh lagi.
4
BAB II
LANDASAN TEORI
2.1 Konsep Dasar Graf
Secara matematis, [1] mendefinisikan Graf G sebagai pasangan himpunan
(V,E), ditulis dengan notasi G = (V,E). Dimana V adalah himpunan tidak kosong
dari simpul-simpul (vertex) dan E adalah kumpulan sisi (edges) yang
menghubungkan sepasang simpul.
Menurut definisi tersebut V tidak boleh kosong, sedangkan E boleh
kosong. Jadi, sebuah graf dimungkinkan tidak mempunyai sisi satu buah pun,
tetapi simpulnya harus ada, minimal satu. Graf yang hanya mempunyai sebuah
simpul tanpa satupun sisi disebut graf trifial.
Simpul pada graf dapat dilabeli dengan huruf, seperti a, b, c, ..., v, w, ...,
dengan bilangan asli 1, 2, 3, ... , atau dapat digabungkan keduanya. Sedangkan sisi
yang menghubungkan simpul u dengan simpul v dinyatakan dengan pasangan
(u,v) atau dengan lambang , , .... Dengan kata lain, jika e adalah sisi yang
menghubungkan simpul u dan v , maka e dapat ditulis e =(u,v).
Gambar 2.1 Tiga buah graf (a) graf sederhana, (b) graf ganda, (c) graf semu
5
2.1.1 Jenis-jenis Graf
Menurut [1] graf dapat dikelompokkan menjadi beberapa kategori atau
jenis bergantung pada sudut pandang pengelompokkannya. Pengelompokkan graf
dapat dipandang berdasarkan ada tidaknya sisi ganda atau sisi gelang, berdasarkan
jumlah simpul, atau berdasarkan orientasi arah pada sisi.
Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka
secara umum graf dapat digolongkan menjadi dua jenis:
1. Graf sederhana
Graf yang tidak mengandung gelang maupun sisi-ganda dinamakan graf
sederhana. pada Gambar 2.1(a) adalah contoh graf sederhana yang
merepresentasikan jaringan komputer. Simpul menyatakan komputer, sedangkan
sisi menyatakan saluran telepon untuk berkomunikasi. Saluran telepon dapat
beroperasi pada dua arah.
2. Graf tak-sederhana
Graf yang mengandung sisi ganda atau gelang dinamakan graf tak-
sederhana. Ada dua macam graf tak sederhana, yaitu graf ganda dan graf semu.
Graf ganda adalah graf yang mengandung sisi ganda. Sisi ganda yang
menghubungkan sepasang simpul bisa lebih dari dua buah. pada Gambar
2.1(b) adalah graf ganda. Sisi ganda dapat diasosiasikan sebagai pasangan tak-
terurut yang sama. Kita juga dapat mendefinisikan graf ganda G = (V(G), E(G))
terdiri dari himpunan tidak kosong simpul-simpul dan E adalah himpunan-ganda
yang mengandung sisi ganda. Pada jaringan telekomunikasi, sisi ganda pada
dapat diandaikan sebagai saluran telepon tambahan apabila beban komunikasi
data antar komputer sangat padat. Perhatikanlah bahwa setiap graf sederhana juga
merupakan graf ganda, tetapi tidak setiap graf ganda merupakan graf sederhana.
Graf semu adalah graf yang mengandung gelang. adalah graf semu
(termasuk bila memiliki graf ganda sekalipun). Sisi gelang pada dapat dianggap
6
sebagai saluran telepon tambahan yang menghubungkan komputer dengan dirinya
sendiri. Graf semu lebih umum daripada graf ganda, karena sisi pada graf semu
dapat terhubung ke dirinya sendiri.
Jumlah simpul pada graf kita sebut sebagai kardinalitas graf, dan
dinyatakan dengan n = |V(G)| , dan jumlah sisi kita nyatakan dengan m = |E(G)| .
Pada contoh diatas, mempunyai n = 4, dan m = 4, sedangkan mempunyai n
= 3 dan m = 4.
Sisi pada graf dapat mempunyai orientasi arah. Berdasarkan orientasi arah
pada sisi, maka secara umum graf dibedakan menjadi 2 jenis:
1. Graf Tak-berarah (undirect graph)
Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak
berarah. Pada graf tak berarah urutan pasangan simpul yang dihubungkan oleh sisi
tidak diperhatikan. Jadi ) = ) adalah sisi yang sama. Tiga buah graf pada
Gambar 2.1 adalah graf tak-berarah. Pada jaringan telepon, sisi pada graf berarah
menyatakan bahwa saluran telepon dapat beroperasi pada dua arah.
2. Graf Berarah (directed graph atau digraph)
Graf yang setiap sisinya diberi orientasi arah disebut graf berarah (digraf).
Pada graf berarah, sisi yang berarah disebut busur. Dimana ) dan )
menyatakan dua buah busur yang berbeda, dengan kata lain ) ≠ ). Untuk
busur ), simpul dinamakan simpul asal dan simpul dinamakan simpul
terminal. Pada Gambar 2.2(a) adalah contoh graf berarah. Pada dapat
dibayangkan sebagai saluran telepon yang tidak dapat beroperasi pada dua arah.
Saluran hanya beroperasi pada arah yang ditunjukkan oleh anak panah. Jadi
sebagai contoh, saluran telepon (1, 2) tidak sama dengan saluran telepon (2, 1).
Graf berarah sering dipakai untuk menggambarkan aliran proses, peta lalu lintas
suatu kota (jalan satu arah atau dua arah), dan sebagainya. Pada graf berarah,
gelang diperbolehkan tetapi sisi ganda tidak.
7
Gambar 2.2 (a) Graf Berarah, (b) Graf-Ganda Berarah
Definisi graf dapat diperluas hingga mencakup graf-ganda berarah. Pada graf-
ganda berarah, gelang dan sisi ganda diperbolehkan ada. pada Gambar 2.3(b)
adalah contoh graf-ganda berarah. Tabel 2 meringkas perluasan definisi graf.
Tabel 2. Jenis-jenis graf [1]
Jenis Sisi Sisi ganda
diperbolehkan?
Sisi gelang
diperbolehkan?
Graf sederhana Tak-berarah Tidak Tidak
Graf ganda Tak-berarah Ya Tidak
Graf semu Tak-berarah Ya Ya
Graf berarah Berarah Tidak Ya
Graf-ganda berarah Berarah Ya Ya
2.1.2 Istilah Dasar
Menurut [1], pada Gambar 2.4 graf yang pertama adalah graf
sederhana, adalah graf semu yang mengandung sisi ganda maupun gelang,
sedangkan adalah graf dengan sebuah simpul yang terpisah dari simpul
lainnya. Ketiga graf ini adalah graf tidak-berarah.
8
Gambar 2.3 Tiga buah graf, , ,
Dalam teori graf banyak istilah-istilah dasar mengenai graf yang perlu
diketahui, antara lain:
1. Bertetangga
Dua buah simpul pada graf tak-berarah dikatakan bertetangga jika
keduanya terhubung langsung dengan sebuah sisi. Dengan kata lain, u bertetangga
dengan v jika (u, v) adalah sebuah sisi pada gaf G. Pada Gambar 2.3(a), simpul 1
bertetangga dengan simpul 2 dan 3, tetapi simpul 1 tidak bertetangga dengan
simpul 4.
Pada graf berarah, sisi kita sebut busur. Jika (u, v) adalah busur maka u
dikatakan bertetangga dengan v dan v dikatakan tetangga dari u. Pada gambar
2.3(a), simpul 1 bertetangga dengan simpul 2, dan simpul 2 dikatakakn tetangga
dari simpul 1.
2. Bersisian
Untuk sembarang sisi e = (u, v), sisi e dikatakan bersisian dengan simpul u
dan simpul v. Pada Gambar 2.3(a), sisi (2, 3) bersisian dengan simpul 2 dan
simpul 3, sisi (2, 4) bersisian dengan simpul 2 dan simpul 4, tetapi sisi (1,2) tidak
bersisian dengan simpul 4.
9
3. Derajat
Derajat suatu simpul adalah jumlah sisi yang bersisian pada simpul v.
Derajat tersebut dinotasikan dengan d(v). Simpul v dikatakan genap atau ganjil
tergantung dari nilai d(v) genap atau ganjil. Contohnya pada Gambar 2.3(a) yaitu
d(1) = 2, d(2) = 3. Bila simpul hanya memiliki derajat 1, maka simpul tersebut
disebut Simpul Pendan.
4. Lintasan
Lintasan yang panjangnya n dari simpul awal ke simpul tujuan
didalam graf G ialah barisan berselang-seling simpul-simpul dan sisi-sisi yang
berbentuk sedemikian sehingga ,
, ..., adalah sisi-sisi dari graf G.
Jika graf yang ditinjau adalah graf sederhana, maka kita cukup menuliskan
lintasan sebagai barisan simpul-simpul saja: , , , …, , , karena di
antara dua buah simpul berurutan di dalam lintasan tersebut hanya ada satu sisi.
Sebagai contoh pada Gambar 2.3(a), lintasan 1, 2, 4, 3 adalah lintasan dengan
barisan sisi (1, 2), (2, 4), (4, 3). Istilah lain untuk lintasan adalah jalur.
Pada graf yang mengandung sisi ganda, dinyatakan sebagai barisan
berselang-seling antara simpul dan sisi menghindari kerancuan sisi mana dari sisi-
sisi ganda yang dilalui. Misalnya pada Gambar 2.3(b), 1, , 2, , 3, , 3 adalah
lintasan dari simpul 1 ke simpul 3 yang melalui sisi , , dan .
5. Siklus atau Sirkuit
Lintasan yang berawal dan berakhir pada simpul yang sama disebut sirkuit
atau siklus. Pada Gambar 2.3 (a) 1, 2, 3, 1 adalah sirkuit. Panjang sirkuit adalah
jumlah sisi didalam sirkuit tersebut. Sirkuit 1, 2, 3, 1 pada Gambar 2.3 (a)
memiliki panjang 3. Sirkuit dikatakan sirkuit sederhana jika setiap sisi yang
dilalui berbeda.
10
6. Terhubung
Graf tak-berarah G disebut graf terhubung jika untuk setiap pasang simpul
u dan v di dalam himpunan V terdapat lintasan dari u ke v (yang juga harus berarti
ada lintasan dari u ke v. Jika tidak, maka G disebut graf tak-terhubung.
dan pada Gambar 2.3 adalah graf terhubung, sedangkan tidak.
Graf pada Gambar 2.4 dibawah ini juga contoh graf tang tak terhubung.
Gambar 2.4 Graf Tak-Berarah Tidak Terhubung
6. Matriks Ketetanggaan
Matriks ketetanggaan adalah matriks yang yang mempresentasikan suatu
graf dimana banyak baris dan kolomnya sama dengan banyak titik dalam graf.
Misalkan G adalah graf tidak berarah dengan titik-titik { }. Matriks
ketetanggaan yang yang sesuai dengan graf G adalah matriks A = ( ) yang
didefinisikan.
{
Karena pada graf tak berarah banyak garis yang menghubungkan titik
dengan selalu sama dengan banyak garis yang menghubungkan dengan
maka jelaslah bahwa matriks ketetanggaannya selalu merupakan matriks yang
simetris [3].
11
7. Graf Berbobot
Jika setiap busur mempunyai nilai yang menyatakan hubungan antara 2
buah titik, maka busur tersebut dinyatakan memiliki bobot. Dalam memodelkan
suatu masalah ke dalam graf, ada informasi yang disampaikan pada setiap sisi
graf. Misalnya pada graf yang menggambarkan lintasan bus, dapat ditambahkan
sebuah bilangan pada seiap sisi untuk menunjukkan jarak antara dua buah halte
yang dihubungkan oleh sisi tersebut.
Gambar 2.5 Graf Tak-Berarah dan Berbobot
Matriks berbobot dari Gambar 2.4 adalah :
edcba
e
d
c
b
a
(
0150810
15014110
014090
8119012
1000120
)
2.2 Lintasan Terpendek
Lintasan terpendek merupakan salah satu dari masalah yang dapat
diselesaikan dengan metode graf. Jika diberikan sebuah graf berbobot, masalah
lintasan terpendek adalah bagaimana kita mencari sebuah jalur pada graf yang
meminimalkan jumlah bobot sisi pembentuk jalur tersebut.
Dalam kehidupan sehari-hari, kita seringkali dihadapkan pada
permasalahan pencarian lintasan terpendek. Sebagai contohnya; ketika kita ingin
12
berpergian dari satu tempat ke tempat lainnya, maka yang akan dicari adalah
lintasan mana yang jaraknya paling pendek dari tempat asal menuju tempat
tujuan. Jadi, kita dapat mengartikan lintasan terpendek sebagai jarak minimal dari
beberapa lintasan yang telah diketahui jaraknya masing-masing.
Oleh karena itu, permasalahan pencarian lintasan terpendek dalam graf
merupakan salah satu permasalahan optimasi [1]. Graf yang digunakan dalam
pencarian lintasan terpendek adalah graf berbobot, yaitu graf yang setiap sisinya
diberikan suatu data. Data pada sisi graf dapat menyatakan jarak, waktu, ongkos
dan sebagainya, sedangkan simpul pada graf menyatakan tempat asal atau
tujuan[10].
Permasalahan lintasan terpendek terdiri dari beberapa macam, antara lain :
a) Lintasan terpendek antara dua buah simpul tertentu (a pair shortest path).
b) Lintasan terpendek antara semua pasang simpul (all pair shortest path).
c) Lintasan terpendek dari simpul tertentu ke semua simpul yang lain (single-
source shortest path).
d) Lintasan terpendek antar dua buah simpul yang melalui beberapa simpul
tertentu (intermediate shortest path).
2.3 Algoritma
2.3.1 Definisi Algoritma
Kata algoritma berasal dari latinisasi nama seorang ahli matematika dari
Uzbekistan Al Khawārizmi, sebagaimana tercantum pada terjemahan karyanya
dalam bahasa latin dari abad ke-12 "Algorithmi de numero Indorum". Pada
awalnya kata algorisma adalah istilah yang merujuk kepada aturan-aturan
aritmatik untuk menyelesaikan persoalan dengan menggunakan bilangan numerik
arab. Pada abad ke-18, istilah ini berkembang menjadi algoritma, yang mencakup
semua prosedur atau urutan langkah yang jelas dan diperlukan untuk
menyelesaikan suatu permasalahan. Masalah timbul pada saat akan menuangkan
bagaimana proses yang harus dilalui dalam suatu/sebuah sistem (program) bagi
13
komputer sehingga pada saat eksekusinya, komputer dapat bekerja seperti yang
diharapkan. Programer komputer akan lebih nyaman menuangkan prosedur
komputasinya atau urutan langkah proses dengan terlebih dahulu membuat
gambaran (diagram alur) diatas kertas[8].
Menurut [7], Algoritma adalah urutan langkah-langkah untuk
memecahkan masalah. Algrotima dibutuhkan untuk memerintahkan komputer
mengambil langkah-langkah tertentu dalam menyelesaikan suatu masalah. Pada
umumnya algoritma kurang lebih sama dengan suatu prosedur yang sering
dilakukan setiap hari, misalnya prosedur untuk membuat kopi, atau memasak telur
dan lain-lain.
2.3.2 Konsep Dasar Algoritma
Menurut [7], Algoritma adalah kumpulan instruksi/perintah yang dibuat
secara jelas dan sistematis berdasarkan urutan yang logis (logika) untuk
penyelesaian suatu masalah. French,C.S. (1984) menyatakan sejumlah konsep
yang mempunyai relevansi dengan masalah rancangan program yaitu kemampuan
komputer, kesulitan dan ketepatan. Penerapan dari konsep tersebut biasanya
digunakan dalam rancangan algoritma.
Dalam merancang sebuah algoritma, Fletcher (1991) memberikan
beberapa cara atau metode yaitu kumpulan perintah, ekspresi, tabel instruksi,
program komputer, kode semu dan flow chart, sedangkan Knuth (1973)
menyarankan algoritma fundamental. Untuk keperluanmatematika dan program
komputer metode yang sering digunakan yaitu :
1. Diagram Alir (Flow Chart)
2. Kode Semu (Pseudo Code)
3. Algoritma Fundamental
Knuth (1973) menyatakan 5 komponen utama dalam algoritma yaitu
finiteness, definiteness, input, output dan effectiveness. Sehingga dalam
merancang sebuah algoritma ada 3 (tiga) komponen yang harus ada yaitu:
14
1. Komponen Masukan (input)
Komponen ini biasanya terdiri dari pemilihan variable, jenis variable, tipe
variable, konstanta dan parameter (dalam fungsi).
2. Komponen Proses
Komponen ini merupakan bagian utama dan terpenting dalam merancang
sebuah algoritma. Dalam bagian ini terdapat logika masalah, logika algoritma
(sintaksis dan semantik), rumusan, metode (rekursi, perbandingan, penggabungan,
pengurangan dan lain-lain).
3. Komponen Keluaran (output)
Komponen ini merupakan tujuan dari perancangan algoritma dan program.
Permasalahan yang diselesaikan dalam algoritma dan program harus ditampilkan
dalam komponen keluaran. Karakteristik keluaran yang baik adalah menjawab
permasalahan dan tampilan yang ramah.
2.4 Pemrograman Dinamis
Dengan semakin berkembangnya Algoritma, maka metode-metode yang
ada pada algoritma kemudian diimplementasikan dalam kehidupan sehari-hari
dalam skala yang lebih besar. Salah satu dari implementasi algoritma adalah
pencarian lintasan terpendek. Pencarian lintasan terpendek merupakan materi
dalam teori graf. Didalam graf berbobot terdapat nilai-nilai yang dikenakan disisi-
sisinya, dan dan panjang dari sebuah lintasan merupakan jumlah dari bobot-bobot
sisinya. Misalkan ( , ) menyatakan bobot dari sisi dalam graf. Dalam graf
berbobot tersebut dapat dicari sebuah lintasan terpendek antara dua sisi yang
diketahui bobotnya. Beberapa algoritma bisa digunakan untuk menyelesaikan
permasalahan pencarian lintasan terpendek. Salah satu bentuk Algoritma
pencarian lintasan terpendek adalah Pemrograman Dinamis.
Pemrograman dinamis merupakan metode pemecahan masalah dengan
cara menguraikan solusi menjadi sekumpulan langkah atau tahapan sedemikian
15
sehingga solusi dari persoalan dapat dipandang dari serangkaian keputusan yang
saling berkaitan [4]. Pemrograman dinamis merupakan strategi algoritma dengan
memanfaatkan sebuah prinsip penting, yaitu Prinsip Optimalitas. Prinsip ini
menyatakan bahwa “ suatu kebijakan optimal mempunyai sifat bahwa apapun
keadaan dan keputusan awal, keputusan selanjutnya harus membentuk suatu
kebijakan optimal yang berkaitan dengan keadaan yang dihasilkan dari
keputusan awal ”[5]. Dengan prinsip optimalitas ini, dijamin bahwa pengambilan
keputusan pada suatu tahap adalah keputusan yang benar untuk tahap-tahap
selanjutnya [4].
Pemrograman dinamis memiliki karakter diantaranya:
1. Persoalan dibagi menjadi beberapa tahapan, dimana setiap tahapnya hanya
akan diambil satu keputusan.
2. Masing-masing tahap terdiri atas status yang saling berhubungan dengan
status tersebut. Status yang dimaksud disini adalah berbagai kemungkinan
masukan yang ada pada tahap tersebut.
3. Ketika masuk pada suatu tahap, hasil kemudian akan dtransformasikan.
4. Biaya beban pada suatu tahap akan meningkat secara teratur seiring
bertambahnya jumlah tahapan.
5. Biaya yang ada pada suatu tahap tergantung pada biaya tahapan yang telah
berjalan dan biaya pada tahap itu sendiri.
6. Keputusan yang terbaik pada suatu tahap bersifat independen terhadap
keputusan pada tahap sebelumnya.
7. Terdapat hubungan rekursif yang menyatakan bahwa keputusan terbaik dalam
setiap status pada tahap k akan memberikan memberikan keputusan terbaik
untuk setiap status pada tahap k+1.
8. Prinsip Optimalisasi berlaku pada persoalan yang dimaksud.
Dalam proses penyelesaian menggunakan pemrograman dinamis
pendekatan yang dilakukan ada dua macam, yaitu pendekatan maju dan mundur.
16
Misalkan menyatakan peubah keputusan yang harus dibuat masing-
masing untuk tahap 1, 2, …, n. Maka [4];
1. Pendekatan Maju
Pemrograman dinamis maju bekerja mulai dari tahap 1, terus maju ke
tahap 2, 3, dan seterusnya sampai tahap n. Runtunan peubah keputusan adalah
.
2. Pendekatan Mundur
Pemrograman dinamis mundur bekerja mulai dari tahap n, terus mundur
ke tahap n – 1, n – 2, dan seterusnya sampai tahap 1. Runtunan peubah keputusan
adalah .
2.5 Algoritma Floyd-Warshall
Algoritma Floyd-Warshall adalah suatu metode yang melakukan
pemecahan masalah dengan memandang solusi yang akan diperoleh sebagai suatu
keputusan yang saling terkait. Artinya solusi-solusi tersebut dibentuk dari solusi
yang berasal dari tahap sebelumnya dan ada kemungkinan solusi lebih dari satu.
Algoritma Floyd-Warshall yang menerapkan pemrograman dinamis lebih
menjamin keberhasilan penemuan solusi optimum untuk kasus penentuan lintasan
terpendek antara semua pasang simpul (all pair shortest path).
Dalam menentukan lintasan terpendek, algoritma Floyd-Warshall
melakukan langkah-langkah sebagai berikut;
1. Inisialisasikan simpul asal ke simpul tujuan.
2. Menuliskan jarak sisi dari simpul asal ke simpul berikutnya.
3. Menambahkan jarak sisi pada setiap simpul berikutnya sampai ke simpul
tujuan.
4. Membandingkan nilai sisi pada setiap kemungkinan lintasan yang ditemukan.
5. Memilih lintasan dengan nilai sisi yang paling optimal (kecil).
17
Misalkan terdapat suatu graf G dengan simpul-simpul V yang masing-
masing bemomor 1 s.d. N (sebanyak N buah). Misalkan pula terdapat suatu
fungsi shortestPath (i, j ,k) yang mengembalikan kemungkinan jalur
terpendek dari i ke j dengan hanya memanfaatkan simpul 1 s.d. k sebagai
titik perantara.
Tujuan akhir penggunaan fungsi ini adalah untuk mencari jalur
terpendek dari setiap simpul i ke simpul j dengan perantara simpul 1 s.d.
k+1. Ada dua kemungkinan yang terjadi:
1. Jalur terpendek yang sebenamya hanya berasal dari simpul-simpul
yang berada antara 1 hingga k.
2. Ada sebagian jalur yang berasal dari simpul-simpul 1 hingga k+1 , dan
juga k+1 hingga j.
Perlu diketahui bahwa jalur terpendek dari i ke j yang hanya
melewati simpul 1 s.d. k telah didefinisikan pada fungsi shortestPath (i, j,
k) dan telah jelas bahwa jika ada solusi dari i s.d. k+1 hingga j, maka
panjang dari solusi tadi adalah jumlah dari jalur terpendek dari i s.d. k+1
(yang melewati simpul-simpul 1 s.d. k), dan jalur terpendek dari k+1 s.d.
j Guga menggunakan simpul-simpul dari 1 s.d. k).
Maka dari itu, rumus untuk fungsi shortestPath (i, j, k) bisa ditulis
sebagai suatu notasi rekursif sbb:
Basis-0
shortestPath (i,j, 0) = edgeCost(i,j);
Rekurens
shortestPath (i, j, k)= min(shortestPath (i, j, k-1), shortestPath
(i, k, k-1)+shortestPath (k, j, k-1));
Rumus ini adalah inti dari algoritma Floyd-Warshall. Algoritma ini
bekerja dengan menghitung shortestPath (i, j, 1) untuk semua pasangan (i, j),
kemudian hasil tersebut akan digunakan untuk menghitung shortestPath(i, j, 2)
untuk semua pasangan (i, j) dst. Proses ini akan terus berlangsung hingga k = n
dan kita telah menemukan jalur terpendek untuk semua pasangan (i, j)
menggunakan simpul-simpul perantara.
18
BAB III
PENENTUAN LINTASAN TERPENDEK
Pada bab ini kan dipaparkan mengenai urutan langkah dalam menentukan
lintasan terpendek. Penentuan lintasan terpendek yang akan dibahas adalah
lintasan antar semua pasang simpul (all shortest path). Metode yang akan
digunakan terdiri dari Metode Graf dan Algoritma Floyd-Warshall.
Definisi 3.1 Misalkan ( , ) adalah sisi yang menghubungkan antara
simpul dan dengan arah dari simpul ke atau ( ) . Suatu
bilangan melambangkan bobot panjang, atau harga dari sisi ( , ), atau
( ). Hubungan ini dapat dilambangkan dengan fungsi
(dimana E merupakan himpunan sisi berarah, dan R himpunan bilangan real).
Digraf yang sisi-sisinya diberikan bobot disebut digraf berbobot (weighted
digraph).
3.1 Representasi Matriks Bobot
Definisi 3.2 Misalkan digraf dengan { } dan.
Bobot dari setiap sisi pada digraf D dapat direpresentasikan dengan matriks bobot
yang berukuran (n adalah banyaknya simpul pada digraf D),
dimana adalah bobot sisi berarah dari simpul ke , . Apabila
lintasan berawal dan berakhir pada simpul yang sama atau maka bobot
sisi tersebut adalah 0. Jika tidak terdapat sisi yang menghubungkan antara
dengan maka nilai bobot sisi tersebut adalah , atau ditulis sebagai berikut:
( ) {
( )
( )
(1)
19
Sebagai contoh, diberikan digraf dengan
{ } berikut:
Gambar 3.1 Digraf berbobot dengan 6 simpul
Sesuai Persamaan (1), maka dapat ditentukan nilai . Sebagai contoh, simpul
dengan bobot = 7, maka bobot untuk matriksnya
. Pada kasus lainnya, dapat dilihat bahwa tidak ada sisi yang
secara langsung menghubungkan simpul , sehingga .. Pada
Gambar 3.1, kita berikan bobot 0 karena berawal dan
berakhir pada simpul yang sama.
Selanjutnya, dari digraf D yang diberikan dibentuk matriks bobot sebagai berikut:
[ ]
3.2 Teorema Lintasan Terpendek
Misalkan adalah sisi yang menghubungkan antara simpul dan
dengan arah dari simpul ke atau . Pada sisi tersebut diberikan
nilai ( ). Nilai ini bisa melambangkan bobot, panjang atau harga dari
sisi . Hubungan ini dapat dilambangkan dengan fungsi , dengan
R adalah himpunan bilangan real dan E himpunan sisi berarah.
20
Misalkan digraf D = (V,E) dengan fungsi bobot . Untuk lintasan
, bobot lintasan ini adalah:
∑
dimana W adalah fungsi yang memetakan bobot lintasan p ke suatu bilangan real
atau dilambangkan dengan .
Selanjutnya, didefinisikan bobot lintasan yang diketahui dari simpul u ke v
adalah bobot minimum dari semua kemungkinan lintasan p dari simpul u ke v,
jika terdapat lintasan pada simpul u ke v. Jika tidak, maka bobot lintasan
terpendek dari simpul u ke simpul v sama dengan atau dapat ditulis sebagai
berikut:
{
{ }
Berdasarkan Persamaan (2) dan (3), jika lintasan terpendek dari simpul u ke v,
maka lintasan p memiliki bobot [12].
3.2.1 Teorema Cormen
Misalkan digraf D = (V,E) dengan fungsi bobot dan
adalah lintasan terpendek dari simpul ke . Untuk setiap i dan j
sedemikian sehingga ( ) adalah sub-lintasan
dari lintasan p dari simpul ke , maka adalah lintasan terpendek dari
simpul ke [13].
Bukti: Karena p adalah lintasan terendek dari simpul ke dan untuk
setiap i dan j berlaku adalah sub-lintasan dari p yang dimulai
dari simpul sampai , sehingga lintasan p dapat diuraikan menjadi:
→
→
→
21
Jika terdapat sub-lintasan lain dari ke , disebut dengan bobot
( ) ( ) maka terdapat lintasan lain dari ke disebut . Lintasan
dapat diuraikan menjadi :
→
→
→
Sehingga berdasarkan (3), maka bobot lintasan adalah :
( ( ) ( ))
( ( ) ( ))
Jadi p bukanlah lintasan terpendek karena ada lintasan lain yang bobotnya lebih kecil dari
lintasan p [ . Kontradiksi dengan p sebagai lintasan terpendek dari ke
[12].
3.3 Struktur Lintasan Terpendek
Misalkan diberikan digraf D = (V,E), dengan { } dan
{ } untuk sembarang k merupakan himpunan bagian dari V.
Andaikan setiap lintasan dari simpul ke mempunyai simpul antara yang
berada dalam himpunan dan p adalah lintasan yang mempunyai bobot
minimum diantara lintasan-lintasan tersebut.
Jika adalah simpul antara pada lintasan p, maka lintasan p dapat
diuraikan menjadi
→
→ , seperti yang ditunjukkan olehGambar 3.1
berikut.
Gambar 3.2 Lintasan terpendek dari ke dengan sebagai simpul perantara
22
Didefinisikan
adalah panjang lintasan terpendek dari ke
sedemikian sehingga semua simpul perantara pada lintasan (jka ada) terdapat pada
himpunan { }. Maka terdapat dua kemungkinan:
1. Jika , maka lintasan dari ke tidak mempunyai simpul antara
sehingga
.
2. Jika , maka lintasan dari simpul ke dapat diuraikan dengan
sebagai simpul antara. Selanjutnya
ditentukan sebagai minimum dari
dan
Berdasarkan uraian tersebut, definisi rekursif
diberikan persamaan berikut :
{
{
}
3.3.1 Langkah-langkah Algoritma Floyd Warshall
Misalkan diberikan digraf berbobot , dengan
{ }. Didefinisikan matriks
adalah matriks berukuran
, dimana setiap elemennya merupakan bobot lintasan terpendek dari simpul
ke dengan semua simpul antara yang berada dalam himpunan
{ }. Untuk menentukan bobot lintasan terpendek dari sembarang dua
simpul pada digraf D, kita harus membentuk barisan terlebih
dahulu.
Matriks merupakan matriks yang elemennya memuat bobot sisi
berarah dari digraf sehingga [
] . Selanjutnya,
berdasarkan Persamaan (3), barisan matriks dapat ditentukan.
Bobot lintasan terpendek setiap pasang simpul pada digraf D diberikan oleh
matriks [
].
23
Berdasarkan uraian tersebutl, prosedur untuk menentukan bobot lintasan
terpendek menggunakanjika diberikan digraf dengan
{ } adalah sebagai berikut:
1. Tentukan matriks [
] sebagai matriks bobot berukuran atau
dengan kata lain .
2. Tentukan [
] , untuk k = 1, 2, ..., n dengan
{
} untuk setiap i, j = 1, 2, ..., n.
3. Bobot lintasan terpendek dari simpul ke , adalah nilai dari
setiap elemen pada matriks [
].
3.3.2 Penentuan Lintasan Terpendek
Definisi 3.3 Misalkan diberikan digraf berbobot , dengan
{ }. Didefinisikan adalah simpul kedua pada lintasan dari
simpul ke dan matriks predecessor (simpul antara)
adalah
matriks yang berukuran yang setiap elemennya merupakan simpul kedua
pada lintasan dari simpul ke dengan semua simpul antara yang berada pada
{ }.
Matriks
adalah kondisi awal dari matriks predecessor yang
ditentukan dengan
= j, . Selanjutnya untuk k = 1, 2, 3, ..., n, nilai
ditentukan berdasarkan matriks , yaitu dengan membandingkan antara nilai
dengan nilai
sebagai berikut :
{
24
Karena lintasan dari ke dengan sebagai simpul antara kemungkinan
memiliki lintasan yang lebih pendek dibandingkan tanpa . Hal ini disebabkan
karena
lebih kecil dari
.
Simpul antara pada lintasan dari simpul ke , diberikan
oleh matriks
. Berdasarkan matriks tersebut, penentuan lintasan
dilakukan sebagai berikut:
1. Jika simpul kedua sama dengan , maka tidak terdapat simpul antara pada
lintasan dari simpul ke . Sebaliknya jika simpul kedua tidak sama dengan
, sebut , maka selanjutnya tentukan simpul kedua pada lintasan dari
simpul ke dan dari simpul ke .
2. Jika simpul kedua pada lintasan dari simpul ke sudah sama dengan
dan simpul ke belum juga sama dengan (sebut ), maka tentukan
lagi simpul kedua pada lintasan tersebut (simpul ke ). Demikian
seterusnya sampai tidak lagi diperoleh lintasan keduanya (sampai lintasan
keduanya sama dengan ).
3. Lintasan yang dilalui oleh lintasan terpendek dari ke adalah barisan dari
simpul .
25
Start
Tentukan n, Matriks bobot n x n
Matriks Predecessor
k<0, k<n, k++
i<0, i<n, i++
j<0, j<n, j++
Tidak Ya
Selesai
Gambar 3.3 Flowchart Algoritma Floyd-Warshall dan Penentuan Lintasan
Terpendek
26
3.4 Contoh Kasus
Misal terdapat sebuah dgraf berbobot , dengan
{ } seperti gambar dibawah :
Gambar 3.4 Digraf berbobot dengan 6 simpul
Penyelesaian :
Langkah-langkah untuk menentukan jarak terpendek dari ke
dengan menggunakan algoritma Floyd-Warshall adalah
sebagai berikut:
1. Pada awalnya berikan bobot pada masing-masing sisi yang berhbungan.
Sesuai dengan Persamaan (1). Berikan bobot 0 (i = j) pada titik yang berawal
dan berakhir pada simpul yang sama. Perhatikan bahwa lintasan terpendek
tidak boleh mengandung dua buah simpul yang sama didalamnya. Dan
berikan bobot ’∞’ pada titik yang tidak saling berhubungan. Matriks digraf
awal berukuran yang dibentuk dari Gambar 3.2 adalah sebagai berikut:
[ ]
27
2. Menentukan kondisi awal matriks predecessor
dimana
anggotanya merupakan simpul kedua pada lintasan dari ke , atau dengan
kata lain
= j, sesuai dengan Definisi 3.3. Maka matriks
predecessor awalnya adalah :
[ ]
3. Menentukan [
] untuk k = 1, 2, ..., n dengan
{
} untuk setiap i, j = 1, 2, ..., n.
4. Jika
maka nilai
=
Jika tidak
demikian, maka
Perhatikan pada langkah ke 3 dan 4, kita diharuskan menentukan bobot
lintasan terpendek dan menentukan lintasan terpendek yang dilalui oleh setiap
pasang titik dengan melakukan iterasi sebanyak n kali. Berikut adalah penjelasan
langkah-langkahnya :
Iterasi untuk k = 1
Pilih bobot terkecil dari titik-titik yang berhubungan
{
} untuk setiap i, j = 1, 2, ..., n. Kemudian tentukan simpul
lintasan terkecilnya sesuai dengan Persamaan (4).
{
} { }
, maka
= 3
Artinya adalah, simpul bukan simpul kedua yang menjadi solusi
lintasan terpendek dari simpul ke .
28
{
} { }
Karena
, maka
Artinya adalah, simpul merupakan simpul kedua yang menjadi solusi
lintasan terpendek dari simpul ke . Sehingga lintasan terpendek dari
simpul ke adalah .
{
} { }
Karena
, maka
Sehingga lintasan terpendek dari simpul ke menjadi, .
Dengan cara yang sama bobot dan simpul pada matriks predecessor dihitung
untuk setiap i, dan j.
Tabel 3.1 Iterasi untuk k = 1
=0
= 7
= 2
{
}
=0 0 7 2
0 4 1
0 1
= 4 0 6
= 2 2 9 2 4 0 3
3 0
Didapatkan matriks digraf dan predecessor untuk iterasi k = 1 :
29
Iterasi untuk k = 2
Iterasi untuk k = 2 dilakukan dengan cara yang sama seperti iterasi untuk
k = 1, hanya titik perantaranya adalah titik . Dengan cara yang sama pula
dilakukan iterasi untuk k = 3, 4, 5, 6.
{
} { }
Karena
, maka
Artinya adalah simpul merupakan simpul kedua antara simpul dan
simpul yang menjadi solusi lintasan terpendek. Sehingga lintasan terpendek
dari simpul ke menjadi .
{
} { }
Karena
, maka
{
} { }
Karena
, maka
{
} { }
Karena
, maka
Tabel 3.2 Iterasi untuk k = 2
=
= 0
= 4
= 2
= 1
{
}
=7 0 7 11 2 8
=0 0 4 1
0 1
= 4 4 8 0 5
= 9 2 9 2 4 0 3
3 0
30
Didpatkan matriks digraf dan predecessor untuk iterasi k = 2 :
Iterasi untuk k = 3
Tabel 3.3 Iterasi untuk k = 3
=
=
= 0
=
= 1
{
}
=11 0 7 11 2 8
=4 0 4 1
= 0 0 1
= 8 4 8 0 5
= 2 2 9 2 4 0 3
3 0
Matriks digraf dan predecessor untuk iterasi k = 3 :
31
Iterasi untuk k = 4
{
} { }
Karena
, maka
{
} { }
Karena
, maka
{
} { }
Karena
, maka
{
} { }
Karena
, maka
Tabel 3.4 Iterasi untuk k = 4
=0
= 4
= 8
= 0
= 5
{
}
=2 0 6 10 2 7
0 4 1
= 0 1
= 0 4 8 0 5
= 4 2 8 2 4 0 3
3 0
Matriks digraf dan predecessor untuk iterasi k = 4 :
32
Iterasi untuk k = 5
{
} { }
Karena
, maka
{
} { }
Karena
, maka
{
} { }
Karena
, maka
{
} { }
Karena
, maka
{
} { }
Karena
, maka
{
} { }
Karena
, maka
{
} { }
Karena
, maka
{
} { }
Karena
, maka
{
} { }
Karena
, maka
{
} { }
Karena
, maka
{
} { }
Karena
, maka
33
{
} { }
Karena
, maka
{
} { }
Karena
, maka
{
} { }
Karena
, maka
{
} { }
Karena
, maka
{
} { }
Karena
, maka
{
} { }
Karena
, maka
Tabel 3.5 Iterasi untuk k = 5
=2
= 8
= 2
= 4
= 0
= 3
{
}
=7 0 6 9 2 7 10
=1 3 0 3 5 1 4
= 1 3 9 0 5 1 4
= 5 7 4 7 0 5 8
= 0 2 8 2 4 0 3
= 3 5 11 5 7 3 0
34
Matriks digraf dan predecessor untuk iterasi k = 5 :
Iterasi untuk k = 6
Tabel 3.6 Iterasi untuk k = 6
=5
=11
= 5
= 7
= 3
= 0
{
}
=10 0 6 9 2 7 10
=4 3 0 3 5 1 4
= 4 3 9 0 5 1 4
= 8 7 4 7 0 5 8
= 3 2 8 2 4 0 3
= 0 5 11 5 7 3 0
Matriks digraf dan predecessor untuk iterasi k = 6:
Bobot dari semua pasang lintasan terpendek direpresentasikan oleh
matriks , dan lintasannya direpresentasikan oleh . Sebagai contoh, lintasan
terpendek dari simpul yang diperoleh dari matriks . Perhatikan
35
(baris 1, kolom 3 pada matriks ) = 5, artinya simpul kedua pada lintasan
adalah simpul . Maka didapat lintasan terpendeknya adalah :
.
Langkah selanjutnya adalah memeriksa apakah terdapat simpul kedua
(simpul antara) dari simpul ke dan dari simpul ke dengn memeriksa
matriks . Perhatikan
, dan
, yang artinya adalah terdapat
simpul kedua dari simpul ke yaitu simpul . Sedangkan dari simpul ke
melalui simpul (tidak ada simpul kedua yang dilalui simpul ke yang
merupakan solusi lintasan terpendeknya). Sehingga lintasan terpendeknya
menjadi :
Periksa kembali apakah terdapat simpul kedua yang menjadi solusi
lintasan terpendek antara simpul ke dan dari simpul ke . Perhatikan
bahwa
, dan
. Berarti tidak ada simpul kedua yang
menghubungkan simpul ke , sedangkan merupakan simpul kedua yang
menjadi solusi lintasan terpendek antara simpul ke . Sehingga lintasan
terpendeknya berubah menjadi :
Selanjutnya periksa kembali untuk memastikan apakah terdapat simpul kedua
antara simpul dan dari simpul . Perhatikan
, dan
Artinya adalah, tidak ada lagi simpul kedua dari simpul dan
dari simpul yang merupakan solusi lintasan terpendek dari simpul
awal ke simpul tujuan . Sehingga dapat diambil kesimpulan bahwa lintasan
merupakan solusi optimum lintasan terpendek dari
simpul ke dengan bobot atau panjang lintasan sebesar
(baris 1,
kolom 3, Matriks .
36
BAB IV
ANALISIS DAN PEMBAHASAN
Berikut ini diberikan contoh penerapan Metode Graf dan Algoritma Floyd-
Warshall pada permasalahan transportasi, yaitu menentukan rute atau lintasan
terpendek antara terminal bus yang ada di kota Jakarta yang dilalui oleh angkutan
umum. Data diperoleh dari hasil pencarian di google map [maps.google.com].
Tabel 4.1 Jarak antar Terminal Bus di Jakarta (dalam km)
1 2 3 4 5 6 7 8 9 10
1 0 25 34 19 24 5 23 11 27 13
2 25 0 12 5 24 16 17 12 34 26
3 26 17 0 17 17 29 11 25 25 39
4 28 5 16 0 22 14 19 10 38 24
5 18 30 18 24 0 15 13 17 13 15
6 4 19 27 13 16 0 16 6 27 14
7 17 20 9 17 11 15 0 14 21 22
8 11 19 18 12 15 8 10 0 26 21
9 35 37 23 33 10 25 21 27 0 23
10 15 29 37 23 15 13 26 21 26 0
Keterangan :
1. Terminal Pulogadung
2. Terminal Kampung Rambutan
3. Terminal Lebak Bulus
4. Terminal Pinang Ranti
5. Terminal Grogol
6. Terminal Rawamangun
7. Terminal Blok-M
8. Terminal Kampung Melayu
9. Terminal Kalideres
10. Terminal Tanjung Priok
37
4.1 Analisis
Proses analisis dibagi menjadi dua macam, yaitu analisis data dan
pembahasan data berdasarkan alur program yang dibuat menggunakan flow chart.
4.1.1 Data Masukan (Input)
Jika terminal-terminal yang ada di Kota Jakarta dianggap sebagai simpul,
dan jalur angkutan umum yang menghubungkan antara terminal-terminal tersebut
dianggap sebagai sisi berarah yang bobotnya sesuai dengan jarak antar terminal-
terminal tersebut. Sedangkan jarak dari lintasan yang berawal dan berakhir pada
simpul yang sama diberikan bobot 0.
Berdasarkan Tabel 4.1 dapat kita ketahui jarak mula-mula lintasan
angkutan uum antar terminal yang ada di kota Jakarta. Sebagai contoh, jarak dari
Terminal Pulogadung (1) ke Terminal Kampung Rambutan (2) adalah 25 km.
Begitupula sebaliknya, dari Terminal Kampung Rambutan ke Terminal
Pulogadung juga berjarak 25 km. Hal ini berarti lintasan yang menghubungkan
kedua terminal tersebut adalah sama, namun arahnya berlawanan.
Berikutnya, perhatikan bobot lintasan dari Terminal Lebak Bulus (3) ke
Terminal Rawamangun (6) sebesar 29 km. Berbeda bila kita mengambil rute
sebaliknya, yaitu sebesar 27 km. Hal itu bisa terjadi bila rute yang dilalui
angkutan umum antar kedua terminal tersebut berbeda. Dapat kita lihat contoh
lainnya dari Terminal Grogol (5) menuju Terminal Kampung Melayu (8) dengan
arah sebaliknya. Dari semua hal tersebut, terdapat 2 kemungkinan yang terjadi:
1. Lintasan yang yang terdaftar sudah optimal
Hal ini dapat terjadi bila tidak ada lintasan yeng lebih optimal dari lintasan
sebelumnya. Atau dengan kata lain, tidak ada terminal perantara yang
memberikan solusi optimal untuk lintasan dari terminal i ke terminal j.
2. Ada lintasan yang lebih optimal dari lintasan sebelumnya
38
Kemungkinan yang ke-2 dapat terjadi bila terdapat terminal perantara yang
meghasilkan lintasan terpendek dan dapat dilalui oleh lintasan dari terminal i
ke terminal j.
4.1.2 Data Proses
Proses dalam sistem penentuan lintasan terpendek dilakukan dengan
melakukan langkah-langkah pada algorima floyd-warshall seperti yang telah
dibahas pada bab sebelumnya. Data yang telah diperoleh sebelumnya
direpresentasikan dalam bentuk matriks ketetanggaan, seperti yang terlihat pada
Tabel 4.1. Dari data tersebut kemudian akan ditentukan bobot lintasan terpendek
yang menghubungkan semua simpul yang ada, atau dalam kasus ini adalah
lintasan terpendek antar terminal di kota Jakarta.
Selain itu, pada proses penentuan lintasan terpendek juga akan ditentukan
simpul pendahulu. Dalam kasus ini simpul pendahulu merepresentasikan lintasan
mana saja yang dilalui dalam menentukan lintasan terpendek dari terminal i ke
terminal j.
4.1.3 Data Keluaran (Output)
Data keluaran yang diperoleh dari proses penentuan lintasan
terpendek ini adalah :
1. Matriks bobot yang merepresentasikan bobot optimum lintasan terpendek
yang dilalui antar semua pasang simpul dari terminal-terminal di kota Jakarta
yang telah ditentukan sebelumnya.
2. Matriks Pendahulu (predecessor) yang merepresentasikan terminal perantara
yang dilalui oleh lintasan dari terminal i ke terminal j bila terbukti simpul
tersebut terbukti memberikan solusi yang lebih optimal dalam menentukan
lintasan terpendek.
Tabel 4.2 dan Tabel 4.3 berikut berturut-turut merupakan matriks yang
merepresentasikan lintasan terpendek antara setiap pasang terminal di kota Jakarta
39
dan terminal antara yang dilalui dalam satu lintasan antar terminal. Hasil ini
diperoleh dengan menggunakan metode graf dan algoritma Floyd-Warshall
(program terlampir).
Tabel 4.2 Jarak terpendek antara setiap pasang Terminal Bus (dalam km)
1 2 3 4 5 6 7 8 9 10
1 0 23 29 18 21 5 21 11 27 13
2 25 0 12 5 24 16 17 12 34 26
3 26 17 0 17 17 26 11 25 25 32
4 18 5 16 0 22 14 19 10 35 24
5 18 29 18 24 0 15 13 17 13 15
6 4 18 24 13 16 0 16 6 27 14
7 17 20 9 17 11 15 0 14 21 22
8 11 17 18 12 15 8 10 0 26 21
9 28 37 23 33 10 25 21 27 0 23
10 15 28 33 23 15 13 26 19 26 0
Tabel 4.3 Terminal yang dilalui oleh lintasan dari terminal i ke terminal j
1 2 3 4 5 6 7 8 9 10
1 1 6 8 6 6 6 6 8 9 10
2 6 2 3 4 5 6 7 8 9 10
3 1 2 3 4 5 7 7 8 9 5
4 6 2 3 4 5 6 7 8 5 10
5 1 4 3 4 5 6 7 8 9 10
6 1 4 8 4 5 6 7 8 9 10
7 1 2 3 4 5 6 7 8 9 10
8 1 4 3 4 5 6 7 8 9 10
9 5 2 3 4 5 6 7 8 9 10
10 1 4 5 4 5 6 7 6 9 10
40
Berdasarkan Tabel 4.2, lintasan terpendek yang akan dilalui untuk
mencapai terminal yang menjadi tujuan dengan mudah dapat ditentukan. Sebagai
contoh, misalkan dari Pulogadung (1) kita ingin menuju ke Kampung Rambutan
(2). Berdasarkan tabel 2, didapatkan panjang lintasan terpendek yang dilalui
adalah 23 kilometer (lihat baris ke 1 kolom 2, Tabel 4.2).
Berdasarkan Tabel 4.3, perhatikan bahwa untuk menuju Kampung
Rambutan dari Pulogadung maka terminal yang harus dilalui adalah Rawamangun
(6) (lihat baris 1 kolom 2, Tabel 4.3). Sehingga lintasanan terpendeknya adalah :
Pulogadung (1)Rawamangun (6)Kampung Rambutan (2).
Selanjutnya periksa kembali apakah terdapat terminal kedua antara
Terminal Pulogadung ke Rawamangun, dan Terminal rawamangun ke Kampung
Rambutan. Perhatikan kembali Tabel 4.3, dari Terminal Pulogadung (1) menuju
Rawamangun (6) maka harus melalui Rawamangun (6) (lihat baris 1 kolom 6,
Tabel 4.3). Hal tersebut berarti tidak ada terminal kedua antara Pulogadung (1)
dengan Rawamangun yang merupakan solusi optimum rute terpendek. Sedangkan
dari Terminal Rawamangun (6) ke Kampung Rambutan (2), terdapat terminal
antara yang dilalui kedua terminal tersebut adalah Terminal Pinang Ranti (4)
(lihat baris 6 kolom 2, Tabel 4.3). Sehingga lintasan terpendeknya berubah
menjadi :
Pulogadung (1)Rawamangun (6)Pinang Ranti (4)Kampung Rambutan (2)
Lakukan langkah yang sama, yaitu memeriksa kembali apakah terdapat
terminal antara yang dilalui dari Terminal Rawamangun (6) ke Pinang Ranti (4),
dan Pinang Ranti (4) ke Kampung Rambutan (2). Perhatikan Tabel 4.3 pada baris
6 kolom 4, dan pada baris 4 kolom 2. Terlihat bahwa daiantara terminal-terminal
tersebut sudah tidak ada lagi terminal kedua yang dilalui yang merupakan solusi
optimal lintasan terpendek. Sehingga dapat diambil kesimpulan bahwa lintasan
yang terpilih apabila kita ingin pergi dari Pulogadung menuju Kampung
Rambutan untuk mendapatkan jarak terpendek adalah:
41
Pulogadung Rawamangun Pinang Ranti Kampung Rambutan
Dari Tabel 4.3 juga terlihat pada baris ke 7 (Terminal Blok-M) tidak
terjadi perubahan lintasan. Tidak ada lintasan antara yang menghubungkan Blok-
M dengan terminal yang ada, itu artinya lintasan dari Blok-M ke semua terminal
sudah optimum sebelumnya.
42
BAB V
KESIMPULAN DAN SARAN
5.1 Kesimpulan
Permasalahan perncarian lintasan terpendek, waktu dan biaya minimum
merupakan fenomena nyata yang ada dikehidupan sehari-hari. Ada banyak sekali
algoritma yang telah dikembangkan untuk menyelesaikan masalah ini, salah
satunya adalah Algoritma Floyd-Warshall yang termasuk dalam Permrograman
Dinamis. Prinsip yang dipegang oleh pemrograman dinamis adalah prinsip
optimalitas, yaitu jika solusi total optimal, maka bagian solusi sampai suatu tahap
juga optimal.
Ditinjau berdasarkan kasus terburuknya, algoritma Floyd-Warshall yang
menerapkan solusi optimum untuk kasus penentuan lintasan terpendek semua
pasang simpull (all pair sort path) pada simpul digraf (graf berarah) D dengan n
simpul membutuhkan waktu eksekusi dengan hasil yang akurat. Algoritma
ini sangat mudah dimengerti, dan sangat mudah untuk diimplementasikan dalam
kehidupan sehari-hari.
5.2 Saran
Tulisan ini hanya membahas mengenai sebagian kecil dari penerapan teori
graf untuk masalah lintasan terpendek dengan algoritma Floyd-Warshall. Ada
beberapa hal yang dapat dikembangkan lebih lanjut, yaitu dengan merancang
aplikasi untuk mengimplementasikan algoritma ini dalam kehidupan sehari-hari.
Selain itu juga ada beberapa hal yang dapat dikaji lebih lanjut, diantaranya adalah
membandingkan algoritma Floyd-Warshall dengan algoritma lainnya untuk
menyelesaiakan permasalahan pencarian lintasan terpendek.
43
DAFTAR PUSTAKA
[1] Munir, Rinaldi. Matematika Diskrit Edisi Ketiga. Informatika,
Bandung, 2007.
[2] Ngurah, Anak Agung Gede. Ketotalsisiajaiban Graf Dan
Defisiensinya. Central Library Institute Technology Bandung,
2007.
[3] Jek Siang, Jong. Matematika Diskrit dan Aplikasinya Pada Ilmu
Komputer. Andi, Yogyakarta, 2002.
[4] Munir, Rinaldi, “Diktat Kuliah IF2251 Program Dinamis (Bagian
1)”. Informatika ITB, Bandung,
[5] Dynamic Programming : Universitas Oxford. Pada tanggal 15
September 2012 pukul 02.51 WIB. http://www.oxford-
mphil.com/images/c/.../Dynamic-programming-4-principle.pdf.
[6] Subagyo. Pangestu, Marwan Asri dan T. Hani Handoko. Dasar-
Dasar Operations Research Edisi Kedua. PTBPFE, Yogyakarta,
2000.
[7] “Buku Ajar Metode Numerik,” didanai oleh Proyek HEDS, 2002.
[8] Algoritma : Wikipedia. Pada tanggal 21 September 2012 pukul
20.35 WIB. http://id.wikipedia.org/wiki/Algoritma
[9] Cormen, Thomas H, et al. Introduction to Algorithm. McGraw-Hill
Book Company, New York, 1994.
[10] Nilanto, Gerdyandanu. “Sistem Informasi Pencarian Lintasan
Terpendek Menggunakan Pemrograman Dinamis,” skripsi, UIN
Syarif Hidayatullah, Jakarta, 2011.
[11] Hartsfield, Nora., Ringer, Gerhard. Pearls in graph theory a
comprehensive introduction. Academic press: San Diego. 1990
[12] Bahri, Syamsul, “Algoritma Penentuan Lintasan Terpendek Untuk
Semua Pasangan Simpul,” skripsi, Matematika IPB, Bogor, 1997.
44
LAMPIRAN
Program untuk menentukan lintasan terpendek semua pasang simpul dari suatu
digraf berbobot menggunakan Algoritma Floyd-Warshall.
/*Nama Program : Floyd
Tujuan : Menentukan matriks bobot lintasan terpendek dan matriks
predecessor dari suatu digraf berbobot sesuai dengan
Algoritma Floyd-Warshall.
Catatan :
a. Data yang diinput berupa matriks bobot dari suatu digraf matriks bobot
yang disimpan dengan format file *.txt .
Sebagai contoh: Misalkan kita memiliki matriks bobot yang berukuran
3x3, dengan elemen berturut-turut:
Maka matriks tersebut diinput dalam susunan sebagai berikut:
3
Kemudian file tersebut disimpan satu folder dengan program aplikasi yang
telah dibuat.
b. Output yang dihasilakan berupa Matriks Bobot dan Matriks Predecessor
awal sampai pada iterasi ke-n (n adalah ukuran matriks).
#include <stdio.h>
int n; /* Jumlah simpul */
int dist[10][10];
int pred[10][10];
void printDist() {
int i, j ;
printf("W = \n");
printf(" ");
45
for (i = 0; i < n; ++i)
printf("%4c", '1' + i);
printf("\n");
for (i = 0; i < n; ++i) {
printf("%4c", '1' + i);
for (j = 0; j < n; ++j)
printf("%4d", dist[i][j]);
printf("\n");
}
printf("\n");
{
printf("p = \n");
printf(" ");
for (i=0;i<n;++i)
printf("%4c", '1' + i);
printf("\n");
for (i = 0; i < n; ++i) {
printf("%4c", '1' + i);
for (j=0; j<n; ++j)
printf("%4d", pred[i][j]);
printf("\n");
}
}
printf("\n");
}
void floyd_warshall() {
int i, j, k;
for (k = 0; k < n; ++k) {
printf(" iterasi untuk k=%d \n",k);
printf("\n");
printDist();
46
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
{
if ((dist[i][k] * dist[k][j] != 0) && (i != j))
if ((dist[i][k] + dist[k][j] < dist[i][j])||
(dist[i][j] == 0))
{
dist[i][j] = dist[i][k] + dist[k][j];
pred[i][j]=k+1;
}
}
}
printDist();
}
int main(int argc, char *argv[]) {
/* memanggil data berupa Matriks Bobot */
FILE *fin = fopen("Data.txt", "r");
fscanf(fin, "%d", &n);
int i, j;
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
fscanf(fin, "%d", &dist[i][j]);
printf("\n");
for (i=0; i<n;++i)
for (j=0;j<n;++j)
pred [i][j]=j+1;
fscanf(fin, "%d", &pred[i][j]);
fclose(fin);
floyd_warshall();
return 0;
}