Algoritma Greedy untuk Menentukan Jalur Terpendek

Algoritma Greedy untuk Menentukan Jalur Terpendek. Disini saya akan membahas bagaimana cara menentukan jalur terpendek. Banyak algoritma yang bisa digunakan untuk menyelesaikan persoalan ini, contohnya greedy, dynamic programming (forward, backward), dan djikstra. Kali ini saya akan membahas bagaimana menggunakan algoritma greedy. Untuk algoritma lain akan saya bahas pada pertemuan selanjutnya.

Algoritma greedy bukanlah mendapatkan solusi paling optimum, karena tidak menghitung keseluruhann dari total nilai yang ada. Akan tetapi greedy merupakan algoritma jalur terpendek yang layak diterima.

Disini saya contohkan graph yang telah saya sediakan, lihat gambar di bawah ini :

Algoritma Greedy untuk Menentukan Jalur Terpendek

Baiklah yang pertama dibahas adalah bagaimana cara kerja algoritma greedy.

Cara kerja algoritma greedy :

1. Tentukan node awal dan node tujuan
2. Lakukan berulang-ulang :
1. Menentukan kandidat : periksa semua sisi yang terhubung langsung dengan node awal
2. Menentukann kandidat solusi 
• Pilih sisi dengan bobot yang paling kecil 
• Hitung panjang lintasan sementara
3. Menentukan solusi terpilih 
• Cek node akhir <> node tujuan
• set node awal = node akhir terpilih
3. Lakukan tahap no. 2 sampai node tujuan ketemu.

Itulah langkah untuk membuat algoritma greedy. Kita akan coba menyelesaikan contoh soal gambar diatas. Kita misalkan node awal kita adalah A, dan node tujuan adalah L

1. Tentukan node awal : A
Tentukan node tujuan : L

2. Looping	Menentukan Kandidat	Menentukan kandidat solusi	Node Akhir	Node Awal	Solusi Terpilih
   1	A-B : 7 A-C : 6 A-D : 5 A-E : 9	Jalur : A-D D(1) = 0 + 5 = 5	D	D	D
   2	D-H : 9	Jalur : D-H D(2) = 0 + 5 = 5D(2) = 5 + 9 = 14	H	H	H
   3	H-J : 10 H-K : 8	Jalur : H - K D(3) = 14 + 8 = 22	K	K	K
   4	K-L : 11	Jalur : K-L D(4) = 22 + 11 = 33	L	-	L

3. Jalur Terpendek : A - D - H - K - L
Dengan Panjang lintasan adalah 33.

Seperti inilah kira-kira cara penyelesaian algoritma greedy. Jika anda kurang paham silahkan tinggalkan komentar, atau bisa langsung menanyakan dengan mengirim ke email saya.

Terima kasih telah membaca Artikel Algoritma Greedy untuk Menentukan Jalur Terpendek . Jika Anda ingin Copy Paste Artikel ini, Harap cantumkan Link Algoritma Greedy untuk Menentukan Jalur Terpendek sebagai sumbernya.
<a href="http://akbartn.blogspot.com/2015/11/algoritma-greedy-untuk-menentukan-jalur.html">Algoritma Greedy untuk Menentukan Jalur Terpendek</a>

Artikel Terkait