Graf berbobot dan lintasan terpendek – algoritma Dijkstra

Yang ditunjukkan

Jaringan jalan dapat dimodelkan sebagai graf berbobot: titik adalah lokasi, sisi adalah jalan, dan setiap bobot adalah jarak dalam kilometer. Algoritma Dijkstra mencari lintasan terpendek dari titik awal dengan memberi label jarak sementara pada setiap titik: pada tiap langkah, titik belum tetap dengan label terkecil ditetapkan, lalu label tetangganya diperbarui. Karena semua bobot positif, label yang sudah tetap tidak dapat diperbaiki lagi. Simulasi juga menampilkan derajat titik, yang jumlahnya dua kali banyak sisi dan yang, pada graf terhubung, menentukan ada tidaknya lintasan serta sirkuit Euler.

Cara menggunakan

Pilih Peta, lalu tentukan titik awal dan tujuan pada Dari dan Ke. Tekan Langkah berikut berulang kali dan minta siswa menebak titik mana yang akan ditetapkan serta label mana yang berubah; gunakan Langkah sebelumnya untuk meninjau suatu keputusan. Bandingkan rute akhir dengan rute yang melewati jalan paling sedikit. Kemudian atur Klik sisi untuk ke tutup / buka jalan, tutup satu jalan pada lintasan terpendek, dan tekan Jalankan semua untuk melihat rute baru.

Parameter yang dapat diubah

• Peta Kota (7 lokasi), Kabupaten di provinsi (9 lokasi)
• Titik awal
• Titik akhir

Pertanyaan untuk dijelajahi

1. Mengapa label suatu titik tidak pernah berubah lagi setelah ditetapkan?
2. Apakah rute dengan sisi paling sedikit selalu merupakan rute terpendek? Contoh mana pada peta yang menunjukkannya?
3. Jalan mana yang dapat Anda tutup agar jalan yang tersisa tetap terhubung dan graf memiliki sirkuit Euler?