Yashiklar prinsipi

2
- мисол. 2- шаклда тасвирланган орграфда олтита уч ( ) ва ўн битта ёй бўлиб, ҳар бир ёй узунлиги унинг ёнига ёзилган. Кўриниб турибдики, берилган графда манфий узунликка эга ёй ҳам бор. Исботлаш мумкинки, бу графда умумий узунлиги манфий бўлган сикл мавжуд эмас.
Юқорида баён қилинган Дейкстра алгоритмини берилган графга қўллаб, энг қисқа узунликка эга йўлни топиш билан шуғулланамиз.
Дастлабки қадам. Манбага (1 белгили учга) қийматни мос қўямиз ва тўпламга эга бўламиз. Шунинг учун, бўлади.
Умумий қадам. 1- итерация. ва бўлгани учун бошланғич учи тўпламга тегишли, охирги учи эса тўплам элементи бўлган барча ёйлар тўплами га эга бўламиз. тўпламга тегишли бўлган ҳар бир ёй учун нинг қийматларини топамиз:
ёй учун ;
ёй учун ;
ёй учун .
Бу , ва миқдорлар орасида энг кичиги бўлгани учун ёйни ажратамиз (3- шаклда бу ёй қалин чизиқ билан белгиланган) ва белгили учга қийматни мос қўямиз. Алгоритмга кўра учни тўпламдан чиқариб, тўпламга киритамиз. Натижада ва тўпламларга эга бўламиз.
Иккала учи ҳам тўпламга тегишли бўлган битта ёй бўлгани учун фақат битта тенгсизликнинг бажарилишини текшириш кифоя. Бу тенгсизлик кўринишдаги тўғри муносабатдан иборат бўлгани учун 2- итерацияга ўтамиз.
2- итерация. бўлгани сабабли , , ва қийматларни ва эканлигини аниқлаймиз. Бу ерда энг кичик қиймат ёйга мос келади. Шунинг учун, ёйни ажратамиз ва қийматни белгили учга мос қўямиз. белгили учни тўпламдан чиқариб, тўпламга киритгандан сўнг ва тўпламлар ҳосил бўлади.
Иккала учи ҳам тўпламга тегишли бўлган учта , ва ёйлардан биринчиси учун тенгсизликнинг бажарилиши 1- итерацияда текширилганлиги ва , қийматларнинг ўзгармаганлиги сабабли фақат иккинчи ва учинчи ёйларга мос ва муносабатларни текшириш кифоя. Бу муносабатлар ва кўринишда бажарилади. Шунинг учун 3- итерацияга ўтамиз.