BAB II STUDI LITERATUR Pada bab ini dijelaskan mengenai sistem informasi jadwal penerbangan yang ada saat ini termasuk didalamnya sumber informasi lainnya yang biasa diakses calon penumpang, gambaran umum kebutuhan akan informasi penerbangan, perkembangan pemanfaatan sistem jaringan kerja sebagai metoda untuk mencari “lintasan terpendek”, perbandingan antar metoda dan kriteria-kriteria yang diperlukan dalam memilih metoda yang akan dikembangkan. Studi dilakukan dengan melakukan pengamatan langsung di lapangan dan melalui literature tertulis yang di dapatkan dari internet, makalah, buku, koran dan flyer/ brochure maskapai penerbangan.
2.1 Sumber Informasi Jadwal Penerbangan Komersial Setiap maskapai penerbangan pada dasarnya memiliki strategi yang berbeda-beda untuk memasarkan jasanya. Cara yang paling umum adalah melalui agen penjulan di setiap bandara dan kerjasama keagenan dengan travel agent di berbagai kota. Strategi ini cukup efektif untuk mengenalkan maskapai penerbangan dan layanannya kepada masyarakat mengingat masyarakat dapat menggali informasi secara langsung dengan datang sendiri ke kantor-kantor agen di kotanya. Ada juga yang lebih cenderung memperbanyak iklan/promo di media massa seperti koran dan televisi. Dan yang terakhir melalui media home page dan online ticketing melalui internet maupun mobile phone.
Gambar 2.1 Home Page Garuda Indonesia Sumber : www.garuda-indonesia.co.id
7
2.2 Kebutuhan Sumber Informasi bagi Calon Penumpang Seiring perkembangan gaya hidup masyarakat yang semakin modern dan dinamis, akses informasi yang lengkap dan akurat menjadi sebuah keharusan. Karakter modern tercermin dalam pemanfaatan sumber informasi yang canggih dan semakin dekat secara personal kepada konsumen seperti akses online ticketing melalui internet dari rumah atau hand phone/PDA. Sedangkan aspek dinamis masyarakt saat ini dapat terlihat dari mobilitas masyarakat yang luas menjangkau berbagai wilayah di tanah air. Maka wajar pengembangan website maskapai penerbangan menjadi salah satu prioritas layanan kepada calon penumpang.
Informasi tambahan Tentang perusahaan dan layanan
konsumen
Informasi Utama tentang Penerbangan (Fligh Info)
Gambar 2.2 – Fitur Layanan Website Garuda Indonesia Sumber : www.garuda-indonesia.co.id
Dari sekian maskapai penulis memilih PT. Garuda Indonesia sebagai acuan literasi karena memiliki kualitas dan layanan yang lebih baik. Seperti terlihat pada Gambar 2.2, informasi yang diberikan terbagi dalam dua kelompok utama, pertama adalah mengenai profil perusahaan beserta keunggulan yang ditawarkan dan kedua adalah informasi khusus mengenai jadwal penerbangan. Pada kelompok pertama lebih merupakan kebijakan masing-masing maskapai bagaimana mereka berusaha membangun image dan kepercayaan bagi para calon penumpang. Yang lebih menjadi fokus pada
8
penelitian ini adalah pada pelayanan informasi jadwal penerbangan. Mayoritas website memberikan informasi utama berupa : 1. Fligh Schedule terdiri dari Departure & Arrival Schedule 2. Fare atau informasi harga tiket Pada beberapa maskapai ada yang ditambah dengan destination map seperti milik Garuda Indonesia dan fasilitas online booking seperti milik AirAsia Indonesia dan Adam Air. Secara umum informasi tentang jadwal penerbangan dari website cukup lengkap dan memadai namun berdasarkan hasil pengamatan, penulis menemukan beberapa kelemahan yang belum bisa dipenuhi oleh suatu airline website. Para calon penumpang sudah bisa memilih jadwal yang dikehendaki pada daftar yang diberikan begitu juga dengan pilihan daftar kota-kota tujuan yang dilayani,akan tetapi pilihan hanya terbatas pada satu maskapai, dan ketika ingin mencari alternatif jadwal dari maskapai lain harus berganti ke websaite maskapai yang lain. Yang kedua, ketika calon penumpang ingin menempuh perjalanan antara kota asal dan kota tujuan yang tidak terhubung langsung, maka mereka harus mencari jalur alternatif yang memungkinkan untuk menghubungkan kota asal dan tujuan. Sebagai contoh penulis mengambil ilustrasi dari destination map Garuda Indonesia seperti pada Gambar 2.3.
Gambar 2.3 – Peta Daftar Kota Tujuan Penerbangan Garuda Indonesia Sumber : www.garuda-indonesia.co.id
9
Misalkan calon penumpang ingin menempuh penerbangan dari kota Pontianak ke Balikpapan. Karena antara kedua kota tersebut tidak ada penerbangan langsung, maka harus dicari jalur transit yang dapat menghubungkannya. Pada kasus penerbangan Pontianak – Balikpapan alternatif yang bisa dipilih adalah : 1. Dari Pontianak terbang dengan Citilink ke Jakarta, kemudian terbang ke Balikpapan dengan Garuda. 2. Dari Pontianak terbang dengan Citilink ke Jakarta, kemudian naik Garuda ke Surabaya dahulu, kemudian naik Citilink ke Surabaya , dan baru dari Surabaya terbang dengan Citilink juga ke Balikpapan 3. Dari Pontianak terbang dengan Citilink ke Jakarta, kemudian naik Garuda ke Surabaya dahulu, kemudian naik Garuda ke Surabaya , dan baru dari Surabaya terbang dengan Citilink juga ke Balikpapan Persoalan pemilihan jalur alternatif diatas akan semakin rumit bila kita dihadapkan pada tuntutan untuk memilih pilihan jalur yang paling cepat sampai di kota tujuan atau jalur yang menghasilkan total biaya perjalanan yang termurah. Belum lagi bila alternatif pilihan diatas kita tambah dengan jadwal dari maskapai selain Garuda, misalnya saja antara Jakarta – Surabaya dilayani oleh 10 maskapai, Jakarta – Balikpapan 5 maskapai, dan Surabaya – Balikpapan ada 3 maskapai tentu kemungkinannya akan menjadi lebih banyak dan membutuhkan lebih banyak waktu untuk memilih sesuai dengan yang kita kehendaki. Perhitungan dan pemilihan alternatif jalur penerbangan yang tidak terhubung langsung seperti diatas tentu tidak praktis dengan mengandalkan sumber informasi yang parsial karena setiap maskapai tentu ingin agar calon penumpang memilih mereka untuk terbang dan mengabaikan yang lain. Perhitungan yang lebih praktis tentu haruslah dengan satu aplikasi yang sudah mencakup semua maskapai penerbangan dan dapat membantu perhitungan pemilihan jalur penerbangan yang tercepat atau termurah secara otomatis. Hanya saja karena aplikasi tersebut untuk saat ini belum ada, penulis memutuskan untuk mengawalinya dengan meneliti metoda pemecahan pemilihan jalur tercepat atau termurah tersebut.
10
2.3 Pemanfaatan Metoda Jaringan Kerja Persoalan transportasi udara yang secara visual dapat kita pada Gambar 2.3 diatas dapat kita pandang sebagai suatu sistem kerja yang terdiri dari berbagai kota tujuan penerbangan sebagai simpul dan rute penerbangan sebagai garis penghubung/graf yang disebut ”busur”. Pola hubungan antara simpul dan busur tersebut dapat kita pandang sebagai sebuah jaringan kerja. Jaringan kerja muncul pada sejumlah perencanaan dan dalam berbagai bidang. Jaringan transportasi, listrik dan komunikasi merupakan sesuatu yang kita jumpai sehari-hari. Penggambaran jaringan kerja juga digunakan secara luas untuk masalah-masalah seperti produksi, distribusi, perencanaan proyek, penempatan fasilitas, menajemen sumberdaya, perencanaan keuangan dan sebagainya. Sesungguhnya penggambaran jaringan kerja menyediakan bantuan secara visual dan konseptual yang sangat berharga dalam menggambarkan hubungan antara komponen-komponen dalam suatu sistem. Sebelum membahas lebih jauh tentang jaringan kerja, berikut ini penjelasan singkat mengenai jaringan kerja. Analogi peristilahan dalam jaringan kerja yang sering dipakai dalam perencanaan operasi adalah seperti tabel dibawah ini : Simpul
Busur
Arus
Persiapan jalan
Jalan
Kendaraan
Bandar udara
Jalur penerbangan
Kapal terbang
Titik pergantian
Kabel,saluran
Pesan
Stasiun pompa
Pipa
Cairan
Pusat kerja
Rute pengiriman material
Pekerjaan
Tabel 2.1 – Tabel Perbandingan Penggunaan Peristilahan dalam Jaringan Kerja A
4
3
8
D
2
4
6
O
B
1 5
T
7
1 4 C
E
Gambar 2.4 – Contoh suatu jaringan kerja
11
Suatu jaringan kerja terdiri atas suatu gugus titik dan garis yang menghubungkan pasangan titik tertentu. Titik-titik tersebut dinamakan simpul (node/vertices; sebagai contoh jaringan kerja dalam gambar 2.4 memiliki 7 buah simpul yang digambarkan dengan lingkaran . Garis-garis yang menghubungkan simpul-simpul tersebut dinamakan busur (arcs/links/edge/branch). Arah arus tersebut ditunjukkan dengan menambahkan ujung panah pada akhir garis yang menggambarkan busur. Dalam melambangkan suatu busur berarah dengan cara mencantumkan dua simpul yang dihubungkan , simpul asal harus dituliskan di depan; misalnya suatu busur berarah dari A ke B harus dilambangkan AB bukannya BA. Busur ini bisa juga dilambangkan dengan A Æ B. Jumlah arus terbesar (mungkin tak hingga) yang dapat dibawa dalam suatu busur berarah dinamakan sebagai kapasitas busur. Untuk simpul, dilakukan pembedaan antara simpul yang merupakan pembangkit arus bersih, penyerap arus bersih, atau tidak keduanya. Suatu simpul pemasok (supply node) atau kadang disebut sebagai simpul sumber atau sumber saja, mimiliki sifat bahwa arus yang mengalir keluar dari simpul tersebut melebihi arus yang masuk kedalam simpul tersebut. Sebaliknya simpul dimana aliran yang masuk melebihi arus yang keluar disebut sebagai simpul penampung (demand node). Suatu simpul perantara (transshipment node) atau simpul intermediate memenuhi sifat arus yang masuk ke dalam simpul sama dengan yang keluar dari simpul. Metode penerapan jaringan kerja yang sering dipakai dalam manajemen operasi adalah : 1. Masalah lintasan terpendek (shortest path problem) Metode shortest path digunakan untuk menyelesaikan permasalahan transportasi yang menghubungkan dua buah simpul yang tidak terhubungkan secara langsung namun berada dalam satu jaringan yang saling terhubungkan (undirected and connected network). Setiap simpul dalam jaringan dihubungkan oleh busur yang memiliki arus tertentu (jarak,waktu,biaya). Simpul utama yang menjadi acuan adalah simpul dimana proses dimulai atau origin node dan simpul tujuan terakhir yang dikehendaki atau destination node. Inti permasalahannya
12
adalah bagaimana menemukan lintasan yang terpendek antara simpul origin ke destination. 2. Masalah jangkauan pohon minimum (minimum spanning tree problems) Metode minimum spanning tree masih merupakan penyelesaian kasus ”lintasan terpendek” pada jaringan undirected dan connected namun dengan penerapan yang berbeda. Pada masalah shortest path yang dicari adalah lintasan terpendek antara simpul origin dan destination, sedangkan minimum spanning tree memilih satu set lintasan yang memiliki shortest total length diantara semua lintasan yang menghubungkan semua simpul dalam jaringan. 3. Masalah arus maksimum (maximum flow problem) Adalah metode penyelesaian jaringan undirected dan connected yang semua lintasan diawali dari satu titik asal disebut sumber/source dan berkhir pada satu titik juga disebut titik penampung/sink. Semua titik yang dilalui disebut sebagai transhipment nodes. Perhitungan properti dari arus pada setiap lintasan menggunakan batasan kapasitas maksimal yang dapat dilalui, misalnya untuk kasus penerbangan dibatasi biaya maksimum pada setiap lintasan yang dipilih adalah Rp. 1.000.000,00. 4. Masalah arus biaya minimum (minimum cost flow problem) Hampir sama dengan penyelesaian masalah maximum flow, hanya saja pembatasan kapasitas berharga minimum yang difokuskan pada perhitungan biaya. Metode ini dapat menyelesaikan kasus jaringan dengan multiple source (supply nodes) dan multiple destinations (demand nodes). Dari keempat metode penyelesaian masalahjaringan, yang dapat memenuhi persyaratan kasus transportasi udara sebagaimana sub bab 2.2 adalah masalah lintasan terpendek (shortest path problem). Pertimbangannya adalah terdapat satu simpul asal dan tujuan dalam jaringan undirected dan connected dengan kapasitas busur berupa waktu tercepat dan biaya termurah.
13
2.4 Metoda Pemilihan Lintasan Terpendek 2.4.1. Definisi Lintasan Terpendek Lintasan terperndek adalah lintasan minimum yang diperlukan untuk mencapai suatu empat dari tempat tertentu. Lintasan minimum yang dimaksud dapat dicari dengan menggunakan graf. Graf yang digunakan adalah graf yang berbobot, yaitu graf yang setiap sisinya diberikan suatu nilai atau bobot. Dalam kasus penelitian ini , bobot yang dimaksud berupa waktu tempuh atau harga tiket. 2.4.2. Macam-macam Tipe Masalah Lintasan Terpendek Secara umum ada beberapa tipe masalah lintasan terpendek, antara lain : a. Lintasan terpendek antara dua buah simpul tertentu (a pair shortest path). b. Lintasan terpendek antara semua pasangan simpul (all pairs shortest path). c. Lintasan terpendek dari simpul tertentu ke semua simpul yang lain (singlesource shortest path). d. Lintasan terpendek antara dua buah simpul yang melalui beberapa
simpul
tertentu (intermediate shortest path).
2.4.3. Strategi Greedy untuk Pemecahan Masalah Lintasan Terpendek 2.4.3.1. Definisi Strategi Greedy Strategi greedy adalah strategi yang memecahkan masalah langkah demi langkah, pada setiap langkah, adapun urutan langkah strategi Greedy adalah : 1. Mengambil pilihan yang terbaik yang dapat diperoleh saat itu 2. Berharap bahwa dengan memilih solusi optimum lokal, pada setiap langkah akan mencapai solusi optimum global. Strategi greedy mengasumsikan bahwa optimum lokal menyusun solusi optimum global. Prinsip strategi greedy adalah: “take what you can get now!”. Ambil apa yang anda peroleh sekarang! Prinsip ini juga dipakai dalam pemecahan masalah optimasi. Dalam kehidupan sehari-hari, kita juga pernah menggunakan prinsip greedy, misalnya: a. Memilih jurusan di Perguruan Tinggi b. Memilih jalur tersingkat dari Bandung ke Jakarta.
14
2.4.3.2. Skema Umum Strategi Greedy Persoalan optimasi dalam konteks strategi greedy disusun oleh elemen-elemen sebagai berikut: 1. Himpunan kandidat, C. Himpunan ini berisi elemen-elemen pembentuk solusi. Pada setiap langkah, satu buah kandidat diambil dari himpunannya. 2. Himpunan solusi, S. Merupakan himpunan dari kandidat-kandidat yang terpilih sebagai solusi persoalan. Himpunan solusi adalah himpunan bagian dari himpunan kandidat. 3. Fungsi seleksi – dinyatakan sebagai predikat SELEKSI – Merupakan fungsi yang pada setiap langkah memilih kandidat yang paling mungkin untuk mendapatkan solusi optimal. Kandidat yang sudah dipilih pada suatu langkah tidak pernah dipertimbangkan lagi pada langkah selanjutnya. 4. Fungsi kelayakan (feasible)–dinyatakan dengan predikat LAYAK– Merupakan fungsi yang memeriksa apakah suatu kandidat yang telah dipilih dapat memberikan solusi yang layak, yakni kandidat tersebut bersama-sama dengan himpunan solusi yang sudah terbentuk tidak melanggar aturan yang ada. 5. Fungsi obyektif, merupakan fungsi yang memaksimumkan atau meminimumkan nilai solusi. Dalam strategi ini, kita berharap optimum global merupakan solusi optimum dari persoalan. Namun, adakalanya optimum global belum tentu merupakan solusi optimum (terbaik), tetapi dapat merupakan solusi sub-optimum atau pseudo-optimum. Hal ini dapat dijelaskan dari dua faktor berikut: 1) Strategi greedy tidak beroperasi secara menyeluruh terhadap semua alternatif solusi yang ada. 2) Pemilihan fungsi SELEKSI: fungsi SELEKSI biasanya didasarkan pada fungsi obyektif (fungsi SELEKSI bisa saja identik dengan fungsi obyektif). Jika fungsi SELEKSI tidak identik dengan fungsi obyektif, kita harus memilih fungsi yang tepat untuk menghasilkan nilai yang optimum.
15
Karena itu, pada sebagian masalah strategi Greedy tidak selalu berhasil memberikan solusi yang benar-benar optimum. Tetapi, strategi greedy pasti memberikan solusi yang mendekati (approximation) nilai optimum.
2.4.4. Algoritma Penyelesaian Masalah Lintasan Terpendek Algoritma untuk masalah Lintasan Terpendek secara garis besar adalah sebagai berikut : •
Tujuan dari iterasi ke –n : Menentuakan simpul yang menduduki urutan ke-n dalam jaraknya terhadap simpul asal (yang akan diulang untuk n=1,2,3,... sampai simpul yang menduduki tempat ke-n tersebut adalah simpul tujuan).
•
Masukan bagi iterasi ke-n : Simpul terdekat ke (n-1) dalam jaraknya terhadap simpul asal (didapatkan dari iterasi sebelumnya), termasuk lintasan terpendeknya dan jaraknya terhadap simpul asal. (simpul yang termasuk dalam lintasan ini disebut sebagai simpul terselesaikan, sedangkan yang lainnya disebut sebagai simpul tak terselesaikan. Simpul asal selalu merupakan simpul terselesaikan).
•
Calon untuk simpul terdekat ke-n : Setiap terselesaikan yang secara langsung terhubungkan dengan link menuju satu atau lebih simpul tak terselesaikan akan memberikan satu calon – suatu simpul tak terselesaikan dengan busur tak berarah terpendek. (jarak sama akan memberikan calon tambahan).
•
Perhitungan untuk simpul terdekat ke-n : Untuk setiap simpul terselesaikan dan calonnya, jumlahkan jarak keduanya dan jarak lintasan terpendek antara titik asal dengan simpul terselesaikan ini. Suatu calon dengan jumlah jarak terpendek akan merupakan simpul terdekat ke-n (jarak sama memberikan tambahan simpul terselesaikan), dan lintasan terpendeknya yang membangkitkan jarak ini. Suatu solusi untuk pemecahan masalah lintasan terpendek seringkali disebut
sebagai pathing algorithm atau algoritma lintasan.. Beberapa metode algoritma yang utama dan sering dipakai untuk menyelesaikan masalah tersebut antara lain adalah : 1. Algoritma Djikstra 2. Algoritma Bellman-Ford 3. Algorithm Floyd-Warshall
16
1) Algoritma Djikstra Algoritma Dijkstra, dinamai menurut penemunya, Edsger Dijkstra, adalah algoritma dengan prinsip greedy yang memecahkan masalah lintasan terpendek untuk sebuah graf berarah dengan bobot sisi yang tidak negatif. Misalnya, bila simpul dari sebuah graph melambangkan kota-kota dan bobot tiap simpul melambangkan jarak antara kota-kota tersebut, algoritma Dijkstra dapat digunakan untuk menemukan jarak terpendek antara dua kota. 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. a) Deskripsi Algoritma Dijkstra melibatkan pemasangan label pada verteks. Kita misalkan L(v) menyatakan label dari verteks v. Pada setiap pembahasan, beberapa verteks mempunyai label sementara dan yang lain mempunyai label tetap. Kita misalkan T menyatakan himpunan verteks yang mempunyai label sementara. Dalam menggambarkan algoritma tersebut, kita akan melingkari verteks-verteks yang mempunyai label tetap. Selanjutnya akan kita tunjukkan bahwa jika L(v) adalah label tetap dari verteks v, maka L(v) merupakan panjang lintasan terpendek dari a ke v. Sebelumnya semua verteks mempunyai label sementara. Setiap iterasi dari algoritma tersebut mengubah status satu label dari sementara ke tetap; sehingga kita dapat mengakhiri algoritma tersebut jika z menerima sebuah label tetap. Pada bagian ini L(z) merupakan panjang lintasan terpendek dari a ke z.
17
b) Algoritma Algoritma ini mencari panjang lintasan terpendek dari verteks a ke z dalam sebuah graf berbobot tersambung. Bobot dari rusuk (i,j) adalah w(i,j)>0 dan label verteks x adalah L(x). Hasilnya, L(z) merupakan panjang lintasan terpendek dari a ke z. Masukan : Sebuah graf berbobot tersambung dengan bobot positif. Verteks a sampai z. Keluaran : L(z), panjang lintasan terpendek dari a ke z. procedure dijkstra (w,a,z,L) L(a) := 0 for semua verteks x ≠⎯a do L(x) := ∞ T := himpunan semua verteks // T adalah himpunan verteks yang panjang terpendeknya dari a belum ditemukan while z Є T do begin pilih v Є T dengan minimum L(v) T:=T-{v} for setiap x Є T di samping v do
Sumber : Dobson, Simon. (2005). Weighted graphs and shortest paths.UCD School of Computer Science and Informatics. Dublin c) Kompleksitas waktu algoritma (Running time) Algoritma Dijkstra'menggunakan waktu sebesar O(V*log V + E) di mana V dan E adalah banyaknya sisi dan titik.
2) Algoritma Bellman-Ford Algoritma Bellman-Ford menghitung jarak terpendek (dari satu sumber) pada sebuah digraph berbobot. Maksudnya dari satu sumber ialah bahwa ia menghitung semua jarak terpendek yang berawal dari satu titik node. Algoritma Dijkstra dapat lebih cepat mencari hal yang sama dengan syarat tidak ada sisi (edge) yang berbobot negatif. Maka Algoritma Bellman-Ford hanya digunakan jika ada sisi berbobot negatif.
18
a) Deskripsi Kebenaran dari algoritma Bellman-Ford dapat ditunjukkan dengan induksi sebagai berikut: Lemma. Setelah pengulangan i dari siklus for: +
Jika
Distance(u)
terhingga,
akan
sebanding
dengan panjang dari beberpapa lintasan dari s menuju u; +
Jika terdapat lintasan dari s menuju u pada kebanyakan sisi i , kemudian Distance(u) adalah kebanyakan panjang pada lintasan terpendek dari s menuju u dengan kebanyakan sisi i.
Bukti. Untuk setiap dasar induksi, perhatikan i=0 dan saat kejadian sebelum siklus for yang dieksekusi pertama kali. Kemudian, untuk setiap simpul asal, source.jarak = 0, adalah benart. Untuk setiap simpul u, lainnya u.jarak = tak terhingga, juga benar karena tidak terdapat dari simpul asal ke simpul u dengan sisi berbobot 0. Untuk kasus induktif, pertama kali kita membuktikan bagian awal. Bayangkan saat jarak setiap simpul diperbarui sebagai berikut v.jarak := u.jarak + uv.bobot. Dengan menggunakan asumsi induktif, u.jarak adalah panjang dari beberapa lintasan yang menghubungkan simpul awal dengan u. Kemudian u.jarak + uv.bobot adalah panjang lintasan yang berasal dari simpul awal menuju v yang mengikuti lintasan yang berasal dari simpul awal menuju u dan kemudian menuju ke v. Untuk bagian kedua,perhatikan bahwa lintasan terpendek dari simpul asal menuju u dengan kebanyakan terdapat pada i sisi. Jadikan v sebagai simpul terakhir sebelum mencapai u pada lintasan tersebut. Kemudian, bagian suatu lintasan dari simpul awal menuju v adalah lintasan terpendek dari simpul asal menuju v pada kebanyakan sisi-sisi i-1. Dengan asumsi induktif ini, v.jarak setelah siklus i-1 kebanyakan panjang dari lintasan ini. Dengan demikian, uv.bobot + v.jarak berada padsa kebanyakn panjang lintasan dari s menuju u. Pada siklus ke- i, u.jarak
19
akan dibandingkan dengan uv.weight + v.jarak, dan himpunan sebanding dengannya jika uv.bobot + v.jarak lebih kecil. Kemudian, setelah siklus i, u.jarak pada kebanyakan panjang lintasan terpendek dari simpul asal menuju u yang melewati kebanyakan sisi i. Ketika i sebanding dengan banyaknya simpul pada graf, setiap lintasan akan dijadikan sebagai shortest path overall, kecuali jika terdapat bobot siklus yang negatif. Jika ada bobot-siklus negatif dan dapat diakses dari simpul asal, kemudian diberikan langkah manapun, akan terdapat sebuah lintasan yang lebih pendek, sehingga tidak terdapat langkah terpendek. Di lain pihak, langkah terpendek tidak akan mengikutsertakan siklus manapun (karena dengan berputar pada siklus tersebut akan membuat langkahnya menjadi semakin pendek), jadi setiap lintasan terpendek akan mengunjungi setiap simpul paling tidak 1 kali, dan banyaknya sisi lebih sedikit dari banyaknya simpul di dalam graf. b) Algoritma // Definisi tipe data dalam graf record titik { list sisi2 real jarak titik sebelum } record sisi { titik dari titik ke real bobot } function BellmanFord(list semuatitik, list semuasisi, titik dari)
// // // // //
Argumennya ialah graf, dengan bentuk daftar titik and sisi. Algoritma ini mengubah titik-titik dalam semuatitik sehingga atribut jarak dan sebelum menyimpan jarak terpendek. Persiapan for each sisi uv in semuasisi: u := uv.dari v := uv.ke // uv adalah sisi dari u ke v if v.jarak > u.jarak + uv.bobot v.jarak := u.jarak + uv.bobot v.sebelum := u // Cari sirkuit berbobot(jarak) negatif for each sisi uv in semuasisi: u := uv.dari v := uv.ke
20
Sumber : Dobson, Simon. (2005). Weighted graphs and shortest paths.UCD School of Computer Science and Informatics. Dublin c) Kompleksitas waktu algoritma (Running time) Algoritma Bellman-Ford menggunakan waktu sebesar : O(V.E) di mana V dan E adalah banyaknya sisi dan titik. Inisialisasi: O(v) Loop utama: O(v.e) Pengecekan loop negative: O(e) Total: O(v.e) 3) Algoritma Floyd-Warshall Algoritma Floyd-Warshall memiliki input graf berarah dan berbobot (V,E), yang berupa daftar titik (node/vertex V) dan daftar sisi (edge E). Jumlah bobot sisisisi pada sebuah jalur adalah bobot jalur tersebut. Sisi pada E diperbolehkan memiliki bobot negatif, akan tetapi tidak diperbolehkan bagi graf ini untuk memiliki siklus dengan bobot negatif. Algoritma ini menghitung bobot terkecil dari semua jalur yang menghubungkan sebuah pasangan titik, dan melakukannya sekaligus untuk semua pasangan titik. a) Deskripsi Dasar algoritma ini adalah sebagai berikut: + Asumsikan semua simpul graf berarah G adalah V = {1, 2, 3, 4, ..., n}, perhatikan subset {1, 2, 3, ..., k}. + Untuk setiap pasangan simpul i, j pada V, perhatiakm semua lintasan dari i ke j dimana semua simpul pertengahan diambil dari {1, 2, ..., k}, dan p adalah lintasan berbobot minimum diantara semuanya. + Algoritma ini mengeksploitasi relasi antara lintasan p dan lintasan terpendek dari i ke j dengan semua simpul pertengahan berada pada himpunan {1, 2, ..., k−1}.
21
+ Relasi tersebut bergantung pada apakah k adalah simpul pertengahan pada lintasan p. Implementasi algoritma ini dalam pseudocode: (Graf direpresentasikan sebagai matrix keterhubungan, yang isinya ialah bobot/jarak sisi yang menghubungkan tiap pasangan titik, dilambangkan dengan indeks baris dan kolom) (Ketiadaan sisi yang menghubungkan sebuah pasangan dilambangkan dengan Tak-hingga) b) Algoritma function fw(int[1..n,1..n] graph) { // Inisialisasi var int[1..n,1..n] jarak := graph var int[1..n,1..n] sebelum for i from 1 to n for j from 1 to n if jarak[i,j] < Tak-hingga sebelum[i,j] := i // Perulangan utama pada algoritma for k from 1 to n for i from 1 to n for j from 1 to n if jarak[i,j] > jarak[i,k] + jarak[k,j] jarak[i,j] = jarak[i,k] + jarak[k,j] b l [i j] b l [k j]
Sumber : Dobson, Simon. (2005). Weighted graphs and shortest paths.UCD School of Computer Science and Informatics. Dublin c) Kompleksitas waktu algoritma (Running time) Algoritma ini berjalan dengan waktu O(V3).
22
