shortest path (lintasan terpendek)

kali ini kita akan membahas tentang shortest path,langsung d baca ajja gan...

2.1. Lintasan Terpendek (Shortest Path)

            Shortest path adalah pencarian rute atau path terpendek antara node yang ada pada graph.biaya (cost) yang dihasilkan adalah minimum.

 Lintasan terpendek  merupakan salah satu masalah yang dapat diselesaikan dengan menggunakan graph. Jika diberikan sebuah graph berbobot, masalah lintasan terpendek adalah bagaimana kita mencari sebuah jalur pada graph yang meminimumkan jumlah bobot sisi pembentuk jalur tersebut.

Algoritma-Algoritma dalam Shortest Path ada beberapa macam yaitu :

2.1.1. Algoritma Greedy

 Algoritma Greedy  adalah algoritma yang memecahkan masalah langkah demi langkah, pada setiap langkah dilakukan dengan cara: 

1.Mengambil pilihan yang terbaik yang dapat diperoleh saat itu

2.Berharap bahwa dengan memilih optimum local pada setiap langkah akan mencapai optimum global

Langkah-langkah algoritma greedy :

1.Menentukan titik awal dan titik tujuan, misalnya titik awal a.

2.Perikasa semua sisi yang langsung bersisian dengan titik a. Pilihsisi yang bobotnya terkecil. Sisi ini menjadi lintasan terpendek pertama, sebut saja L(1).

3.Tentukan lintasan terpendek kedua dengan cara berikut:

4.Hitung: d(i) = panjang L(1) + bobot sisi dari simpul akhir L(1) kesimpul i yang lain.

5.Pilih d(i) yang terkecil.

6.Bandingkan d(i) dengan bobot sisi (a, i). Jika bobot sisi (a, i) lebihkecil daripada d(i), maka L(2) = L(1) U (sisi dari simpul akhir L(i)ke simpul i)

7.Dengan cara yang sama, ulangi langkah 2 untuk menentukanlintasan terpendek berikutnya.

- Kelebihan algoritma Greedy:

Prinsip pencarian lintasan terpendek memakai fungsi ” Seleksi” dan itu berguna untuk menentukan jalan tersingkat untuk menuju suatu tempat.Sehingga, kita dapat sampai tepat waktu menuju tempat tujuan. Hasil analisis berdasarkan bobot-bobot yang berbeda, menunjukkan bahwa semakin banyak bobot yang diberikan, maka semakin akurat pula datayang dihasilkan. Sehingga menghasilkan waktu yang efisien.

-Kekurangan algoritma Greedy:

 1.Algoritma greedy tidak beroperasi secara menyeluruh terhadap semua alternatif solusi yang ada (sebagaimana pada metode exhaustive search). 

2.Pemilihan fungsi SELEKSI: Mungkin saja terdapat beberapa fungsi SELEKSI yang berbeda, sehingga kita harus memilih fungsi yang tepat jika kita ingin algoritma bekerja dengan benar dan menghasilkan solusi yang benar-benar optimum. Karena itu, pada sebagian masalah algoritma

Greedy tidak selalu berhasil memberikan solusi yang benar-benar optimum.

Contoh :

Permasalahan :

“Carilah jalur terpendek dari titik kuning ke titik biru” Pilihan awal yang dipilih algoritma adalah a karena a lebih pendek daripada d. Pilihan selanjutnya hanya satu sehingga tidak ada pilihan lainselain b. Lalu ke c dan ke tujuan akhir. Maka jaraknhya adalah 10,5Padahal jika menggunakan jalur satu lagi sebesar 7. Begitu seterusnya Jika jarak a ke b adalah 1000. Algoritma ini tidak bisa mundur, sehinggamemilih b. Padahal nilainya sangat besar. Disanalah kelemahan algoritmaini. Tetapi dengan tidak pernah mundur ke tempat awal untuk mencari jalan alternatif. Algoritma ini cepat dalam menyelesain pencarian lintasan tercepat.

2.1.2 Algoritma Djikstra

            Algoritma Dijkstra, dinamai menurut penemunya, Edsger Dijkstra,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 (straight-forward). 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.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).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.

Langkah-langkah dalam menentukan lintasan terpendek pada algoritma Dijkstra yaitu:

1.Pada awalnya pilih titik dengan bobot yang terendah dari titik yang belum terpilih, diinisialisasikan dengan „0‟ dan yang sudah terpilih diinisialisasikan dengan „1‟.

 2.Bentuk tabel yang terdiri dari titik, status, bobot dan predecessor.Lengkapi kolom bobot yang diperoleh dari jarak titik sumber ke semua titik yang langsung terhubung dengan titik sumber tersebut.

3.Jika titik sumber ditemukan maka tetapkan sebagai titik terpilih.

4.Tetapkan titik terpilih dengan label permanen dan perbarui titik yang langsung terhubung.

5.Tentukan titik sementara yang terubung pada titik yang sudah terpilih sebelumnya dan merupakan bobot terkecil dilihat dari table dan tentukan sebagai titik terpilih berikutnya.

6.Apakah titik yang tepilih merupakan titik tujuan? Jika ya, maka kumpulan titik terpilih atau predecessor merupakan rangkaian yang menunjukkan lintasan terpendek.

7.Begitu seterusnya sampai semua titik terpilih

Contoh :

Dari graph diatas tentukan lintasan terpendek dari titik A ke titik F !Dengan menggunakan program, diperoleh lintasan terpendek dari titk A ketitik F sebagai berikut .

Diperoleh lintasan terpendek yaitu A-E-D-F dengan bobot total sebesar 22.