Yashiklar prinsipi

3- итерация. Бошланғич учи тўпламга тегишли, охири эса тўпламга тегишли бўлган ёйлар тўртта: , , ва . Шу ёйларга мос нинг қийматлари , , , ва, шунинг учун, бўлади. Демак, бу итерацияда ёйни ажратамиз ва деб оламиз. Энди, алгоритмга кўра, ва тўпламларни ҳосил қиламиз.
Иккала учи ҳам тўпламга тегишли бўлган ёйлар олтита: , , , , ва . Бу ёйларнинг ҳар бири учун тенгсизликнинг бажарилишини текширишимиз керак. Лекин, 1- ва 2- итерацияларда , ва ёйлар учун бу иш бажарилганлиги сабабли текширишни таркибида белгили уч қатнашган , ва ёйлар учун амалга ошириб, қуйидагиларга эга бўламиз: ёй учун муносабат тўғри ( ), ёй учун муносабат тўғри ( ), лекин ёй учун муносабат нотўғри ( ). Охирги муносабатни ҳисобга олиб, алгоритмга кўра ўрнига деб оламиз ва ёйни ажратилган деб, илгари ажратилган ёйни эса ажратилмаган деб ҳисоблаймиз (3- шаклда ёзувнинг ва ёйнинг қалин чизиқъи устига ажратилганликни инкор қилувчи белгиси қўйилган).
4- итерация. , бўлгани учун ва , , , ҳамда бўлади. Демак, ва ёйларни ажратамиз ҳамда 4 белгили учга қийматни мос қўямиз. Натижада , тўпламларга эга бўламиз.


муносабатнинг тўғрилиги , , , , ва ёйлар учун текширилиб кўрилганда, унинг барча ёйлар учун бажарилиши маълум бўлади.
5- итерация. Энди бўлгани учун , , ва бўлади. Бу ерда минимум ёйда эришилгани учун уни ажратиб, орграфнинг охирги белгили учига қийматни мос қўямиз.
Охирги қадам. Берилган орграфда 1 белгили учдан 6 белгили учгача энг қисқа узунликка эга йўл(лар)ни топиш мақсадида, алгоритмга асосан, графнинг охирги белгили учидан бошлаб ажратилган ёйлар йўналишига қарама-қарши йўналишда ҳаракатланиб, унинг 1 белгили учига келишимиз керак. белгили учга кирувчи учта ёйдан фақат биттаси ( ёй) ажратилган бўлгани учун ёй йўналишига қарама-қарши йўналишда ҳаракат қилиб, белгили учдан белгили учга келамиз. белгили учга кирувчи иккала ( ва ) ёйлар ҳам ажратилган бўлгани учун биз тузмоқчи бўлган энг қисқа узунликка эга йўл ягона эмас.
Агар ҳаракатни ёй йўналишига тескари йўналишда давом эттирсак, у ҳолда белгили учдан белгили учга келиб, энг қисқа узунликка эга йўллардан бири бўлган маршрутни топамиз.
Агарда ҳаракатни ёй йўналишига тескари йўналишда давом эттирсак, у ҳолда белгили учдан белгили учга келамиз. белгили учга кирувчи иккита ёйдан фақат биттаси ( ёй) ажратилган бўлгани учун белгили учдан белгили учга келамиз. Шу усулда давом эцак, олдин белгили, кейин эса белгили учга ўтиб мумкин бўлган энг қисқа узунликка эга бўлган йўллардан иккинчисини, яъни маршрутни аниқлаймиз.
Шундай қилиб, 2- шаклда тасвирланган графда энг қисқа узунликка эга ва йўллар борлигини аниқладик. Бу йўлларнинг ҳар бири минимал узунликка эга. ■