MAKALAH ALGORITMA DIJKSTRA
Di Ajukan sebagai tugas Mata Kuliah : Perancangan dan analisisalgoritma
Dosen Pengampu : Erna DwiAstuti, M.Kom
Disusun Oleh :
·
M. FAJRUN N. (130048)
·
ARIFIN (2014150159)
·
ANJAR (130130)
PRODI TEKNIK INFORMATIKA
FAKULTAS TEKNIK DAN ILMU KOMPUTER
UNIVERSITAS SAINS AL-QUR’AN (UNSIQ)
JAWA TENGAH DI WONOSOBO
2015
A. Latar belakang
Makalah ini membahas tentang persoalan lintasan terpendek suatu graf dengan algoritma dijikstra. Lintasan terpendek merupakan bagian dari teori graf. Jika diberikan sebuah graf berbobot, masalah jarak terpendek adalah bagaimana kita mencari sebuah jalur pada graf yang meminimalkan jumlah bobot sisi pembentuk jalur tersebut. Persoalan ini adalah persoalan optimasi, dimana kita akan mencari solusi penyelesaian yang paling efektif dari masalah penentuan lintasan terpendek pada suatu graf.
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. Pembatasan Masalah
Melihat dari latar belakang masalah serta memahami pembahasannya maka penulis dapat memberikan batasan-batasan pada :
1. Persoalan lintasan terpendek pada Graf..
2. Algoritma Djikstra dalam pseudo-code.
3. Analisa Algoritma Djikstra.
C. Rumusan Masalah
Masalah yang dibahas dalam penulisan makalah ini adalah :
1. Bagaimana cara untuk mengetahui prsoalan lintasan terpendek pada Graf?
2. Bagaimana cara untuk mengetahui Algoritma Djikstra dalam pseudo-code?
3. Bagaimana cara menganalisa Algoritma Djikstra?
D. Tujuan Penulisan
Tujuan daripada penulisan makalah ini adalah :
1. Mengetahui Persoalan lintasan terpendek pada Graf.
2. Mengetahui Algoritma Djikstra dalam pseudo-code.
3. Mengetahui Analisa Algoritma Djikstra .
E. Manfaat Penulisan
Hasil dari penulisan ini diharapkan dapat memberikan manfaat kepada semua pihak, khususnya kepada mahasiswa untuk menambah pengetahuan dan wawasan dalam Persoalan lintasan terpendek pada Graf dengan menggunakan Algoritma Djikstra . Manfaat lain dari penulisan makalah ini adalah dengan adanya penulisan makalah ini diharapkan dapat dijadikan acuan didalam membuat sebuah Graf dengan mmenggunakan Algoritma Djikstra.
F. Metode Pengumpulan Data
Data penulisan makalah ini diperoleh dengan metode survey, Selain itu, tim penulis juga memperoleh data dari internet.
PENDAHULUAN
Permasalah optimasi merupakan permasalahan yang sering sekali kita temui dalam
kehidupan sehari-hari. Hal ini tidak lepas dari sifat dasar manusia yang selalu ingin mendapat keuntungan semaksimum mungkin dan memperoleh kerugian seminimum mungkin. Jika kita membicarakan permasalahan mengenai rute atau jalur yang menghubungkan tempat-tempat tertentu maka kita sering menggambarkanya dengan bulatan untuk memvisualisasikan tempat dan garis untuk jalan / rute. Representasi semacam ini merupakan suatu representasi dari graf.
Graf adalah himpunan simpul yang dihubungkan dengan suatu garis dimana garis tersebut menghubungkan dengan tepat ke 2 simpul sehingga simpul-simpul ini saling berhubungan. Dalam kehidupan sehari-hari banyak sekali persoalan yang di implementasikan dengan graf. Bidang-bidang yang menggunakan penerapan graf antara lain Switching network, Coding theory, Electrical analysis, Operation research, aljabar, computer science, dan kimia.
Banyak sekali aplikasi yang mengunakan graf sebagai alat untuk merepresentasikan atau memodelkan persoalan sehingga persoalan itu dapat diselesaikan dengan baik. Aplikasiaplikasi tersebut misalnya menentukan lintasan terpendek (the shortest path problem), traveling salesman problem, chinese postman problem, graf colouring, Making a road system one-way, rangking the participants in a tournament, dan masih banyak lagi. Dalam kesempatan ini kami mencoba mengulas tentang persoalan menentukan lintasan terpendek (The Shortest Path Problem).
Menurut teori graf, persoalan lintasan terpendek adalah suatu persoalan untuk mencari
lintasan antara dua buah simpul pada graf berbobot yang memiliki gabungan nilai jumlah
bobot pada sisi graf yang dilalui dengan jumlah yang paling minimum. Persoalan lintasan
terpendek ini banyak sekali dijumpai di kehidupan sehari-hari. Aplikasi yang paling sering ditemui adalah pada bidang transportasi, seperti pada pencarian rute terbaik untuk menempuh dua kota.
Persoalan Lintasan Terpendek Pada Graf
Menurut teori graf, persoalan lintasan terpendek adalah suatu persoalan untuk mencari lintasan antara dua buah simpul pada graf berbobot yang memiliki gabungan nilai jumlah bobot pada sisi graf yang dilalui dengan jumlah yang paling minimum atau dapat dinyatakan juga sebagai berikut : diberikan sebuah graf berbobot (dengan himpunan simpul V, himpunan sisi E, dan fungsi bobot bernilai bilangan riil yang dapat ditulis dengan f : E → R), dan diberikan elemen v dari V, sehingga dapat dicari sebuah lintasan P dari v ke setiap v' dari V, sehingga
Ʃ f(p)
pϵP adalah nilai minimum dari semua lintasan yang menghubungkan v ke v'.
Persoalan lintasan terpendek merupakan salah satu persoalan optimasi yeng menggunakan graf berbobot, dimana bobot pada setiap sisi graf tersebut dapat kita gunakan untuk menyatakan jarak kota, waktu pengiriman pesan, ongkos pembangunan, dan sebagainya.
• Aplikasi dari Persoalan lintasan terpendek pada Graf
Ada beberapa macam persoalan lintasan terpendek, antara lain :
1. Lintasan terpendek antara dua buah simpul tertentu
2. Lintasan terpendek antara semua pasangan simpul
3. Lintasan terpendek dari simpul tertentu ke semua simpul yang lain
4. Lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu
Aplikasi persoalan penentuan lintasan terpendek ini banyak sekali kita jumpai dalam
kehidupan sehari-hari :
a. Menentukan rute / jalur terbaik yang harus ditempuh dari suatu kota menuju ke kota
yang lain
b. Menentukan jalur komunikasi 2 buah terminal komputer
c. Menentukan jalur penerbangan dunia yag paing efektif untuk di lakukan.
ALGORITMA DIJKSTRA
Pada tahun 1959 sebuah tulisan sepanjang
tiga halaman yang berjudul A Note on Two Problems in Connexion with
Graphs diterbitkan padajurnalNumerische Mathematik. Padatulisanini,
Edsger W. Dijkstra - seorangilmuwan computer berumur duapuluh sembilantahun
mengusulkan algoritma-algoritma untuk solusi dari dua masalah teoritis graf
dasar: the minimum weight Algoritma Dijkstra untuk masalah
jalan terpendek adalah satu dari algoritma - algoritma paling ternama pada ilmu
komputer dan sebuah algoritma paling popular pada oparasi pencarian (OR).
Implementasi algoritma dijkstra.
Algoritma ini termasuk algoritma pencarian graf yang digunakan untuk
menyelesaikan masalah lintasan terpendek dengan satu sumber pada sebuah graf
yang tidak memiliki cost sisi negatif, dan menghasilkan sebuah pohon lintasan.
Algoritma ini menggunakan prinsip greedy yang digunakan untuk menyatakan bahwa
pada setiap langkah kita memilih sisi yang berbobot minimum dan memasukannya ke
dalam himpunan solusi. Akan tetapi bobot dari graf tersebut harus bernilai
bilangan positif (bobot >= 0). Algoritma ini untuk menggambarkan jarak kedua
tempat dengan jarak yang digambarkan secara singkat .
|
contoh skema algoritma dijsktra
Tujan Algoritma Dijkstra
·
Tujuan
Algoritma Dijkstra yaitu untuk menemukan jalur terpendek berdasarkan bobot
terkecil dari satu titik ke titik lainnya.
·
Kelemahan
algoritma ini adalah semakin banyak titik akan semakin memakan waktu proses.
·
Jumlah
titik menentukan tingkat efektifitas dari algoritma djikstra.
Properti Algoritma
Djikstra
1. Matriks
Ketetangga M [mij]
mij = bobot sisi (i,j) ; pada graf tak
berarah mij = mji
mii = 0
mij = , jika tidak ada sisi dari
simpul i ke simpul j
2. Larik
S = [si] yang dalam hal ini,
si = 1, jika simpul i termasuk ke
dalam lintasan terpendek
si = 0, jika simpul i tidak termasuk
ke dalam lintasan terpendek
3. Larik
/ tabel D = [di] yang dalam hal ini, di = panjang lintasan dari simpul awal s
ke simpul I.
|
Maximum Flow Problem ( Network
Flow )
Flow network adalah sebuah graf berarah
yang tiap sisinya memiliki kapasitas/bobot dan pada tiap sisi tersebut terdapat
arus (flow) yang mengalir antara 2 simpul yang mengapit sisi tersebut. Jumlah
arus yang mengalir pada tiap sisi harus lebih kecil atau sama dengan kapasitas
sisi tersebut.Pada aplikasinya, sebuah graf berarah sering disebut dengan
network. Jumlah arus yang mengalir pada tiap sisi harus lebih kecil atau sama
dengan kapasitas sisi tersebut. Pada aplikasinya, sebuah graf berara sering disebut
dengan network.Setiap arus (flow) yang ada dalam network, harus
memenuhi sebuah batasanya itu arus yang masuk pada suatu simpul harus sama
dengan arus yang keluar pada simpul tersebut, kecuali pada source, yang
keluarnya lebih besar dari arus masuk, dan sink, yang arus
masuknya lebih besar dari arus keluar Sebuahnetwork biasanya
digunakan untuk memodelkan sistem lalu lintas, saluran pipa, sirkuitelektrik.
Pencarian rute terpendek merupakan salah
satu persoalan dalam teori graf. Persoalan ini bisa diselesaikan dengan
algoritma dijkstra karena lebih mudah dan menarik, adapun beberapa keuntungan
yang kita peroleh dari Algoritma Dijkstra yaitu :
1. Algoritma Dijkstra
dapat menentukan jalur tercepat dengan waktu yang lebih cepat dibandingkan
algoritma lainnya.
2. Menggunakan Algoritma Dijkstra
mempermudah kita dalam mengetahui jarak atau lintasan terpendek dari suatu
titik tertentu ke semua titik yang lain.
3. Menggunakan
Algoritma Dijkstra dalam penerapan di dalam sistem geografis akan
menampilakan visualisasi data dalam bentuk peta
4. Pada penampilan
rute atau peta Algoritma Dijkstra lebih mudah di baca dan di pahami.
5. Pada rute atau peta
dan lintasannya dapat diberikan warna, sehingga penampilan Algoritma Dijkstra
lebih menarik dan lebih mudah untuk membedakan dari suatu titik tertentu ke
titik yang lain.
Edsger Wybe Dijkstra, menemukan suatu algoritma untuk mencari lintasan terpendek
pada suatu graf. Algoritma Dijkstra pada awalnya diterapkan pada graf berarah, tetapi
ternyata algoritma ini juga benar untuk algoritma graf tak-berarah. Algoritma ini menggunakan prinsip greedy yang digunakan untuk menyatakan bahwa pada setiap langkah kita memilih sisi yang berbobot minimum dan memasukannya ke dalam himpunan solusi.
Akan tetapi bobot dari graf tersebut harus bernilai bilangan positif (bobot >=0). 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 diluar bagian pohon.
v Algoritma djikstra dalam pseudo-code :
procedure Dijkstra (input m: matriks, a:simpul awal)
{mencari lintasan terpendek dari simpul awal a ke semua simpul lainya
Masukan : matriks ketetanggaa (m) dari graf berbobot G dan
simpul awal a
Keluaran: lintasan terpendek dari a ke semua simpul lainnya}
• Deklarasi
s1,s2,...,sn : interger {larik interger}
d1,d2,...,dn : interger {larik interger}
i : interger
• Algoritma
{Langkah 0 (inisialisasi) : }
for i ← 1 to n do
si ← 0
di ← mai
endfor
{Langkah 1: }
sa ← 1 {karena simpul a adalah simpul asal lintasan terpendek, jadi terpilih dalam lintasan terpendek}
da ← ꝏ {tidak ada lintasan terpendek dari simpul a ke a}
{Langkah 2,3,...,n1:}
for i ← 2 to n1 do
Cari j sedemikian sehingga sj = 0 dan dj = min {d1,d2,...,dn}
Sj ← 1 {simpul j sudah terpilih ke dalam lintasan terpendek}
perbarui di, untuk i = 1,2,3,...,n
dengan : di (baru) = min {di(lama), dj + mji}
endfor
Analisa Algoritma Dijkstra
Algoritma ini mirip dengan algoritma Prim untuk mencari MST, yaitu pada tiap iterasi
memeriksa sisi-sisiyang menghubungkan subset verteks W dan subset verteks (V-W) dan
memindahkan verteks w dari (VW) ke W yang memenuhi kriteria tertentu. Perbedaannya
terletak pada kriteria itu sendiri. Dalam algoritma Dijkstra, yang dicari adalah sisi yang
menghubungkan ke suatu verteks di (V-W) sehingga jarak dari verteks asal Vs ke verteks
tersebut adalah minimal.
Dalam implementasinya penghitungan jarak dari verteks asal vs disederhanakan dengan
menambahkan field minpath pada setiap verteks. Field-field minpath ini diinisialisasi sesuai dengan adjacency-nya dengan vs, kemudian dalam setiap iterasi di-update bersamaan masuknya w dalam W. Field minpath ini menunjukkan jarak dari vs ke verteks yang bersangkutan terpendek yang diketahui hingga saat itu. Jadi pada verteks dalam W, minpath sudah menunjukkan jarak terpendek dari Vs untuk mencapai verteks yang bersangkutan, sementara pada (V-W) masih perlu di-update pada setiap iterasi dalam mendapatkan verteks.
w seperti diterangkan di atas. Yaitu, setiap mendapatkan w maka update minpath setiap
adjacent verteks x dari w di (V-W) sisa dengan:
minimum (minpath dari x , total minpath w + panjang sisi yang bersangkutan). Agar dapat berlaku umum maka di awal algoritma seluruh minpath diinisialisasi
dengan +∞.
Demikian halnya pencarian w itu sendiri disederhanakan menjadi pencarian node di (VW) dengan minpath terkecil. Selengkapnya algoritma Dijkstra adalah sebagai berikut :
1. Inisialisasi
W berisi mula-mula hanya vs, field minpath tiap verteks v dengan Weight[vs, v], jika
ada sisi tersebut, atau, +∞ jika tidak ada.
2. Lalu, dalam iterasi lakukan hingga (V-W) tak tersisa (atau dalam versi lain: jika ve
ditemukan) dari field minpath tiap verteks cari verteks w dalam (V-W) yang memiliki
minpath terkecil yang bukan tak hingga. Jika ada w maka masukkan w dalam W.
Update minpath pada tiap verteks t adjacent dari w dan berada dalam (VW) dengan:
minimum (minpath[t] , minpath[w] + weight [w, t]).
Verteks-verteks dalam W dapat dibedakan dari verteks dalam (V-W) dengan suatu field
yang berfungsi sebagai flag atau dengan struktur linked-list. Informasi lintasan dapat
diketahui dengan pencatatan predesesor dari setiap verteks yang dilakukan pada saat update harga minpath tersebut (fungsi minimum). Jika minpath[t] di-update dengan (minpath[w] + Weight [w, t]) maka predesesor dari t adalah w. Pada tahap inisialisasi predesesor setiap verteks diisi oleh vs.
Algoritma Dijkstra membuat label yang menunjukkan simpul-simpul. Label-label ini
melambangkan jarak dari simpul asal ke suatu simpul lain. Dalam graf, terdapat dua macam label, sementara dan permanen. Label sementara diberikan untuk simpul-simpul yang belum dicapai. Nilai yang diberikan untuk label sementara ini dapat beragam. Label permanen diberikan untuk simpul-simpul yang sudah dicapai dan jarak ke simpul asal diketahui. Nilai yang diberikan untuk label ini ialah jarak dari simpul ke simpul asal. Suatu simpul pasti memiliki label permanen atau label sementara. Tetapi tidak keduanya.
Algoritma dimulai dengan menginisialisasi simpul manapun di dalam graf (misalkan
simpul A) dengan label permanen bernilai 0 dan simpul-simpul sisanya dengan label
sementara bernilai 0. Algoritma ini kemudian memilih nilai sisi terendah yang menghubungkan simpul dengan label permanen (dalam hal ini simpul A) ke sebuah simpul lain yang berlabel sementara (misalkan simpul V). Kemudian label simpul V di-update dari label sementara menjadi label permanen. Nilai simpul V merupakan penjumlahan nilai sisi dan nilai simpul A.
Langkah selanjutnya ialah menemukan nilai sisi terendah dari simpul dengan label sementara, baik simpul A maupun simpul B (misalkan simpul E). Ubah label simpul E menjadi permanen, dan ukur jarak ke simpul A. Lamanya waktu untuk menjalankan Algoritma Dijkstra's pada suatu graf dengan Y (himpunan sisi) dan Z (himpunan simpul) dapat dinyatakan sebagai fungsi Y dan Z menggunakan notasi Big-O. Waktu yang dibutuhkan algoritma Dijkstra untuk bekerja ialah sebesar O(V*log V + Y). Implementasi paling sederhana dari algoritma Dijkstra ialah penyimpanan simpul dari suatu himpunan ke dalam suatu array atau list berkait.
KESIMPULAN
1. Persoalan mencari lintasan terpendek dari setiap graf berbobot, merupakan masalah optimasi.
2. Algoritma Dijkstra merupakan salah satu algoritma yang digunakan untuk memecahkan permasalahan lintasan terpendek yang terdapat pada suatu graf.
3. Algoritma ini digunakan pada graf berbobot dengan syarat bobot dari masing-masing sisi haruslah bernilai positif (>=0).
4. Salah satu implementasi dari algoritma Dijkstra ialah penyimpanan simpul dari suatu himpunan ke dalam suatu array atau list berkait (linked list).
5. Dalam mencari lintasan terpendek, algoritma yang paling banyak digunakan orang
ialah algoritma Dijkstra, karena kerjanya efisien dan tidak membutuhkan waktu yang banyak. Tetapi Algoritma Dijkstra yang menerapkan prinsip greedy tidak selalu berhasil memberikan solusi optimum untuk kasus penentuan lintasan terpendek (single pair shortest path).
DAFATAR PUSTAKA
http://nq-belajar.blogspot.com/2014/12/makalah-algoritma-dijkstra.html
Tidak ada komentar:
Posting Komentar