- Algoritma Warshall
Algoritma
Warshall memiliki input graf berarah dan berbobot (V,E), yang berupa daftar
titik (node/vertex V) dan daftar sisi (edge E). Jumlah bobot sisi-sisi 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. Algoritma Warshall yang menerapkan pemrograman
dinamis lebih menjamin
keberhasilanpenemuan solusi optimum untuk kasus penentuanlintasan terpendek
(single pair shortest path).
Contoh :
Dari Titik F Menuju
Titik C ada berapa cara :
(F – A – B – C) —>91Km
(F – A – D – C) —>107Km
(F – A – F – E – D – C)
—>114Km
(F – A – F – E – D – C)
—>114Km
(F – E – D – C) —>80Km
(F – E – D – C) —>80Km
Nah, dengan algoritma Warshall
ini, kita dapat mendapatkan informasi yang sedemikian rupa untuk kita timbang
dan menentukan jalur yang paling efisien.
Aplikasi dalam kehidupan
sehari-hari :
Seperti kita berkunjung ke
suatu tempat, pasti ada banyak pilihan jalan yang harus kita lalui, tergantung
kita memilih dan memutuskan kita pilih mana. Tentu, kita akan memilih rute atau
jalan yang lebih efesien “Biaya murah, cepat dan tidak terlalu repot”.
- Algoritma Dijkstra
Algoritma
Dijkstra, dinamai menurut penemunya, Edsger Dijkstra, adalah sebuah algoritma
rakus (greedy algorithm) dalam memecahkan permasalahan jarak terpendek
(shortest path problem) untuk sebuah graf berarah (directed graph) dengan
bobot-bobot sisi (edge weights) yang bernilai tak-negatif.
Algoritma Dijkstra :
·
Tentukan
u0 paling kiri. Biasanya u0 diberi tahu.
·
Lintasan
berakhir paling ujung.
·
Lintasan
atau busur yang dilalui tidak boleh membentuk cycle.
·
Harus
berurutan pemberian labelnya pada tiap simpul.
· Carilah busur dengan bobot yang paling minimum.
Contoh 1.
Sekarang kita akan mencari
jalur terpendek dari A ke C. Ada banyak sekali kemungkinan jalan yang bisa di
tempuh
·
A – E – D – C
·
A – F – G – C
·
A – B – C
· Dan
rute/node2 lainnya.
Tapi
sekarang kita akan mencari jalur terpendek, dengan cara membandingkan jarak
atau ongkos/biaya yang terkecil.
Contoh
2.
Carilah
lintasan terpendek dari u0 ke setiap simpul lainnya, dari graf di bawah ini !
|
|
|
|
Yaitu : Ketika kita
memasak, maka kita perlu menyiapkan segala alat yang diperlu untuk di masak,
nah disini kita belajar bagaimana ketika memasak tidak banyak memakan waktu
yang lama dan efesien dan cepat dengan cara membandingkan dalam mengerjakan hal
yang lebih dulu. Dan masih banyak aplikasinya yang boleh kita diterapkan dalam
kehidupan kita sehari-hari.
Aplikasi dalam kehidupan
sehari :
Yaitu : Ketika kita memasak, maka kita
perlu menyiapkan segala alat yang diperlu untuk di masak, nah disini kita
belajar bagaimana ketika memasak tidak banyak memakan waktu yang lama dan
efesien dan cepat dengan cara membandingkan dalam mengerjakan hal yang lebih
dulu. Dan masih banyak aplikasinya yang boleh kita diterapkan dalam kehidupan
kita sehari-hari.
Reference :
Munir, Rinaldi,2005. Matematika Diskrit. Bandung:
Informatika Bandung. http://www.scribd.com/doc/27745962/Microsoft-Access-2007,
Kamayudi,
Apri. 2006. Studi dan Implementasi Algoritma Djikstra, Bellman-Ford dan
Floyd-Warshall dalam menangani masalah lintasan terpendek dalam Graf. Program
Studi Teknik Informatika, Institut Teknologi Bandung.
Luh
Joni Erawati. 2008. “Pencarian Rute Terpendek Tempat Wisata di Bali dengan
Menggunakan Algoritma Dijkstra”
http://www.ittelkom.ac.id/library/index.php?view=article&catid=20%3Ainformatika&id=161%3Aalgoritmadijkstr&option=com_content&Itemid=15
http://www-b2.is.tokushimau.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml
0 komentar: