Algoritma dijkstra dengan Strategi Greedy

Algoritma dijkstra adalah salah satu metode untuk memecahkan masalah pencarian rute terpendek. Algoritma ini biasanya diterapkan pada sebuah aplikasi pencari rute jalan yang terdeklat dari suatu daerah ke daerah lain.

Strategi greedy:

  Lintasan dibentuk satu per satu. Lintasan berikutnya yang dibentuk ialah lintasan yang meminimumkan jumlah jaraknya. 

Contoh Soal : 

Jawaban :

Strategi greedy:

  Pada setiap langkah, ambil sisi yang 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 diantara semua lintasannya ke simpul-simpul yang belum terpilih.