Friday, January 13, 2012

Analisis Algoritma Pencarian Rute Terpendek Dengan Algoritma Dijkstra dan Bellman - Ford


Analisis Algoritma Pencarian Rute Terpendek
Dengan Algoritma Dijkstra dan Bellman - Ford
Abstrak
Permasalan pencarian rute terpendek merupakan suatu masalah yang sangat terkenal di dunia Informatika. Dari dahulu hingga sekarang telah dikembangkan berbagai algoritma untuk memecahkan permasalahan ini. Persoalan yang terkenal dalam pencarian rute terpendek adalah persoalan pedagang keliling (traveling salesperson problem - TSP). Seperti yang telah ditulis di atas, hingga saat ini telah banyak yang menemukan solusi untuk pencarian rute terpendek ini. Salah satunya yang terkenal adalah algoritma dijkstra.
Selain itu, sebagai pembanding keefektivan algoritma ini kami membandingkannya dengan algoritma Bellman – Ford yang juga merupakan algoritma yang cukup banyak dipakai dalam peermasalahan ini.
Kata kunci: Dijkstra,Bellman – ford, Shortest path, Travellong salesperson.

1. Pendahuluan
Permasalahan utama pencarian rute terpendek tentu saja mencari rute atau jalur terpendek yang memungkinkan. Namun untuk implementasinya, persoalan ini dapat dikembangkan lebih luas lagi diantaranya untuk mencari biaya minimum, dll. Intinya adalah mencari solusi yang palin efektiv yang dapat diterpakan dalam persoalan yang dihadapi.
2. Analisis Algoritma Dijkstra dan  Bellman-Ford
2.1 Algoritma Dijkstra
Algoritma Dijkstra, dinamakan sesuai dengan nama penemunya, seorang ilmuwan komputer berkebangsaan Belanda yang bernama Edsger Dijkstra, adalah algoritma yang digunakan untuk mencari lintasan terpendek pada sebuah graf berarah. Cara kerja algoritma Dijkstra memakai stategi greedy, dimana pada setiap langkah dipilih sisi dengan bobot terkecil yang menghubungkan sebuah simpul yang sudah terpilih dengan simpul lain yang belum terpilih.
2.2 Algoritma Bellman-Ford
Algoritma Bellman-Ford ,seperti halnya algoritma dijkstra,digunakan untuk mencari lintasan terpendek pada sebuah graf berarah. Yang membedakan keduanya adalah pada algoritma Bellman-ford bisa digunakan untuk graf yang memiliki sisi dengan bobot negatif, walaupun menggunakan waktu yang lebih lama. Kompleksitas algoritma ini sebesar O(nm) dimana n adalah jumlah simpul dan m adalah jumlah sisi.
Berikut adalah salah satu contoh
implementasi dari algoritma Bellman-Ford :
/* pendefinisian tipe data untuk sebuah
graf */
record vertex {
list edges
real distance
vertex predecessor
}
record edge {
node source
node destination
real weight
}
function BellmanFord(list vertices, list
edges, vertex source)
/* pengimplementasian terhadap graf yang
direpresentasikan oleh list of simpul dan
sisi, dan mengubah simpul sehingga jarak
dan predesesornya menyimpan jarak
terpendek */
// inisialisasi graf
for each vertex v in vertices:
if v is source then
v.distance = 0
else
v.distance := infinity
v.predecessor := null
// periksa setiap simpul
for i from 1 to size(vertices):
for each edge uv in edges:
u := uv.source
v := uv.destination
// uv is the edge from u to v
if v.distance>u.distance+uv.weight
v.distance:=u.distance+uv.weight
v.predecessor := u
// mencari loop yang berbobot negatif
for each edge uv in edges:
u := uv.source
v := uv.destination
if v.distance > u.distance + uv.weight
error "Graf mengandung loop negatif"
3.Kesimpulan
Baik algoritma dijkstra maupun bellman-ford sama2 digunakan untuk mencari lintasan terpendek. Namun, tidak seperti algoritma dijkstra, algoritma bellman-ford dapat digunakan pada graf yang mengandung simpul negatif, selama graf tersebut tidak mengandung kalang negatif yang dapat dicapai dari titik awal. Algoritma dijkstra lebih menguntungkan dari sisi running time , namun untuk permasalahan khusus yang mengandung simpul negatif, algoritma bellman-Ford lah yang lebih menguntungkan.
4. Daftar Pustaka
[1] Munir Rinaldi, Diktat Kuliah Strategi Algoritmik, 193, 2005.
Previous Post
Next Post

5 comments:

  1. berdasarkan artikel tersebut, bisa menjadi rujukan link penelitian dibawah ini

    http://repository.gunadarma.ac.id/bitstream/123456789/1044/1/50406021.pdf

    terima kasih

    ReplyDelete
  2. kami juga mempunyai artikel mengenai algoritmaa djikstra, bisa dibaca di
    http://www.google.co.id/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&cad=rja&ved=0CC4QFjAB&url=http%3A%2F%2Frepository.gunadarma.ac.id%2Fbitstream%2F123456789%2F2734%2F1%2FKommit2000_komputasi_008.pdf&ei=452TUN6IC5GHrAfq3ICQBA&usg=AFQjCNFjUuLg5YEIWyE4wM0RKhtEMqWHEw&sig2=ZbmirwkkaJyvPx1woPKTqg
    semoga bermanfaat :D

    ReplyDelete
  3. kak mau nanya dong, kalo bellman ford apakah harus ada bobot negatifnya? kalo diimplementasikan dengan kehidupan sehari2, bobot negatif itu seperti apa?

    ReplyDelete

"Kalau mau Copy-Paste artikel boleh saja, tapi sumbernya ke blog ini"