Դեքստրայի ալգորիթմ

Դեյքստրայի ալգորիթմ ( Dijkstra’s algorithm)։ Ալգորիթմ գրաֆներով, որը հայտնագործվել է հոլանդացի գիտնական Է. Դեյքստրայի կողմից 1959 թ.։ Այն գտնում է գրաֆի որևէ գագաթից մնացաց գագաթները ընկած կարճագույն հեռավորությունը։ Ալգորիթմը գործում է միայն ոչ բացասական կշիռ ունեցող կողմերով գրաֆների համար։ Ալգորիթմը շատ տարածված կիրառություն ունի ծրագրավորման և տեխնոլոգիաների մեջ։

Խնդրի ձևակերումը 
օրինակներ
Տարբերակ 1. Տրված է ավտոճանապարհների ցանց, որոնք կապում են Հայաստանի Հանրապետության քաղաքները միմյանց հետ։ Որոշ ճանապարհներ միակողմանի երթևեկելի են։ Անհրաժեշտ է գտնել Երևանից դեպի հանրապետության մնացած քաղաքներ տանող ամենակարճ ճանապարհները (շարժվել կարելի է միայն ավտոճանապարհներով)։ 
Տարբերակ 2. Տրված է որոշակի քանակի թռիչքուղիներ երկրագնդի երկրների միջև, որոնցից յուրաքանչյուրի արժեքը հայտնի է։ Կամայական "Ա" երկրից "Բ" երկիր թռիչքի արժեքը կարող է հավասար չլինել "Բ"-ից "Ա" թռիչքի արժեքին։ Անհրաժեշտ է գտնել Հայաստանից Իտալիա ուղևորության նվազագույն հնարավոր արժեքը (հնարավոր է, որ թռիչքն ընթանա միջանկյալ կանգառներով)։

Պաշտոնական սահմանում 
Տրված է կշռված ուղղորդված գրաֆ G(V,E) առանց հանգույցների և բացասական կշիռ ունեցող կողմերի։ Գտնել G գրաֆի որևէ a գագաթի ամենակարճ հեռավորությունը այդ գրաֆի մնացաց բոլոր գագաթներից։

Օրինակ 

Ալգորիթմներ