BAB IV ANALISIS PEMILIHAN ALGORITMA LINTASAN TERPENDEK DAN PENYELESAIAN KASUS RUTE PENERBANGAN DOMESTIK 4.1. Langkah Pemilihan dan Penerapan Algoritma Seiring dengan perkembangan teknologi yang makin pesat termasuk dalam aplikasi dari algoritma pencarian lintasan terpendek, maka sangat penting untuk memilih algoritma yang tepat agar diperoleh hasil yang optimal. Ada banyak pilihan algoritma untuk mencari lintasan terpendek diantaranya dengan algoritma Djikstra, Bellman-Ford, dan Floyd Warshal. Masing-masing memiliki keunggulan dan kelemahan tergantung dari persoalan yang dihadapi. Pengertian dasar dan prinsip kerja secara singkat telah dibahas pada bab sebelumnya, sehingga pada bab ini lebih melihat kepada aspek keunggulan yang mendukung dan kelemahan yang tidak sesuai dengan karakteristik penerbangan domestik dan desain aplikasi yang akan dibuat. Pada penelitian ini langkah yang dilakukan adalah ”memilih algoritma dan mengaplikasikan dengan sedikit penyesuaian terhadap kasus yang dihadapi ” dan tidak melakukan proses algorithm engineering dari awal berupa desain algoritma. Pada ’desain algoritma’ lebih mengarah kepada pembuatan konsep sedangkan ’pemilihan’ hanya menyeleksi algoritma yang telah ada. Meskipun tidak membuat, namun proses atau tahapan yang dikerjakan hampir sama dengan siklus algorithm engineering sebagaimana ditunjukkan gambar 4.1. Algorithm Design
Theoretical Analysis
Algorithm Selection
Algorithm Implemntation
Experimental Analysis
(a)
(b)
Gambar 4.1 (a) Diagram”Algorithm Engineering Cycle” (Sumber : C.Demetrescue,I.Finocchi, dan G.F.Itliano.Algorithm Engineering. The Algorithmic Colum,Buletin of the EACTS,page 63.2003) (b) Tahap Peneitian pada Bab ini (dalam kotak merah)
28
Langkah awal membuat analisis teori mengenai keunggulan dan kelemahan algoritma yang dibandingkan. Setelah itu dipilih algoritma yang memiliki keunggulan sesuai dengan parameter yang telah ditetapkan. Algoritma yang terpilih inilah yang menjadi acuan dasar pembuatan aplikasi di tahap berikutnya. Disebut acuan karena penerapannya juga harus disesuaikan dengan kasus yang diselesaikan, sehingga masih ada kemungkinan untuk membuat sedikit modifikasi dan pengembangan lanjutan. 4.2. Penentuan Parameter Perbandingan Pemilihan Algoritma Penentuan parameter disesuaikan dengan desain aplikasi yang akan dibuat yang mengacu pada tujuan penelitian dan rumusan masalah sebagaimana dijelaskan pada Bab I. Parameter tersebut adalah : 1. Spesifikasi Penyelesaian Masalah Kriteria spesifikasi penyelesaian menyangkut ”spesifikasi karakteristik graf” yang dapat diselesaikan. Karakter tersebut antara lain : •
Weigth edge
•
Node source
•
Node destination
2. Jenis Masalah yang diselesaikan Kriteria ini menyangkut jenis masalah lintasan terpendek yang diselesakan yang merupakan pilihan dari masalah dibawah ini : •
Lintasan terpendek antara dua buah simpul tertentu (a pair shortest path).
•
Lintasan terpendek antara semua pasangan simpul (all pairs shortest path).
•
Lintasan terpendek dari simpul tertentu ke semua simpul yang lain (single- source shortest path).
•
Lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu (intermediate shortest path).
3. Kompleksitas Waktu Running Algoritma Salah satu aspek paling penting dalam algoritma adalah seberapa cepat ia bekerja (running time). Seringkali menjadi suatu yang sangat mudah untuk menggunakan algoritma dalam menyelesaikan suatu masalah, akan tetapi bila proses berkerja algorima berjalan terlalu lambat maka tidak ada bedanya dengan penyelesaian manual. Karena kecepatan yang tepat dari algoritma sangat bergantung pada dimana algoritma tersebut dijalankan, sebagaimana detil secara 29
tepat dari algoritma terhadap implementasinya, para ilmuwan komputer yang secara khusus meneliti masalah ini menyimpulkan bahwa besarnya running time relatif terhadap besar/banyaknya input. Sebagai contoh, bila input terdiri dari N buah integer, algoritma tersebut mungkin memiliki running time yang proporsional terhadap N2, yang direpresentasikan dengan O(N2). Artinya bila kita mencoba menjalankan suatu program implementasi dari suatu algoritma dengan input sebesar N, maka akan membutuhkan waktu C*N2 detik, dimana C adalah konstanta yang tidak berubah relatif terhadap perubahan ukuran input. Bagaimanapun, waktu pelaksanaan dari banyak algoritma kompleks dapat berbeda-beda dalam kaitan dengan faktor selain dari ukuran dari masukan. Sebagai contoh, suatu algoritma penyortiran boleh jadi bekerja jauh lebih cepat ketika satu set diberi bilangan bulat yang telah disortir dibanding ketika diberi satuan bilangan bulat dalam suatu order;pesanan acak. Para pakar informatika memberi contoh hasil kompleksitas running time algoritma secara umum sebagai berikut (dengan asumsi N=100): O(Log(N))
10-7 detik
O(N)
10 detik
O(N*Log(N))
10-5 detik
-6
2
-4
O(N )
10 detik
O(N6)
3 menit
N
O(2 )
10
14
O(N!)
10
142
tahun tahun
Tabel 4.1. Contoh running time algoritma tertentu dengan N=100 (Sumber : Ibackstrom.”The Importance of Algorithms”,topcoder.com.2007)
Namun untuk efektifitas dan kemudiahan penelitian running time yang akan dibandingkan adalah running time dari literatur yang telah banyak digunakan oleh para insinyur informatika. 4.3. Pemilihan Algoritma Masalah Lintasan Terpendek Berdasarkan perbandingan langsung dari uraian teoritik tiga buah algoritma yang diusulkan dalam bab II (Studi Literatur) yaitu : a. Algoritma Djikstra
30
b. Algoritma Bellman-Ford c. Algoritma Floyd-Warshal Dan dengan menggunakan parameter pembanding di sub bab 4.2, maka dapat dibuat tabel perbandingan sebagai berikut : Kriteria
Djikstra
Bellman-Ford
Floyd-Warshal
Spesifikasi
•
•
•
penyelesaian masalah
•
Efektif untuk graf
penyelesaian masalah
bobot positif/negatif
Untuk kasus graf
mirip dengan Djikstra
namun tidak dapat
Hanya digunakan
menghitung siklus
negatif, Djikstra dapat
untuk menyelesaikan
negatif
menghitung dengan
kasus graf berbobot
kecepatan lebih baik
negatif
terkecil dari semua
Untuk graf berbobot
jalur yang
Tidak dapat
negatif running time
menghubungkan
menghitung graf yang
lebih baik dari
pasangan titik dan
berbobot negatif
Djikstra
melakukannya
dari Belman-Ford
•
Dapat menghitung
berbobot positif
dengan bobot tak-
•
Struktur dasar
•
•
•
Menghitung bobot
Hasil perhitungan
sekaligus untuk
belum tentu optimal
pasangan titik
•
(bergantung pada kasus
Menggunakan pemrograman
yang dihadapi)
dinamik Jenis masalah
Single-source shortest path
Single-source shortest path
All-pairs shortest path
O((V+E)logV)
O(V.E)
O(V3)
yang diselesaikan Running Time
Tabel 4.2. Tabel Perbandingan antar Algoritma
Berdasarkan tabel perbandingan tersebut dapat diambil kesimpulan bahwa : 1. Ketiganya dapat menyelesaikan menyelesaikan masalah lintasan terpendek, namun untuk kasus graf dengan bobot yang selalu positif algoritma djikstra lebih efektif dan lebih cepat, sedang algoritma Bellman-Ford dan Floyd-Warshal unggul di penyelesaian graf dengan bobot negatif. 2. Berdasarkan urutan waktu penyelesaian dengan memasukkan data sebarang pada rumus diatas diperoleh urutan algoritma dari yang tercepat adalah : O(V.E) < O((E+V)logV) < O(V3) = Bellman-Ford < Dijkstra < Floyd-Warshall 31
3. Berdasarkan masalah yang dapat diselesaikan.: Algoritma Dijkstra untuk masalah Single-source Shortest Path, Algoritma BellmanFord untuk masalah Single-source Shortest Path, Algoritma Floyd-Warshall untuk masalah All-pairs Shortest Path Berdasarkan batasan masalah yang diberikan dan karakteristik jaringan penerbangan domestik di Indonesia didapatkan karakteristik graf yang akan diselesaikan adalah sebagai berikut : a) Mempunyai satu simpul pemasok/sumber dan satu simpul penampung/tujuan dengan rute perjalanan melalui beberapa simpul perantara b) Kapasitas busur disini yang diperhitungkan berupa waktu tempuh perjalanan (minimum total trip time) atau harga tiket penerbangan pada kelas termurah (minimum total trip cost). c) Harga kapasitas busur selalu positif. Maka algoritma yang masih memungkinkan adalah algoritma DJIKSTRA dan FLOYD WARSHAL. Sebenarnya jika melihat pada kriteria (a) maka yang paling cocok adalah algoritma Floyd Warshall, namun Djikstra juga bisa diterapkan untuk mencari pasangan simpul tertentu yang ditentukan. Tahap selanjutnya adalah memilih diantara dua algoritma tersebut berdasarkan kesesuaian dengan kasus yang dihadapi dan implementasinya. 4.4. Analisis Perbandingan Algoritma Penyelesaian Masalah Lintasan Terpendek pada Kasus Jaringan Penerbangan Domestik 4.4.1 Algoritma Djikstra Input algoritma ini adalah sebuah graf berarah dan berbobot, G dan sebuah source vertex s dalam G. V adalah himpunan semua simpul dalam graph G. Setiap sisi dari graph ini adalah pasangan vertices (u,v) yang melambangkan hubungan dari vertex u ke vertex v. Himpunan semua edge disebut E. Weights dari edges dihitung dengan fungsi w: E → [0, ∞); jadi w(u,v) adalah jarak non-negatif dari vertex u ke vertex v. Cost dari sebuah edge dapat dianggap sebagai ’jarak’ antara dua vertex, yaitu jumlah jarak semua edge dalam path tersebut. Untuk sepasang vertex s dan t dalam V, algoritma ini menghitung jarak terpendek dari s ke t. 4.4.1.1 Intuisi dasar dalam Algoritma Djikstra •
Pada Setiap langkah dalam algoritma : 32
¾ Semua lintasan terpendek yang diketahui simpul-simpulnya masukkan dalam { S } ¾ Simpan dalam C[K] , jarak dengan lintasan terpendek dalam node K {S}
(untuk semua lintasan yang melalui node dalam {S}) ¾ Tambahkan ke {S} node terdekat selanjutnya •
Gambar 4.2
Perbarui jarak ke J setelah menambahkan node K ¾ Lintasan terpendek sebelumnya disiagakan dalam C[K] ¾ Cari kemungkinan lintasan lebih pendek dengan menghitung yang melalui node K ¾ Bandingkan besar C[J] dengan
Gambar 4.3
C[K] + bobot (K,J) (Sumber : Emad Fauzi, Tseng Chau-Wen. Graphs & Graphs Algorithm 2. Departement of Computer Science, Maryland University,USA) 4.4.1.2 Konsep Langkah Penyelesaian Djikstra Sebagai contoh kasus dimisalkan diketahui jaringan penerbangan antar kota yang disimbulkan dengan angka 1,2,3,4 dan 5 seperti gambar berikut. Angka dalam lingkaran menunjukkan kota-kota sedangkan angka di tepi garis menunjukkan ”jarak” yang dapat mewakili waktu tempuh yang diperlukan untuk penerbangan antara dua kota yang dihubungkan atau biaya perjalanan yang dibutuhkan. Kemudian akan kita cari lintasan terpendek yang menghubungkan kota 1 ke kota 5.
5
2
1
10 4
1 8
3
9
5
3
Gambar 4.4 Contoh Jaringan Sederhana
33
Maka algoritma dasarnya adalah: { S } = Ø ; C[X] = 0 ; C[Y] = ∞ untuk semua node yang lain while ( bukan semua node dalam { S } ) find node K not in { S } dengan C[K] terkecil tambahkan K ke dalam { S } for tiap node M tidak dalam { S } yang berdekatan dengan K C[M] = min ( C[M] , C[K] + cost of (K,M) ) Penghitungan untuk memperoleh hasil optimal ini menggunakan prinsip dasar strategi greedy. Penyelesaian langkah per langkah diilustrasikan dengan penjelasan berikut ini : Dimisalkan : {S} adalah himpunan simpul yang jarak terdekatnya telah diketahui C[K} adalah kapasitas busur yang menunjukkan waktu tempuh pada simpul tertentu dari simpul pemasok dimana harga C[K] = 0, menunjukkan simpul pemasok C[K] = ∞, menunjukkan tidak ada busur yang terhubungkan secara langsung dari simpul tersebut ke simpul pemasok. Untuk menyelesaikan masalah tersebut dilakukan langkah-langkah sebagai berikut : 0 5
2
8
4
9
1
1
5
8
3
3
5
5
9
8
5
5 4
5
9
8
1 8
3
4 3
9
2
3
4
5
9
3
8
3
5
10
1
1
5
3
3
6 5
5
9
10 1
1
3
3
10 1
4
3 2
5 2
10 1
1
3
3
10 1
8
4
2
2
5
4
2
1
1
10
10 1
1
2
5
4 3
9
5
2
7 10
1
1 8
3
4
9
5
3
34
9 2
5
8
3
5
10 1
1
8
4
2 1
1
5
9
8
3
10 4
9
5
3
3
1 5
2
10 1
1 8
4
5
9
3
3
Gambar 4.5 Langkah penyelesaian algoritma Djikstra
Langkah 0 - Tahap inisiasi {S}=Ø
2
5
C[1] = 0
1
1
C[2] = ∞ C[3] = ∞
8
4
5
9
3
3
C[4] = ∞ C[5] = ∞
10
Gambar 4.6 – Tahap Inisiasi Djikstra
Langkah 1 – Memasukkan simpul K yang dipilih sebagai simpul sumber dan memasukkannya ke himpunan simpul yang di perhitungkan {S} {S}=1 5
C[1] = 0 C[2] = ∞
2
10
1
1
4
C[3] = ∞ C[4] = ∞ C[5] = ∞
8
3
9
5
3
Gambar 4.7 – Tahap identifikasi simpul sumberalgoritma Djikstra
Langkah 2 – Memperbarui C[K] untuk semua simpul terdekat dari simpul 1 yang tidak ada dalam {S} {S}=1 35
C[1] = 0 C[2] = 5 C[4] = ∞
2
5
C[3] = 8
10
1
1
4
5
9
C[5] = ∞ 8
3
3
C[2] = min (∞ , 0 [2] = min (∞ , C[1] + (1+ 5) = 5 C[3] = min (∞ , C[1] + (1,3) ) = min (∞ , 0 + 8) = 8 Gambar 4.8 – Langkah ke-2 Djikstra (Pencarian simpul terdekat)
Langkah 3 – Memilih simpul K terpilih dengan jarak terdekat dari simpul 1 dan ditambahkan ke {S} { S } = 1, 2
2
5
C[1] = 0
1
1
C[2] = 5 C[3] = 8
8
4
5
9
3
3
C[4] = ∞ C[5] = ∞
10
Gambar 4.9 – Langkah ke-3 Djikstra (Memilih simpul yang terdekat)
Langkah 4 - Memperbarui C[K] untuk semua simpul terdekat dari simpul 2 yang tidak ada dalam {S}
2
5
{ S } = 1, 2 C[1] = 0
1
1
C[2] = 5
8
C[3] = 6
10
4
5
9
3
3
C[4] = 15 C[5] = ∞
C[3] = min (8 , C[2] + (2,3) ) = min (8 , 5 + 1) = 6 C[4] = min (∞ , C[2] + (2,4) ) = min (∞ , 5 + 10) = 15
Gambar 4.10 – Langkah ke-4 Djikstra (Memperbarui C[K] pada simpul terdekat dari simpul terpilih)
Langkah 5 – Memilih simpul K terpilih dengan jarak C[K} terdekat dan ditambahkan ke {S} { S } = 1, 2, 3 C[1] = 0 C[2] = 5 C[3] = 6
5
2
10
1
1 8
3
4
9
5
3 36
C[4] = 15 C[5] = ∞
Gambar 4.11 - Langkah ke-5 Djikstra (Memilih simpul K terpilih yang terdekat)
Langkah 6 - Memperbarui C[K] untuk semua simpul terdekat dari simpul 3 yang tidak ada dalam {S} { S } = 1, 2, 3
2
5
C[1] = 0
1
1
C[2] = 5 C[3] = 6
8
4
5
9
3
3
C[4] = 9 C[5] = ∞
10
C[4] = min (15 , C[3] + (3,4) ) = min (15 , 6 + 3) = 9 Gambar 4.12 - Langkah ke-6 Djikstra
Langkah 7– Memilih simpul K terpilih dengan jarak C[K} terdekat dan dimasukkan ke {S} { S } = 1, 2, 3, 4 5
C[1] = 0 C[2] = 5
2
10
1
1
4
C[3] = 6 8
C[4] = 9 C[5] = ∞
3
9
5
3
Gambar 4.13 - Langkah ke-7 Djikstra
Langkah 8 - Memperbarui C[K] untuk semua simpul terdekat dari simpul 4 yang tidak ada dalam {S}
5
{ S } = 1, 2, 3, 4 C[1] = 0
8
C[3] = 6
10
1
1
C[2] = 5
2
4
9
5
3
3
C[4] = 9
C[5] = min (∞ , C[4] + (4,5) ) = min (∞ , 9 + 9) = 18
C[5] = 18
Gambar 4.14 - Langkah ke-8 Djikstra
Langkah 9 – Memilih simpul K terpilih dengan jarak C[K} terdekat dan dimasukkan ke {S} { S } = 1, 2, 3, 4, 5 C[1] = 0 C[2] = 5 C[3] = 6
5
2
10
1
1 8
3
4
9
5
3
C[4] = 9 37
C[5] = 18
Gambar 4.15 - Langkah ke-9 Djikstra
Langkah 10 – Memastikan bahwa semua simpul dalam {S} telah di hitung { S } = 1, 2, 3, 4, 5
2
5
C[1] = 0 C[2] = 5
1
1
C[3] = 6
8
C[4] = 9 C[5] = 18
10
4
5
9
3
3
Gambar 4.16 - Langkah ke-10 Djikstra
Proses diulang hingga semua simpul masuk ke dalam {S}.
Jadi dari perhitungan tersebut diperoleh bahwa jalur terdekat yang ditempuh untuk menuju simpul 5 dari simpul 1 adalah lintasan 1-2-3-4-5 dengan total jarak = 18 Sejauh ini untuk kasus percobaan lintasan terpendek jaringan penerbangan antar kota secara sederhana, algoritma Dijkstra dapat berhasil menyelesaikan pencarian lintasan terpendek dengan baik. 4.4.1.3 Studi Implementasi Algoritma Djikstra Pada pengujian implementasi algoritma Djikstra ini agar lebih mudah diambilkan dari penggalan graf yang terdapat dalam peta daftar kota tujuan Garuda Indonesia dan Citylink yang terdapat pada Gambar 2.3 dengan komponen ”kapasitas busur” berupa data dummy untuk mempermudah pengamatan dan perhitungan. PNK BPN
1.5
8 BTH
2
3 4
3
SUB
CKG
2
2
2 JOG
DPS 5
6
38
PNK BPN
1.5
8 BTH
2
3 4
3
SUB
CKG
2
2
2 JOG
DPS 5
6
Gambar 4.17 – Contoh implementasi algoritma Djikstra dari kasus subpart gambar 2.3
Dengan data graf sebagaimana gambar diatas apabila dicari rute perjalanan ”terpendek” antara kota Batam ke kota Denpasar dengan menggunakan algoritma Djikstra maka dihasilkan rute BTH – CKG – SUB – DPS dengan total jarak lintasan 9 (ditunjukkan dengan garis busur berwarna merah). Garis graf diatas busur dengan garis putus-putus menunjukkan hasil pencarian path dari source ke setiap vertex dalam graf melalui mekanisme single source shortest path. 4.4.2
Algoritma Floyd-Warshal
4.4.2.1 Intuisi Dasar Algoritma Floyd-Warshall ¾ Memperluas daya jangkau algoritma Berdasarkan pada aliran pencarian ulang yang serupa : -
Dimisalkan Dk [i,j] menandai besarnya ”jarak” pada lintasan terpendek dari i ke j yang mana simpul antaranya adalah suatu subset {1,2,...,k}.
-
Kemudian, Dk[i,j] = min ( Dk-1[i,j], Dk-1[i,k] + Dk-1[k,j] )
¾ Floyd-Warshall All-Pairs shortest paths Menghitung Dk dari Dk-1: Untuk setiap pasangan simpul ( i,j ) di dalam Dk-1, maka diset bahwa nilai Dk[i,j] merupakan harga yang paling minimum dari pilihan berikut ini : o Dk-1[ i,j ] ( alur paling pendek sebelumnya)
o Dk-1[i,k]+ Dk-1[k,j] ( alur paling pendek baru yang mungkin yang mana melalui simpul k)
39
Gunakan hanya simpul-simpul nomor 1,.....,k
i j
Gunakan hanya simpul-simpul dengan nomor 1,.....,k-1
k
Gunakan hanya simpul-simpul dengan nomor 1,.....,k-1
Gambar 4.18 – Intuisi dasar Floyd-Warshall
Algoritma All-Pairs shortest paths Floyd-Warshall merupakan cara penyelesaian menggunakan pemrograman dinamik sehingga penyelesaian diharapkan bisa lebih optimal karena tidak seperti Algoritma Djikstra bekerja secara serial, Floydwarshall secara paralel mencari lintasan ”terdekat” dari setiap pasangan vertek/simpul dalam graf dengan mencari lintasan alternatif yang melalui simpul antara 1...k dalam graf. Cara ini akan menghasilkan solusi optimal pada setiap subpath/localgraf yang dilalui untuk menghasilkan solusi total yang optimal juga.
Algorithm AllPair(G) {assumes vertices 1,…,n} for all vertex pairs (i,j) if i = j D0[i,i] ← 0 else if (i,j) is an edge in G D0[i,j] ← weight of edge (i,j) else D0[i,j] ← + ∞ for k ← 1 to n do for i ← 1 to n do for j ← 1 to n do Dk[i,j] ← min{Dk-1[i,j], Dk-1[i,k]+Dk-1[k,j]} return Dn
40
4.4.2.2 Langkah Penyelesaian dan Implementasi Algoritma Floyd-Warshall Untuk lebih mempersingkat pembahasan studi implementasi dilakukan langsung pada contoh kasus sebagaimana pada subbab 4.4.1.3. Langkah 0. Inisiasi graf dalam satu set siklus dengan pokok graf berupa lintasan dari simpul sumber menuju simpul penampung(tujuan) yang melalui jumlah simpul antara terbanyak. Bentuk graf pada Gambar 4.17 bisa juga digambarkan sebagai graf sebagai berikut : 6 5 BTH
4
CKG
2
JOG
3
BPN
2
SUB
2
DPS
2
3 8
Gambar 4.19 – Graf untuk implementasilangkah inisiasi Floyd-Warshall
Dari ilustrasi gambar dapat kita ketahui bahwa untuk mendapatkan lintasan ”terpendek” dari Batam (BTH) ke Denpasar (DPS) ada EMPAT pasangan simpul (pairs of vertex) yang menjadi subpath yang mempunyai pilihan lintasan lebih dari satu lintasan. Setiap subpath diatas harus kita cari lintasan” terpendek”nya untuk menghasilkan lintasan terpendek secara total dari BTH ke DPS. Keempat pasangan simpul tersebut adalah : 1. JOG – DPS ( min : JOG - DPS ; JOG – SUB – DPS ) 2. CKG – SUB (min ; CKG – JOG – SUB ; CKG – BPN – SUB ; CKG – SUB) 3. CKG – DPS [min : CKG – DPS ; (min: JOG – DPS)] 4. BTH – SUB [min : BTH – SUB ; (min: CKG – SUB )] Langkah 1. Mencari lintasan terpendek pada subpath 1 untuk mengeliminasi subgraf yang tidak “terpendek” sehingga hanya tertinggal subgraf yang memiliki kemungkinan mempunyai lintasan “terpendek”.
41
Pada lintasan JOG – DPS ( min : JOG - DPS ; JOG – SUB – DPS ) diperoleh lintasan ”terpendek” yaitu JOG – SUB – DPS, sehingga subgraf JOG – DPS dapat kita eliminasi dari graf utama. 6
4
BTH
CKG
2
JOG
3
BPN
2
2
SUB
DPS
2
3 8
Gambar 4.20 – Eliminasi tahap 1
Langkah 2 . Eliminasi pada subpath ke-2 Pada tahap ini kita mencari nilai (min ; CKG – JOG – SUB ; CKG – BPN – SUB) sebagai sebagian solusi lintasan “terpendek” pada subpath CKG – SUB. Dan kita mendapatkan CKG – JOG – SUB sebagai yang “terpendek” sehingga subpath CKG – BPN – SUB kita eliminasi. 6
BTH
4
2
CKG
JOG
2
SUB
2
DPS
3 8
Gambar 4.21 – Eliminasi tahap ke-2
Langkah 3. Eliminasi subpath ke-3 Masih sama dengan tahap sebelumnya untuk subpath CKG – SUB dengan membandingkan lintasan terpendek pada eliminasi sebelumnya dengan lintasan CKG – SUB yang ditempuh langsung tanpa melalui simpul perantara.
42
6
4
BTH
CKG
2
SUB
DPS
3 8
Gambar 4.22 – Eliminasi tahap ke-3
Langkah 4. Eliminasi subpath ke-4 Masih sama dengan tahap sebelumnya untuk subpath BTH – SUB dengan membandingkan lintasan terpendek lintasan C yang ditempuh langsung tanpa melalui simpul perantara dengan lintasan BTH – CKG - SUB. Dan yang lebih pendek adalah lintasan BTH – CKG – SUB, sehingga graf lintasan BTH – SUB kita hapus ari graf utama. 6
4
BTH
CKG
2
SUB
DPS
3
Gambar 4.23 – Eliminasi tahap ke-4
Langkah 5. Eliminasi subpath ke-5 Seperti pada gambar Gambar 4.23 subpath yang masih perlu kita cari lintasan terpendeknya adalah pasangan simpul CKG – DPS. Dari hasil perhitungan penerbangan dari Jakarta (CKG) menuju Denpasar (DPS) yang menggunakan simpul perantara di Surabaya(SUB) lebih pendek daripada penerbangan langsung pada rute tersebut. Jadi subpath/subpgraf CKG – DPS kita hapus dari graf utama. Karena sudah tidak ada lagi pasangan simpul yang terpilih lintasan terpendeknya maka graf tersebut menunjukkan lintasan dengan jarak total dari Batam(BTH) ke Denpasar(DPS) yang ”terpendek”.
BTH
4
CKG
SUB
2
DPS
3
Gambar 4.24 –Solusi final pencarian rute terdekat dari BTH – DPS
43
Berdasarkan hasil penerapan Algoritma Floyd-Warshall diatas, hasil final lintasan ‘terpendek’ yang diperoleh adalah sebesar 9. Nilai ini bila dikaitkan dengan pembahasan solusi optimal total pada Subbab 4.4.1.3 merupakan hasil yang paling optimal karena tidak ada lagi pilihan lintasan untuk pasangan simpul asal – tujuan (BTH – DPS) yang lebih pendek dari 9. Jadi penerapan algoritma Floyd-Warshall bila dibandingkan dengan algoritma Djikstra, solusi lokal pada setiap subpat/subgraf (pasangan semua simpul dalam graf ) menghasilkan nilai yang selalu optimal dan hasil finalnya juga akan selalu yang paling optimal (terpendek). 4.5. Hasil Akhir Pemilihan Algoritma Lintasan Terpendek DJIKSTRA
FLOYD-WARSHALL
Spesialis single source shortest path dan Spesifik untuk kasus all-pairs shortest path ( bisa
juga
destination
untuk
single
shortest
source-single semua lintasan terpendek masing-masing
path
dengan antara tiap kemungkinan pasang kota yang
penambahan parameter destination node Intuisi
pencarian
dari
berbeda )
vertex/simpul Intuisi pencarian dengan mencari dan
tetangga terdekat dengan himpunan bagian membandingkan vertex S
path
alternatif
yang
melalui simpul antara (1, ... , k )
Pada satu kali running program bisa Pada satu proses pencarian bisa langsung mengetahui lintasan terpendek dari satu kota diketahui lintasan terpendek setiap pasangan ke kota lainnya di dalam graf
vertex di dalam graf
Dari hasil analisis perbandingan diatas dapat diambil kesimpulan bahwa Algoritma FloydWarshall lebih cocok dipakai untuk penyelesaan masalah lintasan terpendek pada kasus penerbangan domestik.
44
Algoritma yang diusulkan : 1. Djikstra 2. Bellman-Ford 3. Floyd-Warshall Analisis Teori
Algoritma tersaring : ¾ Djikstra ¾ Floyd-Warshall Analisis Implementasi
Algoritma terpilih : Floyd-Warshall
Gambar 4.25 – Rangkuman Seleksi Algoritma Shortest Path
45
