Cara Mudah Memahami Metode Djikstra

Menentukan Jarak Terpendek

Depok-Semanggi Dengan Metode Djikstra

 

                             Kelapa dua    
Kampung

                                 rambutan

                     500m
2000m    

Margonda
     1000m    
UI     1500m     Pasar minggu

     4000m

                                1200m

                                        Pancoran

 

 

500m 1000m 1000m 3200m

 

Plaza Komdak      LIPI

Semanggi    

     1000m

     Gatot Subroto 1000m Kuningan                         

Berikut ini adalah penelusuran jalur dari Margonda hingga ke Plaza Semanggi, apabila menggunakan algoritma Dijkstra (prinsip Greedy) :

Tahap 1 : Dari Margonda kita memilih jalur UI dengan jarak (1000m)

Tahap 2 : Dari UI ada 2 jalur Kelapa Dua (500m) dan Pasar Minggu (1500m) maka kita memilih Kelapa Dua karena jaraknya yang lebih dekat.

Tahap 3 : Kemudian dari Kelapa Dua lanjut ke Kp. Rambutan (2000m).

Tahap 4 : setelah dari Kp. Rambutan kita melewati arah pancoran (4000m)

Tahap 5 : dari arah pancoran, kita ambil arah jalan yang menuju LIPI (1000m), karena jaraknya

Lebih dekat daripada ke kuningan (3200m)

Tahap 6 : kemudian, dari LIPI tinggal lurus saja menuju Komdak (1000m)

Tahap 7 : dan yang terakhir dari Komdak kita bisa hanya dengan menyebrang sejauh (500m)

 

 

Maka total jarak yang di tempuh dari margonda hingga ke semanggi adalah 10 Km(10000 m) dengan jalur (Margonda(1000m)+UI(500)+Kelapa Dua(2000m)+Kampung Rambutan(4000m)-Pancoran(1000m)-LIPI(1000m)-Komdak(500m)-plaza Semanggi)= 10 km.

Biaya dari depok ke semanggi menurut metode Djikstra bila menggunakan

1. Bis P54 dengan rute margonda langsung ke semanggi menghabiskan biaya Rp.2500,-
   
2. Naik angkot 112 dari depok menuju Kp. Rambutan dengan biaya Rp.3500,-,terus naik P70 dengan biaya senin-jum'at Rp. 6000,- dan Sabtu-Minggu Rp. 7000,-. Lewat jalur masuk tol Taman Mini-MT. Haryono-Pancoran-Gatot Subroto-Komdak-Semanggi.
   

ABSTRAK

 

Penentuan lintasan terpendek dari satu titik ke titik yang lain adalah masalah yang sering ditemui dalam kehidupan sehari-hari. Berbagai kalangan menemui permasalahan serupa dengan variasi yang berbeda, contohnya seorang pengemudi yang mencari jalur

terpendek dari tempat asal ke tempat tujuan, pengantar pesanan makanan cepat saji yang juga mencari jalur terpendek dari tempat asal ke tempat tujuan, dan juga seorang desainer jaringan computer yang harus mendesain skema perutean pada jaringan

yang dia tangani agar memaksimalkan performa jaringan dan meminimalkan beban yang harus ditangani oleh jaringan tersebut.

 

Seiring dengan waktu yang berjalan dan juga perkembangan ilmu pengetahuan dan teknologi,permasalahan pencarian lintasan terpendek ini telah terpecahkan dengan berbagai algoritma. Beberapa algoritma populer yang memecahkan persoalan lintasan terpendek tersebut adalah algoritma Dijkstra, Bellman-Ford, A-star, Floyd-Warshall, dsb.

 

1. PENDAHULUAN

Salah satu persoalan optimasi yang sering ditemui dalam kehidupan sehari-hari adalah pencarian lintasan terpendek (shortest path). Persoalan ini bisa dimodelkan ke dalam suatu graf berbobot dengan nilai pada masingmasing sisi yang merepresentasikan persoalan yang akan dipecahkan. Kata "terpendek" pada kata "lintasan terpendek" ini tidak berarti hanya bisa diartikan jarak secara fisik, namun hal itu tergantung dari tipe persoalan yang akan dipecahkan. Bisa jadi kata tersebut memiliki makna tingkat aksesibilitas suatu simpul dalam graf dari simpul yang lain.

Persoalan lintasan terpendek yang akan dibahas di makalah ini adalah lintasan terpendek antara dua buah simpul tertentu di dalam graf (single pair shortest path). Persoalan ini bisa jadi merupakan analogi dari beberapa persoalan populer yang tercantum di abstrak makalah.

 

2. PENJELASAN MENGENAI ALGORITMA DIJKSTRA DAN FLOYDWARSHALL

 

2.1 Algoritma Dijkstra

Algoritma Dijkstra ditemukan oleh ilmuwan komputer Edsger Dijkstra dan merupakan salah satu varian dari algoritma greedy, yaitu salah satu bentuk algoritma populer dalam pemecahan persoalan yang terkait dengan masalah optimasi. Sifatnya sederhana dan lempang (straightforward). Sesuai dengan artinya yang secara harfiah berarti tamak atau rakus – namun tidak dalam konteks negatif –, algoritma greedy ini hanya memikirkan solusi terbaik yang akan diambil pada setiap langkah tanpa memikirkan konsekuensi ke depan. Prinsipnya, ambillah apa yang bisa Anda dapatkan saat ini (take what
you can get now!), dan keputusan yang telah diambil pada setiap langkah tidak akan bisa diubah kembali. Intinya algoritma greedy ini berupaya membuat pilihan nilai optimum lokal pada setiap langkah dan berharap agar nilai optimum lokal ini mengarah kepada nilai optimum global.

 

 

 

 

 

Elemen-elemen penyusun algoritma greedy adalah:

 

1. Himpunan kandidat, C

Himpunan ini berisi elemen-elemen yang memiliki peluang untuk membentuk solusi. Pada persoalan lintasan terpendek dalam graf, himpunan kandidat ini adalah himpunan simpul pada graf tersebut.

 

2. Himpunan solusi, S

Himpunan ini berisi solusi dari permasalahan yang diselesaikan dan elemennya terdiri dari elemen dalam himpunan kandidat namun tidak semuanya atau dengan kata lain himpunan solusi ini adalah upabagian dari himpunan kandidat.

 

3. Fungsi seleksi

    Fungsi seleksi adalah fungsi yang akan memilih setiap kandidat yang yang memungkinkan untuk menghasilkan solusi optimal pada setiap langkahnya.

 

4. Fungsi kelayakan

Fungsi kelayakan akan memeriksa apakah suatu kandidat yang telah terpilih (terseleksi) melanggar constraint atau tidak. Apabila kandidat melanggar constraint maka kandidat tidak akan dimasukkan ke dalam himpunan solusi.

 

5. Fungsi objektif

Fungsi objektif akan memaksimalkan atau meminimalkan nilai solusi. Tujuannya adalah

memilih satu saja solusi terbaik dari masing-masing anggota himpunan solusi.

 

2.1.1 Analisis Algoritma Dijkstra

    Ada beberapa kasus pencarian lintasan terpendek yang diselesaikan menggunakan algoritma Dijkstra, yaitu: pencarian lintasan terpendek antara dua buah simpul tertentu (a pair shortest path), pencarian lintasan terpendek antara semua pasangan simpul (all pairs
shortest path), pencarian lintasan terpendek dari simpul tertentu ke semua simpul yang lain (single-source shortest
path), serta pencarian lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu (intermediate shortest path).

 

Penggunaan strategi greedy pada algoritma Dijkstra adalah:

Pada setiap langkah, ambil sisi berbobot minimum yang menghubungkan sebuah simpul yang sudah terpilih dengan sebuah simpul lain yang belum terpilih. Lintasan dari simpul asal ke simpul yang baru haruslah merupakan lintasan yang terpendek di antara semua lintasannya ke

simpul-simpul yang belum terpilih.

 

KESIMPULAN

1. Algoritma Dijkstra yang menerapkan prinsip greedy tidak selalu berhasil memberikan solusi optimum
   untuk kasus penentuan lintasan terpendek (single pair shortest path).
   

   
    

2. Untuk metode djiktra margonda ke semanggi yang dilihat dari jarak maka kita mengambil
   

   jalur :
   

   Margonda – UI - Kelapa dua - Kampung Rambutan - Pancoran- LIPI – Komdak –P.Semanggi. Karena, jarak pertama yang kita lihat lebih dekat melewati arah kelapa dua.
   

Untuk metode djiktra margonda ke semanggi yang dilihat dari biaya maka kita mengambil cara yang pertama, yaitu menggunakan P54. Karena, biaya yang dikeluarkan lebih terjangkau dan murah. Selain itu, hanya dengan sekali naik angkutan umum.

 

Sumber     : ringkasan materi Struktur Organisasi Data