Jalur Terpendek: 20 Sisi
fx-50FH II · CMPLX · 637 bytes
Cari satu jalur berbiaya minimum dalam jaringan tak berarah dengan paling banyak sepuluh simpul dan 20 sisi; tampilkan simpul berurutan, lalu biaya total.
- 637 byte
- Mode CMPLX
Contoh soal dan pembahasan
Contoh 1
Latihan riset operasi universitas orisinal: robot museum bergerak antarruang bernomor. Hubungan dua arah dan biayanya dalam menit. Cari jalur waktu minimum dari 2 ke 6 dan waktu totalnya.
Semua sisi tak berarah; hubungan yang tidak tercantum tidak ada. Daftar (a–b: biaya): 2–1: 7; 2–3: 4; 1–4: 5; 3–4: 2; 3–5: 8; 4–6: 3; 5–6: 2; 1–5: 12
Jawaban
Penyelesaian standar (tanpa kalkulator)
- Terapkan Dijkstra dari S. u adalah simpul baru yang ditetapkan, d(v) jarak sementara terbaru, dan ∞ berarti belum terjangkau.
- u=2, d(2)=0; d(1)=7, d(3)=4
- u=3, d(3)=4; d(4)=6, d(5)=12
- u=4, d(4)=6; d(6)=9
- u=1, d(1)=7; ∅
- u=6, d(6)=9; d(5)=11
- Telusuri pendahulu dan jumlahkan langsung biaya jalur: 2 → 3 → 4 → 6; Biaya total 4+2+3=9 min
Contoh 2
Latihan riset operasi universitas orisinal: jaringan antar-jemput pameran memakai satuan tarif bulat. Hubungan 7–8 gratis, dengan biaya tepat 0. Cari jalur tarif minimum dari 7 ke 2 dan tarif totalnya.
Semua sisi tak berarah; hubungan yang tidak tercantum tidak ada. Daftar (a–b: biaya): 7–8: 0; 8–9: 3; 9–2: 4; 7–1: 9; 1–2: 2; 8–2: 10; 9–1: 1
Jawaban
Penyelesaian standar (tanpa kalkulator)
- Terapkan Dijkstra dari S. u adalah simpul baru yang ditetapkan, d(v) jarak sementara terbaru, dan ∞ berarti belum terjangkau.
- u=7, d(7)=0; d(1)=9, d(8)=0
- u=8, d(8)=0; d(2)=10, d(9)=3
- u=9, d(9)=3; d(1)=4, d(2)=7
- u=1, d(1)=4; d(2)=6
- u=2, d(2)=6; ∅
- Telusuri pendahulu dan jumlahkan langsung biaya jalur: 7 → 8 → 9 → 1 → 2; Biaya total 0+3+1+2=6
Contoh 3
Latihan riset operasi universitas orisinal: jaringan komunikasi pelatihan menghubungkan sepuluh terminal virtual. Setiap hubungan dua arah memiliki biaya transmisi bulat tetap. Masukkan semua 20 hubungan sesuai urutan, termasuk yang terakhir, dan cari jalur biaya minimum dari 1 ke 10 serta totalnya.
Semua sisi tak berarah; hubungan yang tidak tercantum tidak ada. Daftar (a–b: biaya): 1–2: 5; 2–3: 7; 3–4: 4; 4–5: 6; 5–6: 3; 6–7: 8; 7–8: 2; 8–9: 5; 9–10: 4; 1–6: 9; 2–7: 9; 3–8: 9; 4–9: 9; 5–10: 9; 2–9: 1; 1–4: 1; 4–7: 1; 7–10: 1; 1–8: 9; 3–10: 8
Jawaban
Penyelesaian standar (tanpa kalkulator)
- Terapkan Dijkstra dari S. u adalah simpul baru yang ditetapkan, d(v) jarak sementara terbaru, dan ∞ berarti belum terjangkau.
- u=1, d(1)=0; d(2)=5, d(4)=1, d(6)=9, d(8)=9
- u=4, d(4)=1; d(3)=5, d(5)=7, d(7)=2, d(9)=10
- u=7, d(7)=2; d(8)=4, d(10)=3
- u=10, d(10)=3; d(9)=7
- Telusuri pendahulu dan jumlahkan langsung biaya jalur: 1 → 4 → 7 → 10; Biaya total 1+1+1=3
Kapan digunakan
Matematika universitas · riset operasi. Untuk jaringan tetap dengan biaya nonnegatif yang dapat dijumlahkan. Tidak menentukan arah fisik atau kondisi perjalanan secara otomatis.
Masukkan jaringan
- Pada Y? pertama, masukkan S+Ti: S simpul awal dan T tujuan. Lalu bergantian Y? = a+bi untuk sisi tak berarah dan M? = biayanya. Gunakan ENG untuk i. Tidak perlu memasukkan jumlah simpul atau sisi.
- Akhiri dengan EXE saja pada Y? berikutnya, lalu EXE saja pada M?. Keduanya adalah pertanyaan berbeda. Biaya nol yang diketahui harus diisi 0EXE.
Baca jalur dan biaya
- Setiap layar Disp adalah satu simpul jalur mulai S. Tekan EXE setelah setiap simpul, termasuk T, untuk mencapai biaya akhir. −1 berarti tidak ada jalur. S=T menampilkan S lalu 0. Keluar dengan AC; EXE menjalankan ulang.
Syarat dan batas
- Nomor simpul bilangan bulat 1–10, biaya sisi bilangan bulat 0–100, paling banyak 20 sisi bukan gelang. Sisi paralel masing-masing memakai satu slot. Semua biaya memakai satuan sama.
- Versi 20 sisi memeriksa bilangan bulat dan rentang ujung serta biaya. Satu kolom kosong, nilai tidak sah, atau sisi tambahan menyebabkan Math ERROR. Gelang sah diabaikan sebelum penuh; setelah penuh hanya pasangan kosong dapat mengakhiri masukan.
- Program memakai 637 dari 680 bytes bersama, menyisakan 43 bytes untuk slot lain. Setiap eksekusi menghapus A, B, C, D, X, Y, M dan Ans; simpan nilai penting terlebih dahulu.
- Buat dan jalankan dalam CMPLX, a+bi, Norm 1. Contoh memakai Deg dan P1. Selesai normal memulihkan Norm 1. i menggabungkan dua label bulat, bukan biaya imajiner.
- Sisi berarah, bobot negatif, dan lebih dari sepuluh simpul tidak didukung. Hanya satu jalur diberikan saat seri, tanpa jaminan jumlah sisi paling sedikit. Pertahankan kode persis karena margin presisinya sempit.
Memeriksa akses…