Boshqacha qilib aytganda, har qanday a cho'qqi uchun unga eng qisqa yo'ldagi qirralarning sonini k bilan belgilaymiz (agar shunday yo'llar bir nechta bo'lsa, istalgan birini olish mumkin). Keyin bu bayonotda aytilishicha, k fazadan keyin bu eng qisqa yo'lni topish kafolatlanadi. - Boshqacha qilib aytganda, har qanday a cho'qqi uchun unga eng qisqa yo'ldagi qirralarning sonini k bilan belgilaymiz (agar shunday yo'llar bir nechta bo'lsa, istalgan birini olish mumkin). Keyin bu bayonotda aytilishicha, k fazadan keyin bu eng qisqa yo'lni topish kafolatlanadi.
- Isbot. Ixtiyoriy a cho'qqisini ko'rib chiqaylik, unga v boshlang'ich cho'qqisidan yo'l bor va unga eng qisqa yo'lni ko'rib chiqaylik: (p_0=v, p_1, \ldots, p_k=a). Birinchi bosqichdan oldin p_0=v cho'qqisiga eng qisqa yo'l to'g'ri topilgan. Birinchi bosqichda chekka (p_0,p_1) Ford-Bellman algoritmi bo'yicha skanerdan o'tkazildi, shuning uchun birinchi bosqichdan keyin p_1 cho'qqigacha bo'lgan masofa to'g'ri hisoblab chiqilgan. Bu gaplarni k marta takrorlasak, k-fazadan keyin p_k=a cho'qqigacha bo'lgan masofa to'g'ri hisoblanganligini bilib olamiz, buni isbotlash kerak edi.
E'tiborga olish kerak bo'lgan oxirgi narsa shundaki, har qanday eng qisqa yo'lning n-1 dan ortiq qirralari bo'lishi mumkin emas. Shuning uchun algoritm faqat n-1 fazalarni hosil qilishi kifoya. Shundan so'ng, biron bir dam olishning biron bir cho'qqigacha bo'lgan masofani yaxshilash bilan yakunlanishi kafolatlanmaydi. - E'tiborga olish kerak bo'lgan oxirgi narsa shundaki, har qanday eng qisqa yo'lning n-1 dan ortiq qirralari bo'lishi mumkin emas. Shuning uchun algoritm faqat n-1 fazalarni hosil qilishi kifoya. Shundan so'ng, biron bir dam olishning biron bir cho'qqigacha bo'lgan masofani yaxshilash bilan yakunlanishi kafolatlanmaydi.
Salbiy sikl holati Yuqorida, biz hamma joyda grafikda salbiy tsikl yo'q deb taxmin qildik (aniqlik uchun, biz v boshlang'ich cho'qqisidan erishish mumkin bo'lgan salbiy tsiklga qiziqamiz va erishib bo'lmaydigan tsikllar yuqoridagi algoritmda hech narsani o'zgartirmaydi). Agar u mavjud bo'lsa, qo'shimcha qiyinchiliklar ushbu tsikldagi barcha cho'qqilargacha bo'lgan masofalar, shuningdek, ushbu tsikldan erishish mumkin bo'lgan cho'qqilargacha bo'lgan masofalar aniqlanmaganligi sababli yuzaga keladi - ular minus cheksizlikka teng bo'lishi kerak. - Salbiy sikl holati Yuqorida, biz hamma joyda grafikda salbiy tsikl yo'q deb taxmin qildik (aniqlik uchun, biz v boshlang'ich cho'qqisidan erishish mumkin bo'lgan salbiy tsiklga qiziqamiz va erishib bo'lmaydigan tsikllar yuqoridagi algoritmda hech narsani o'zgartirmaydi). Agar u mavjud bo'lsa, qo'shimcha qiyinchiliklar ushbu tsikldagi barcha cho'qqilargacha bo'lgan masofalar, shuningdek, ushbu tsikldan erishish mumkin bo'lgan cho'qqilargacha bo'lgan masofalar aniqlanmaganligi sababli yuzaga keladi - ular minus cheksizlikka teng bo'lishi kerak.
Do'stlaringiz bilan baham: |
