Դեյքստրայի ալգորիթմ, կշռված գրաֆների (որը կարող է ներկայացնել ճանապարհային ցանց) գագաթների միջև ամենակարճ հեռավորությունը գտնող ալգորիթմ։ Հայտնաբերել է հոլանդացի գիտնական Էդսգեր Վիբե Դեյքստրան 1956 թվականին և հրատարակել երեք տարի անց[2][3][4]։
Գոյություն ունեն ալգորիթմի բազմաթիվ տարբերակներ։ Դեքստրայի նախնական ալգորիթմը գտել է երկու տրված գագաթների միջև ամենակարճ հեռավորությունը[4], բայց ավելի տարած տարբերակում ալգորիթմը գտնում է ֆիքսված գագաթից գրաֆի մյուս գագաթների հեռավորությունը՝ կառուցելով ամենակարճ հեռավորության ծառ։
Ալգրոիթմը գտնում է գրաֆում տրաված գագաթից մյուս բոլոր գագաթների հեռավորությունը[5]:196–206։ Այն կարող է նաև կիրառվել մեկ գագաթից մյուս գագաթ հեռավորությունը գտնելու համար՝ դադարեցնելով ալգորիթմը ցանկալի հեռավորությունը գտնելուց հետո։ Օրինակ, եթե գրաֆի գագաթները համապատասխանում են քաղաքների, իսկ կողմերի գինը համապատասխանում է քաղաքների միջև հեռավորությանը (պարզության համար ենթադրենք, որ քաղաքների մեջ կա երթևեկելի ճանապարհ, որի վրա խանգարող օբյեկտներ չկան), ապա Դեքստրայի ալգորիթմը կարող է կիրառվել տրված քաղաքից յուրաքանչյուր քաղաք տանող ամենակարճ ճանապարհը գտնելու համար։
օրինակներ Տարբերակ 1. Տրված է ավտոճանապարհների ցանց, որոնք կապում են Հայաստանի Հանրապետության քաղաքները միմյանց հետ։ Որոշ ճանապարհներ միակողմանի երթևեկելի են։ Անհրաժեշտ է գտնել Երևանից դեպի հանրապետության մնացած քաղաքներ տանող ամենակարճ ճանապարհները (շարժվել կարելի է միայն ավտոճանապարհներով)։ Տարբերակ 2. Տրված է որոշակի քանակի թռիչքուղիներ երկրագնդի երկրների միջև, որոնցից յուրաքանչյուրի արժեքը հայտնի է։ Կամայական "Ա" երկրից "Բ" երկիր թռիչքի արժեքը կարող է հավասար չլինել "Բ"-ից "Ա" թռիչքի արժեքին։ Անհրաժեշտ է գտնել Հայաստանից Իտալիա ուղևորության նվազագույն հնարավոր արժեքը (հնարավոր է, որ թռիչքն ընթանա միջանկյալ կանգառներով)։
Տրված է կշռված ուղղորդված գրաֆ G(V,E) առանց հանգույցների և բացասական կշիռ ունեցող կողմերի։ Գտնել G գրաֆի որևէ a գագաթի ամենակարճ հեռավորությունը այդ գրաֆի մնացաց բոլոր գագաթներից։
↑Richards, Hamilton. «Edsger Wybe Dijkstra». A.M. Turing Award. Association for Computing Machinery. Վերցված է 2017 թ․ հոկտեմբերի 16-ին. «At the Mathematical Centre a major project was building the ARMAC computer. For its official inauguration in 1956, Dijkstra devised a program to solve a problem interesting to a nontechnical audience: Given a network of roads connecting cities, what is the shortest route between two designated cities?»
↑Frana, Phil (2010 թ․ օգոստոս). «An Interview with Edsger W. Dijkstra». Communications of the ACM. 53 (8): 41–47. doi:10.1145/1787234.1787249.
