18. Diberikan graf dengan 10 simpul sebagai berikut:
Dari graf di samping (graf tidak berarah), berapakah jarak terkecil yang dapat ditempuh dari simpul 6 ke simpul 9?
Pembahasan Soal OSP Komputer Informatika 2019 no 18.
Pertama anggap jalur antara 3 simpul lurus tanpa cabang sebagai 1 jalur contoh 6-5-3
6-5-3=7 disingkat 6-3
6-7-4=8 disingkat 6-4
3-8-10=6 disingkat 3-10
3-1-2=13 disingkat 3-2
Jawaban singkat:
Dari 6 ke 9 melewati 10 atau 2 sehingga hitung jalur 6 ke 10 dan 6 ke 2 dengan tidak melewati simpul lainnya (contoh 6 ke 10 tidak boleh melalui 2. Disini didapat jarak terpendek 6 ke 10 (6-3-10) bernilai 13 dan jalur terpendek 6 ke 2 (6-4-2) bernilai 14. Selanjutnya dari 10 ke 9 terpendek adalah 2 dengan total 15 dan dari 2 ke 9 terpendek 4 (2-10-9) dengan total 18. Sehingga dapat disimpulkan jalur terpendek 6-3-10-9 dengan total 15.
Jawaban lebih rinci:
Simpul awal 6 memiliki 2 jalur ke 3 dan 4. 6-3 bernilai 7 dan 6-4 bernilai 8. Karena 6-3 lebih pendek pilih untuk sementara.
Selanjutnya karena ada jalur 6-4-3 untuk memastikan hitung jalur terpendek sehingga didapat 6-3 sebagai terpendek.
Dari 3 bercabang 3 yang terpendek 3-4 bernilai 3 sehingga total 10. Karena jarak 6-3-4 lebih jauh dari 6-4 maka cabang 3-4 keluar. Selanjutnya cabang terpendek ke dua 3-10 bernilai 6 dengan total 13.
Selanjutnya kembali ke 6-4 bercabang ke 3 dan 2. Karena total jarak cabang ke 3 lebih jauh dari 6-3 maka cabang ke 3 keluar. Kemudian total 6-4-2 bernilai 14.
Dari 2 bercabang ke 10 dan 9. Jika memilih cabang 10 maka didapat total 16. Karena 16 lebih besar dari 13 (6-3-10) cang ini keluar. Sehingga hanya bisa menggunakan cabang 9 dengan total 6-4-2-9 bernilai 19.
Selanjutnya tersisa jalur 6-3-10 yang cabang terpendek ke 9 bernilai 2 sehingga total 6-3-10-9 bernilai 15.
Jadi jarak terpendek simpul 6 ke simpul 9 adalah 15 dengan jalur 6-5-3-8-10-9.
0 komentar:
Post a Comment