Tugas/Ujian Sains Komputasi: Algoritma dan Perancangan Software - Tugas IV
TASK 1
Soal
Jalankan Bellman-Ford Algorithm dengan titik
sebagai titik awal!
Jawab
Langkah I
Jika kita bermula dari titik
, kita hanya punya dua
pilihan:
atau
.
Langkah II
Dari titik bisa ke
atau
. Sedangkan dari
hanya bisa ke
.
Perhatikan bahwa dari
akan menghasilkan
nilai 8 sedangkan dari
akan menghasilkan
nilai 5. Oleh karena itu kita tidak akan memilih
.
Langkah III
Dari kita hanya bisa
memilih ke
, sehingga
akan menghasilkan
nilai 6. Nilai ini lebih rendah daripada jalur
sebelumnya.
Sehingga kita akan menghapus alternatif rute
yang telah ada.
Langkah IV
Langkah berikutnya sudah jelas, tinggal menyelesaikan dari
ke
saja.
Kesimpulan
Rutenya adalah z-s-y-x-t.
TASK 2
Soal
Jalankan Bellman-Ford Algorithm dengan titik
sebagai titik awal!
Jawab
Langkah I
Dari titik kita bisa
pergi ke titik
dan
titik
.
Langkah II
Dari titik kita bisa
pergi ke titik
dan
titik
. Namun
akan menghasilkan
nilai 14, nilai tersebut lebih besar dibandingkan rute existing dari
sehingga kita
akan abaikan rute ini. Rute
menghasilkan
nilai 11.
Dari titik kita bisa
pergi ke
dan titik
. Rute
menghasilkan
nilai 4. Kalau dibandingkan dengan rite
, nilai rute
lebih rendah
sehingga kita akan abaikan rute
.
Sedangkan akan
menghasilkan nilai 16.
Langkah III
Dari titik kita tidak
mungkin kembali ke
dan
ke
karena nilai yang
sudah ada sekarang masih lebih rendah dari rute yang baru. Sehingga
secara jelas, kita hanya bisa memilih rute
lalu
.
Kesimpulan
Kita dapatkan bahwa ada negative cycle. Hal ini tidak boleh terjadi, jika kita teruskan kembali prosesnya, tidak akan konklusif sehingga terjadi endless looping.
Rutenya: Tidak ditemukan.
if you find this article helpful, support this blog by clicking the ads.