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

Դեքստրայի ալգորիթմ
Dijkstra Animation.gif
Տեսակpathfinding algorithm?, գրաֆների ալգորիթմ և greedy algorithm?
Վատագույն դեպքում կատարումըO(|E|+|V|\log |V|)
Օգտագործում էգրաֆ
ՀայտնաբերողԷդսգեր Վ․ Դեյքստրա
Անվանված էԷդսգեր Վ․ Դեյքստրա

Խնդրի ձևակերումըԽմբագրել

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

Պաշտոնական սահմանումԽմբագրել

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

ՕրինակԽմբագրել