Yashiklar prinsipi

3. Дейкстра алгоритми
Минимал узунликка эга йўл ҳақидаги масалани ҳал этиш усуллари орасида Дейкстра томонидан таклиф этилган алгоритм кўп қўлланилади. Қуйида графнинг 1 белгили учидан чиқиб (бу учни манба деб қабул қиламиз) графдаги ихтиёрий учгача (бу учни охирги уч деб ҳисоблаймиз) энг қисқа узунликка эга йўлни топиш имконини берувчи Дейкстра алгоритми келтирилган.
Дастлабки қадам. Манбага (1 белгили учга) қийматни мос қўйиб, бу учни дастлаб деб қабул қилинган тўпламга киритамиз: . деб оламиз.
Умумий қадам. Бошланғич учи тўпламга, охирги учи эса тўпламга тегишли бўлган барча ёйлар тўплами бўлсин. Ҳар бир ёй учун миқдорни аниқлаймиз, бу ерда деб учга мос қўйилган қиймат (графнинг 1 белгили учидан чиқиб белгили учигача энг қисқа йўл узунлиги) белгиланган.
қийматни аниқлаймиз. тўпламнинг охирги тенгликда минимум қиймат берувчи барча элементларини, яъни ёйларни ажратамиз. Ажратилган ёйларнинг ҳар биридаги белгили учга қийматни мос қўямиз. қиймат мос қўйилган барча учларни тўпламдан чиқариб тўпламга киритамиз.
Иккала учи ҳам тўпламга тегишли бўлган барча ёйлар учун тенгсизликнинг бажарилишини текширамиз. Текширилаётган тенгсизлик ўринли бўлмаган (жаъни бўлган) барча белгили учларнинг ҳар бирига мос қўйилган эски қиймат ўрнига янги қийматни мос қўямиз ва ёйни ажратамиз. Бунда эски қиймат аниқланган пайтда ажратилган ёйни ажратилмаган деб ҳисоблаймиз.
Учларга қиймат мос қўйиш жараёнини охирги ( белгили) учга қиймат мос қўйилгунча давом эттирамиз. Графнинг 1 белгили учидан (манбадан) чиқиб унинг ихтиёрий учигача (охирги учигача) энг қисқа йўл узунлиги бўлади.
Охирги қадам. Графнинг охирги учидан бошлаб ажратилган ёйлар йўналишига қарама-қарши йўналишда унинг 1 белгили учига келгунча ҳаракатланиб, натижада графдаги 1 белгили учдан ихтиёрий учгача энг қисқа узунликка эга йўл(лар)ни топамиз. ■