Analisis Algoritma Pencarian Rute Terpendek
Dengan Algoritma Dijkstra dan Bellman - Ford
Abstrak
Permasalan pencarian ruteterpendek merupakan suatu masalah yang sangat terkenal di dunia Informatika. Daridahulu hingga sekarang telah dikembangkan berbagai algoritma untuk memecahkanpermasalahan ini. Persoalan yang terkenal dalam pencarian rute terpendek adalahpersoalan pedagang keliling (traveling salesperson problem - TSP). Seperti yangtelah ditulis di atas, hingga saat ini telah banyak yang menemukan solusi untukpencarian rute terpendek ini. Salah satunya yang terkenal adalah algoritma dijkstra. Selain itu,sebagai pembanding keefektivan algoritma ini kami membandingkannya dengan algoritmaBellman – Ford yang juga merupakan algoritma yang cukup banyak dipakai dalam peermasalahanini. Kata kunci: Dijkstra,Bellman – ford, Shortest path, Travellongsalesperson.
1. Pendahuluan
Permasalahan utamapencarian rute terpendek tentu saja mencari rute atau jalur terpendek yangmemungkinkan. Namun untuk implementasinya, persoalan ini dapat dikembangkanlebih luas lagi diantaranya untuk mencari biaya minimum, dll. Intinya adalah mencarisolusi yang palin efektiv yang dapat diterpakan dalam persoalan yang dihadapi.
2. Analisis AlgoritmaDijkstra dan Bellman-Ford
2.1 Algoritma Dijkstra
Algoritma Dijkstra,dinamakan sesuai dengan nama penemunya, seorang ilmuwan komputer berkebangsaanBelanda yang bernama Edsger Dijkstra, adalah algoritma yang digunakan untukmencari lintasan terpendek pada sebuah graf berarah. Cara kerja algoritmaDijkstra memakai stategi greedy, dimana pada setiap langkah dipilih sisidengan bobot terkecil yang menghubungkan sebuah simpul yang sudah terpilihdengan simpul lain yang belum terpilih.
2.2 AlgoritmaBellman-Ford
Algoritma Bellman-Ford,seperti halnya algoritma dijkstra,digunakan untuk mencari lintasan terpendekpada sebuah graf berarah. Yang membedakan keduanya adalah pada algoritmaBellman-ford bisa digunakan untuk graf yang memiliki sisi dengan bobot negatif,walaupun menggunakan waktu yang lebih lama. Kompleksitas algoritma ini sebesarO(nm) dimana n adalah jumlah simpul dan m adalah jumlah sisi.
Berikut adalah salah satucontoh
implementasi dari algoritmaBellman-Ford :
/* pendefinisian tipedata 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)
/* pengimplementasianterhadap graf yang
direpresentasikan olehlist of simpul dan
sisi, dan mengubahsimpul sehingga jarak
dan predesesornyamenyimpan 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 setiapsimpul
for i from 1 to size(vertices):
for each edge uv in edges:
u := uv.source
v := uv.destination
// uv is the edge fromu to v
if v.distance>u.distance+uv.weight
v.distance:=u.distance+uv.weight
v.predecessor := u
// mencari loop yangberbobot 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 dijkstramaupun bellman-ford sama2 digunakan untuk mencari lintasan terpendek. Namun,tidak seperti algoritma dijkstra, algoritma bellman-ford dapat digunakan padagraf yang mengandung simpul negatif, selama graf tersebut tidak mengandung kalangnegatif yang dapat dicapai dari titik awal. Algoritma dijkstra lebihmenguntungkan dari sisi running time , namun untuk permasalahan khususyang mengandung simpul negatif, algoritma bellman-Ford lah yang lebih menguntungkan.
4. Daftar Pustaka
[1] Munir Rinaldi, DiktatKuliah Strategi Algoritmik, 193, 2005.
Beberapa waktu lalu tepatnya di bulan april, Google melakukan update page rank untuk kesekian kalinya, dan melakukan perubahan algoritma pada hasil indexnya dengan algoritma yang baru yaitu algoritma google panda yang mengganti pendahulunya algoritma google caffeine. Banyak blog-blog lama yang telah merasakan ganasnya algoritma google terutama blog-blog luar dengan content bahasa Inggris. Algoritma google dipergunakan untuk mengurangi dan mengikis habis blog atau website dengan conteng auto generate dan copy paste sehingga hasil pencarian lebih mendekati kebenaran.
