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

Վիքիպեդիայից՝ ազատ հանրագիտարանից

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

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

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

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

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


Ոչ պաշտոնական բացատրություն[խմբագրել]

Dijkstra Animation.gif

Օրինակ

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

Ալգորիթմ

Նայել նաև

Հղումներ

Գրականություն

նշումներ