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

Դեյքստրայի ալգորիթմ
Տեսակ	ուղի որոնման ալգորիթմ, գրաֆների ալգորիթմ, greedy algorithm? և ալգորիթմ
Վատագույն դեպքում կատարումը	և
Օգտագործում է	գրաֆ
Հայտնաբերող	Էդսգեր Վ․ Դեյքստրա
Անվանված է	Էդսգեր Վ․ Դեյքստրա

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

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

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

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

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

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

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

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

Ծանոթագրություններ խմբագրել

↑ http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.4349&rep=rep1&type=pdf
↑ 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.
↑ ^4,0 ^4,1 Dijkstra, E. W. (1959). «A note on two problems in connexion with graphs». Numerische Mathematik. 1: 269–271. CiteSeerX 10.1.1.165.7577. doi:10.1007/BF01386390. S2CID 123284777.
↑ Mehlhorn, Kurt; Sanders, Peter (2008). «Chapter 10. Shortest Paths» (PDF). Algorithms and Data Structures: The Basic Toolbox. Springer. doi:10.1007/978-3-540-77978-0. ISBN 978-3-540-77977-3.

[_ea6a308e7ffc017f-1] ttp://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.4349&rep=rep1&type=pdf

[2] 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?»

[Dijkstra_Interview-3] Frana, Phil (2010 թ․ օգոստոս). «An Interview with Edsger W. Dijkstra». Communications of the ACM. 53 (8): 41–47. doi:10.1145/1787234.1787249.

[Dijkstra1959-4] 4,0 ^4,1 Dijkstra, E. W. (1959). «A note on two problems in connexion with graphs». Numerische Mathematik. 1: 269–271. CiteSeerX 10.1.1.165.7577. doi:10.1007/BF01386390. S2CID 123284777.

[mehlhorn-5] Mehlhorn, Kurt; Sanders, Peter (2008). «Chapter 10. Shortest Paths» (PDF). Algorithms and Data Structures: The Basic Toolbox. Springer. doi:10.1007/978-3-540-77978-0. ISBN 978-3-540-77977-3.

[2]

[3]

[4]

[1]

[5]