ALGORITMA DJIKSTRA
ALGORITMA
DJIKSTRA
Dosen Pengampu : Adhika P., S. Kom
MATA
KULIAH
: TEORI GRAFT DAN OTOMATA
JURUSAN
: TEKNIK INFORMATIKA
DISUSUN
OLEH :
Siti
Fatimah
Universitas
Nahdlatul Ulama Sunan Giri Bojonegoro (UNUGIRI)
2016
A.
ABSTRAK
Paper
ini membahas tentang persoalan lintasan terpendek suatu graf dengan algoritma
dijikstra. Saat ini banyak sekali algortima-algoritma yang dapat digunakan
untuk menyelesaikan persoalan penentuan lintasan terpendek (shortest path
problem) dari suatu graf. Solusi yang didapat dari penelusuran algoritma
tersebut dapat diberi nama Pathing Algorithm. Ada dua algortima yang cukup
terkenal yang bisa digunakaan untuk menyelesaikan persoalan lintasan terpendek,
yaitu Algoritma Dijkstra dan Algoritma Bellman-Ford. Tetapi pada kesempatan ini
kita hanya akan membahas tentang algoritma dijkstra.
Algoritma Dijkstra merupakan salah
satu algoritma yang digunakan untuk memecahkan permasalahan lintasan terpendek
yang terdapat pada suatu graf . Algoritma ini digunakan pada graf berbobot
dengan syarat bobot dari masing-masing sisi haruslah bernilai positif (>=0).
B.
PENDAHULUAN
Persoalan
mencari lintasan terpendek (shortest path problem) dalam graf merupakan
persoalan optimasi. Pencarian lintasan terpendek termasuk masalah yang paling
umum dalam suatu weighted-connected graph. Dalam masalah ini terdapat subkelas-subkelas
masalah yang lebih spesifik. Misalnya pada jaringan jalan raya yang
menghubungkan kota-kota disuatu wilayah, hendak dicari lintasan terpendek yag
menghubungkan antara dua kota berlainan tertentu (Single-source shortest path
problems), semua lintasan terpendek masing-masing dari suatu kota ke setiap
kota lainnya (Single-source shortest path problems), semua lintasan terpendek
masing-masing antara tiap kemungkinan pasang kota yang berbeda (all-pairs
shortest path problems).
Untuk memecahkan
masing-masing dari masalahmasalah tersebut terdapat sejumlah solusi. Yaitu
algoritma Dijkstra untuk single-source shortest path, algoritma Floyd-Warshall
untuk masalah all-pairs shortest path, dan algoritma Johnson untuk masalah
all-pairs shortest path pada sparse graph.
Dalam beberapa masalah
graf lain, suatu graf dapat memiliki bobot negatif dan kasus ini dipecahkan
oleh algoritma Bellman-Ford. Yang akan dibahas di sini adalah algoritma
Dijkstra yaitu mencari lintasan terpendek dari suatu vertex asal tertentu ke
setiap verteks lainnya (algoritma ini juga berfungsi sangat optimal pada
masalah single-destination).
C.
Dasar
Teori
Dasar
teori yang digunakan dalam penyelesaian masalah pada paper ini dengan
menggunakan Algoritma djikstra, yaitu mencari rute permasalahan terpendek
antara simpul sumber menuju simpul tujuan.
D.
Penjelasan
Algoritma dan Uraian Pemecahan Masalah
Algoritma ini diberi
nama sesuai nama penemunya, Edsger Wybe Dijkstra. Algoritma Dijkstra mencari
lintasan terpendek dalam sejumlah langkah. Algoritma ini menggunakan prinsip
greedy yang menyatakan bahwa pada setiap langkah kita memilih sisi yang
berbobot minimum dan memasukkannya ke dalam himpunan solusi. Input algoritma
ini adalah sebuah graf berarah yang berbobot (weighted directed graph) G dan
sebuah sumber vertex s dalam G dan V adalah himpunan semua vertices dalam graph
G. Algoritma Dijkstra dimulai dari sebuah simpul asal dan dalam setiap
iterasinya menambahkan sebuah verteks lain ke lintasan terpendek pohon
merentang. Verteks ini merupakan titik terdekat ke akar namun masih di luar
bagian pohon.
Algoritma
Dijkstra adalah salah satu metode untuk memecahkan masalah pencarian rute
terpendek. Algoritma ini biasanya diterapkan pada sebuah aplikasi pencari rute
jalan yang terdekat dari suatu daerah ke daerah lainnya. Untuk
bisa menerapkan algoritma ini dibutuhkan beberapa data yang harus disiapkan,
yaitu :
- Beberapa Titik/simpul/daerah, titik/simpul/daerah yang bisa dijangkau secara langsung, dan juga jarak antara mereka.
- Titik/simpul/daerah awal.
- Titik/simpul/daerah tujuan.
4.
Coba perhatikan contoh pemecahan masalah dengan algoritma djikstra
di bawah ini.
Titik A adalah titik awal dan titik F adalah
titik tujuan. Kemudian kita akan mencari rute manakah yang harus dilewati dan
memilik total jarak yang paling dekat. Untuk bisa mendapatkan rute itu, maka
grafik diatas ditambahkan beberapa kotak untuk mengisi beberapa label. Seperti
ini :
E.
Proses
Setelah itu ada beberapa langkah yang harus dilakukan, yaitu
:
1. Mengisi kotak label pada titik awal
dengan label urutan 1 dan label jarak 0.
2. Menetapkan label jarak sementara untuk semua titik yang dapat dihubungi
langsung dari awal.
3. Pilih titik dengan label jarak sementara terkecil dan
menuliskan nilainya di label jarak,
serta tambahkan label urutan-nya.
4. Masukan label jarak sementara pada setiap titik yang belum memiliki label urutan dan label jarak dan dapat dihubungi
langsung dari titik yang baru saja ditulis label jarak dan label
urutan-nya. nilainya diisi dengan total dari label jarak dari titik sebelumnya dan jarak dari titik
tersebut. Jika label jarak sementara
di titik tersebut sudah memiliki nilai, maka harus diganti hanya jika nilai
yang baru lebih kecil.
5. Pilih titik dengan label jarak sementara terkecil dan
menggunakan label jarak sementara-nya
sebagai label jarak dari titik
tersebut, serta tambahkan label urutan-nya.
6. Ulangi langkah 4 dan 5 hingga titik tujuan memiliki label jarak dan label urutan.
Maka pada
langkah pertama adalah Mengisi kotak
label pada titik awal dengan label urutan 1 dan label jarak 0.
Kemudian
mengisi label jarak sementara
titik yang dapat dihubungi langsung dari titik A yakni titik B, C,
dan E.
Maka yang terpilih adalah titik B karena memiliki label
jarak sementara terkecil, dan mengisi nilai label jarak-nya sama dengan label
jarak sementara serta memberikan label urutan-nya.
Selanjutnya mengisi
label jarak sementara titik yang belum memiliki label jarak dan dapat dihubungi langsung dari titik B yakni
hanya titik C. Label
jarak sementara titik C diisi dengan total jarak dari titik A
sampai ke titik C yang melalui titik B, yakni 4 + 2 = 6.
Namun sebelumnya nilai label jarak
sementara-nya titik C
sudah ada dan lebih kecil (5), jadi label jarak sementara-nya tidak diganti dan tetap bernilai 5.
Langkah selanjutnya adalah memilih label jarak sementara terkecil. Karena titik E dan titik C
memiliki label jarak sementara yang
sama yakni 5, maka bisa memilih salah satu dari kedua titik tersebut.
Misalkan titik C yang dipilih, maka berikan label jarak dan label
urutan-nya.
Kemudian titik yang dapat dihubungi secara langsung dari titik
C dan belum memiliki label jarak adalah titik E dan D. Titik E => 5 + 1 = 6,
lebih besar jika dibandingkan dengan nilai label jarak sementara yang dimiliki
oleh titik E sebelumnya (5), maka nilai 6 diabaikan dan tetap diisi 5. Titik D
=> 5 + 2 = 7, maka langsung saja label jarak sementara titik D diisi dengan
7.
Selanjutnya titik E terpilih karena memiliki label jarak
sementara terkecil. Berikan label jarak dan label urutan-nya.
Dan titik F dan G adalah titik yang dapat dihubungi secara langsung dari titik E dan belum memilik label jarak. Titik F => 5 + 3 = 8 dan langsung diisikan kedalam label jarak sementara-nya. sedangkan titik D => 5 + 1 = 6 dan lebih kecil dari pada nilai sebelumnya yaitu 7, maka nilai label jarak sementara-nya diganti dengan 6.
Maka titik D terpilih karena memiliki label jarak sementara
terkecil. Berikan label jarak dan label urutan-nya.
Titik F adalah titik terakhir yang dapat dihubungi secara langsung dari titik D dan belum memilik label jarak serta merupakan titik tujuan. Titik F => 6 + 1 = 7 dan lebih kecil dari pada nilai sebelumnya yaitu 8, maka nilai label jarak sementara-nya diganti dengan 7.
Karena titik F adalah satu-satunya titik terakhir yang
belum mempunyai label jarak dan
label urutan. maka lansung saja
berikan nilai label jarak dan label urutan-nya. Dengan begitu titik tujuan sudah memiliki label jarak dan label jarak sementara.
Cara mengetahui rute yang harus
dilewati
Untuk mengetahui rute manakah yang harus dilewati adalah
dengan menelusuri kembali dari titik tujuan ke titik awal. tuliskan label jarak di samping setiap titik.
Titik
mana sajakah yang dapat dihungi langsung dari titik F ?, Yakni titik E dan D.
maka, untuk menentukan titik manakah yang seharusnya dilewati adalah dengan
cara mengurangkan label jarak titik F dengan jaraknya ke titik tujuan serta
label jarak titik tersebut. jika hasilnya kurang dari 0 maka titik tersebut
tidak layak untuk dilewati, dan jika hasilnya lebih dari 0 serta lebih
mendekati 0 maka titik tersebut yang seharusnya dilewati.
Dengan begitu diketahui rute yang
harus dilewati dan memiliki jarak terpendek dari titik A menuju titik F
adalah A -> E -> D -> F
A.
Kesimpulan
Persoalan mencari
lintasan terpendek merupakan masalah optimasi. Pencarian lintasan terpendek
menggunakan graf berbobot. Dalam mencari lintasan terpendek, algoritma yang
paling banyak digunakan orang ialah algoritma Dijkstra, karena paling kerjanya
paling efisien (mangkus), tidak membutuhkan waktu yang banyak. Salah satu
implementasi dari algoritma Dijkstra ialah penyimpanan simpul dari suatu
himpunan ke dalam suatu array atau list berkait. Dari masalah diatas diketahui rute yang harus dilewati
dan memiliki jarak terpendek dari titik A menuju titik F adalah A
-> E -> D -> F.
B.
Daftar
Referensi
http://nq-belajar.blogspot.co.id/2014/12/makalah-algoritma-dijkstra.html
Thanks for atention....Good bye!!!!!
FB : https://www.facebook.com/sifa.muacihcetiamenunggumu?fref=nf
IG : fatim12469
Twitter : https://twitter.com/ifadafa13_
Thanks for atention....Good bye!!!!!
FB : https://www.facebook.com/sifa.muacihcetiamenunggumu?fref=nf
IG : fatim12469
Twitter : https://twitter.com/ifadafa13_
Komentar
Posting Komentar