"Agar (d[e[j].a] < INF)" tekshiruvi faqat grafik manfiy og'irlikdagi qirralarni o'z ichiga olgan taqdirdagina kerak bo'ladi: bunday tekshiruvsiz yo'l hali topilmagan cho'qqilardan bo'shashishlar sodir bo'ladi, va shaklning noto'g'ri masofalari \ infty - 1, \infty - 2 va hokazo. - "Agar (d[e[j].a] < INF)" tekshiruvi faqat grafik manfiy og'irlikdagi qirralarni o'z ichiga olgan taqdirdagina kerak bo'ladi: bunday tekshiruvsiz yo'l hali topilmagan cho'qqilardan bo'shashishlar sodir bo'ladi, va shaklning noto'g'ri masofalari \ infty - 1, \infty - 2 va hokazo.
- Yaxshilangan amalga oshirish
- Ushbu algoritmni biroz tezlashtirish mumkin: ko'pincha javob bir necha bosqichda topiladi va qolgan bosqichlar hech qanday foydali ish qilmaydi, faqat barcha qirralar behuda ko'rib chiqiladi. Shuning uchun, biz joriy bosqichda biror narsa o'zgarganmi yoki yo'qmi, bayroqni saqlaymiz va agar biron bir bosqichda hech narsa sodir bo'lmagan bo'lsa, u holda algoritmni to'xtatish mumkin. (Ushbu optimallashtirish asimptotikani yaxshilamaydi, ya'ni ba'zi grafiklarda barcha n-1 fazalari kerak bo'ladi, lekin "o'rtacha", ya'ni tasodifiy grafiklarda algoritmning harakatini sezilarli darajada tezlashtiradi.) Bunday optimallashtirish bilan algoritmning bosqichlari sonini n-1 raqamiga qo'lda cheklash umuman keraksiz bo'lib qoladi - kerakli fazalar sonidan keyin u o'zini to'xtatadi.
Yo'lni tiklash Keling, Ford-Bellman algoritmini qanday o'zgartirish mumkinligini ko'rib chiqaylik, shunda u nafaqat eng qisqa yo'llarning uzunligini topadi, balki eng qisqa yo'llarning o'zini tiklashga imkon beradi. Buning uchun yana bir p[0 \ldots n-1] massivini yaratamiz, unda har bir cho'qqi uchun uning "ajdodini" saqlaymiz, ya'ni. unga olib boradigan eng qisqa yo'lda oxirgidan oldingi cho'qqi. Haqiqatan ham, a cho'qqisiga eng qisqa yo'l, oxiriga a cho'qqisi qo'shilgan ba'zi bir p[a] cho'qqisiga eng qisqa yo'ldir. - Yo'lni tiklash Keling, Ford-Bellman algoritmini qanday o'zgartirish mumkinligini ko'rib chiqaylik, shunda u nafaqat eng qisqa yo'llarning uzunligini topadi, balki eng qisqa yo'llarning o'zini tiklashga imkon beradi. Buning uchun yana bir p[0 \ldots n-1] massivini yaratamiz, unda har bir cho'qqi uchun uning "ajdodini" saqlaymiz, ya'ni. unga olib boradigan eng qisqa yo'lda oxirgidan oldingi cho'qqi. Haqiqatan ham, a cho'qqisiga eng qisqa yo'l, oxiriga a cho'qqisi qo'shilgan ba'zi bir p[a] cho'qqisiga eng qisqa yo'ldir.
Do'stlaringiz bilan baham: |
