Algoritma Bellman-Ford

2.1.3. Algoritma Bellman-Ford 

Algoritma Bellman-Ford merupakan algoritma untuk mencari shortest path,dengan menghitung jarak terpendek pada sebuah diagraf berbobot, atau menghitung semua jarak terpendek yang berawal dari satu titik node.

Langkah-langkah:

1.Tentukan vertex source dan daftar seluruh vertices maupun edges.

2.Assign nilai untuk distance dari vertex source = 0, dan yang lain infinite

3.Mulailah iterasi terhadap semua vertices yang dimulai dari vertex source,

4.Untuk menentukan distance dari semua vertices yang berhubungan dengan vertex source dengan formula seperti berikut ini :

- U = vertex asal

- V = vertex tujuan

- UV = Edges yang menghubungkan U dan V

- Jika distance V, lebih kecil dari distance U + weight UV maka distance V, diisi dengan distance U + weight UV

- Lakukan hingga semua vertices terjelajahi

5.Untuk mengecek apakah ada negative cycle dalam graf tersebut lakukan iterasi untuk semua edges yang ada, kemudia lakukan pengecek an seperti dibawah ini :

6.Untuk semua edges UV, jika ada distance vertex U + weight edges UV kurang dari distance vertex V maka sudah jelas bahwa graf tersebut memiliki negative cycle.

Contoh :

Dari graph di atas tentukan lintasan terpendek dari titik 1 ke titik 4.

Langkah-langkah:

1.Tahap pertama adalah tahap inisialisasi yaitu dengan melabeli titik awal atau titik asal yaitu titik 1 dengan 0 dan titik-titik lainnya dengan ∞.d(1,1) ← 0 untuk masing-masing v anggota V

 – {s} maka d (s,v) ← ∞

 2.Tahap kedua yaitu tahap proses iterasi

Untuk masing-masing sisi (1,2) anggota E maka

Jika d(1,2) > d(1,2)+w(2,3) maka

d(1,2) diganti dengan d(1,2)+w(2,3)

Akhirnya diperoleh d(1,4)=5+4+4=13.

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.

kali ini saya akan membahas algoritma struktur data mengenai graph,langsung ajja d baca gan,semoga bermanfat...

Graph

Graf adalah kumpulan simpul (nodes) yang dihubungkan satu sama lain dengan garis atau busur (edge).

Suatu Graf terdiri dari dua himpunan yaitu himpunan V dan E :

a. Verteks (simpul) adalah himpunan simpul yang terbatas dan tidak kosong.

b. Edge (Sisi/busur) adalah himpunan busur yang menghubungkan sepasang simpul.

Simpul-simpul pada graf adalah suatu obyek yang mewakili suatu kota atau tempat dan sebagainya. Busur dapat mewakili obyek seperti, jalan raya,sambungan telepon, dan lain-lain. Menurut arah dan beban yang dimiliki oleh busur,maka Graf dibedakan sebagai berikut:

a. Graf berarah dan berbobot tiap busur mempunyai anak panah dan bobot.

Lihat contoh gambar 1.1.

Gambar 1.1 Graf Berarah dan Berbobot

b. Graf tidak berarah dan berbobot

busur tidak mempunyai panah, tetapi tetap memiliki bobot atau beban pada setiap busurnya.

Lihat contoh gambar 1.2.

                  Gambar 1.2. Graf tidak berarah dan berbobot

c. Graf berarah dan tidak berbobot Busur memiliki arah, tetapi tidak memiliki bobot atau beban pada setiap busurnya.

Lihat contoh gambar 1.3.

Gambar berarah dan tidak berbobot

d. Graf tidak berarah dan tidak berbobot Busur tidak memiliki arah dan tidak memiliki bobot pada setiap busurnya.

Lihat contoh gambar 2.4.

Gambar tidak berarah dan tidak berbobot