Analisis Algoritma DIJKSTRA (tugas PTI)

Model yang Dipilih :  

PENCARIAN RUTE TERPENDEK TEMPAT WISATA DI BALI DENGAN MENGGUNAKAN ALGORITMA DIJKSTRA.

 Analisisnya adalah sebagai berikut:

1. Isi     :

Perkembangan teknologi komputer telah membuka wawasan dan paradigma baru dalam proses pengambilan keputusan dan penyebaran informasi. Data yang merepresentasikan ”dunia nyata” dapat disimpan dan diproses sedemikian rupa sehingga dapat disajikan dalam bentuk-bentuk yang lebih sempurna dan sesuai kebutuhan.

Pencarian rute terpendek termasuk ke dalam materi teori graf. Algoritma yang sangat terkenal untuk menyelesaikan persoalan ini adalah algoritma Dijkstra. Algoritma ini ditemukan oleh seorang ilmuwan komputer berkebangsaan Belanda yang bernama Edsger Dijkstra. Gambar 1 berikut ini

adalah pseudo code dari algoritma Dijkstra(Jong Jek Siang,2004).

Algoritma Dijkstra

1. procedure dijkstra (w,a,z,L)
2. L(a) := 0
3. S := { }
4. for semua verteks x≠a do
5. L(x) := ∞
6. T := himpunan semua vertex
7. while z(T do
8. begin
9. pilih v(T dengan minimum L(v)
10. T:= T-{v}
11. S:= S union {v}
12. for setiap x(T di samping v
do
13. L(x):=min{L(x), L(v)+w(v,x)}
14. end
15. end dijkstra

2. Hasil

Aplikasi pencarian jalur terpendek pada petapariwisata Bali ini telah diuji dengan menggunakanbeberapa kasus. Rekapitulasi pengujian terhadapaplikasi ini dapat dilihat pada Tabel 1.Sebagai contoh kasus pencarian jalurterpendek menggunakan algoritma Dijkstra, yakni:

Lokasi asal : Tanah Lot

Lokasi tujuan : SanurJarak Terpendek : 33.33 km
Banyak titik dilalui : 9
Jalur terpendeknya : 33 (Tanah Lot) – 34
(Beraban) – 27 (Canggu) - 29(Persimpangan
Gunung Merapi-Gunung Agung-Setia Budi) – 31
(Simpang Ubung) – 32 (Simpang Tohpati) -
30(Padang Galak) – 21 (Persimpangan Ngurah
Rai Bypass - Hang Tuah) – 22 (Sanur)

3. Kelebihan

1. Algoritma Dijkstra cukup baik digunakanpada pencarian rute terpendek dari danmenuju suatu tempat wisata di Bali
2. Kualitas gambar peta Bali yang dihasilkancukup baik dengan menggunakan format file
SVG.
3. Sistem yang dibangun memiliki berbagaikeunggulan yaitu: kemudahan dalam akses
dan jangkauan luas.

4. Kelemahan:

tampilan sistem masih sederhana sepertifasilitas multimedia perlu ditambah agar lebihmenarik dan interaktif. Untuk itu, sistem ini perludikembangkan lebih lanjut

5. Saran

Bagi para mahasiswa UNIB dan lainnya pada umumnya diharapkan untuk mempelajari algoritma Dijksta , agar pengetahuan tentang algoritma bertambah