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

Դեյքստրայի ալգորիթմ, կշռված գրաֆների (որը կարող է ներկայացնել ճանապարհային ցանց) գագաթների միջև ամենակարճ հեռավորությունը գտնող ալգորիթմ։ Հայտնաբերել է հոլանդացի գիտնական Էդսգեր Վիբե Դեյքստրան 1956 թվականին և հրատարակել երեք տարի անց։

Գոյություն ունեն ալգորիթմի բազմաթիվ տարբերակներ։ Դեքստրայի նախնական ալգորիթմը գտել է երկու տրված գագաթների միջև ամենակարճ հեռավորությունը, բայց ավելի տարած տարբերակում ալգորիթմը գտնում է ֆիքսված գագաթից գրաֆի մյուս գագաթների հեռավորությունը՝ կառուցելով ամենակարճ հեռավորության ծառ։

Ալգրոիթմը գտնում է գրաֆում տրված գագաթից մյուս բոլոր գագաթների հեռավորությունը։ Այն կարող է նաև կիրառվել մեկ գագաթից մյուս գագաթ հեռավորությունը գտնելու համար՝ դադարեցնելով ալգորիթմը ցանկալի հեռավորությունը գտնելուց հետո։ Օրինակ, եթե գրաֆի գագաթները համապատասխանում են քաղաքների, իսկ կողմերի գինը համապատասխանում է քաղաքների միջև հեռավորությանը (պարզության համար ենթադրենք, որ քաղաքների մեջ կա երթևեկելի ճանապարհ, որի վրա խանգարող օբյեկտներ չկան), ապա Դեքստրայի ալգորիթմը կարող է կիրառվել տրված քաղաքից յուրաքանչյուր քաղաք տանող ամենակարճ ճանապարհը գտնելու համար։

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

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

 Օրինակ 
   Պատկեր:Dijkstra_graph0.PNG 
   Պատկեր:Dijkstra_graph0.PNG 
   Պատկեր:Dijkstra_graph1.PNG 
   Պատկեր:Dijkstra_graph2.PNG 
   Պատկեր:Dijkstra_graph3.PNG 
   Պատկեր:Dijkstra_graph4.PNG 
   Պատկեր:Dijkstra_graph5.PNG 
   Պատկեր:Dijkstra_graph6.PNG 
   Պատկեր:Dijkstra_graph7.PNG 
   Պատկեր:Dijkstra_graph8.PNG 
   Պատկեր:Dijkstra_graph9.PNG 
   Պատկեր:Dijkstra_graph10.PNG 
   Պատկեր:Dijkstra_graph11.PNG 
   Պատկեր:Dijkstra_graph12.PNG 
   Պատկեր:Dijkstra_graph13.PNG 
   Պատկեր:Dijkstra_graph14.PNG 

 Ծանոթագրություններ 

Կատեգորիա:Գրաֆների ալգորիթմներ