Դեյքստրայի ալգորիթմ (անգլերեն՝ Dijkstra’s algorithm)։ Ալգորիթմ գրաֆներով, որը հայտնագործվել է հոլանդացի գիտնական Է․ Դեյքստրայի կողմից 1959թ․։ Այն գտնում է գրաֆի որևէ գագաթից մնացաց գագաթները ընկած կարճագույն հեռավորությունը։ Ալգորիթմը գործում է միայն ոչ բացասական կշիռ ունեցող կողմերով գրաֆների համար։ Ալգորիթմը շատ տարածված կիրառություն ունի ծրագրավորման և տեխնոլոգիաների մեջ։
[խմբագրել] Խնդրի ձևակերումը
օրինակներ
Տարբերակ 1․ Տրված է ավտոճանապարհների ցանց, որոնք կապում են Հայաստանի Հանրապետության քաղաքները միմյանց հետ։ Որոշ ճանապարհներ միակողմանի երթևեկելի են։ Անհրաժեշտ է գտնել Երևանից դեպի հանրապետության մնացաց քաղաքներ տանող ամենակարճ ճանապարհները (շարժվել կարելի է միայն ավտոճանապարհներով)։
Տարբերակ 2․ Տրված է որոշակի քանակի թռիչքուղիներ երկրագնդի երկրների միջև, որոնցից յուրաքանչյուրի արժեքը հայտնի է։ Կամայական "Ա" երկրից "Բ" երկիր թռիչքի արժեքը կարող է հավասար չլինել "Բ"-ից "Ա" թռիչքի արժեքին։ Անհրաժեշտ է գտնել Հայաստանից Իտալիա ուղևորության նվազագույն հնարավոր արժեքը (հնարավոր է, որ թռիչքն ընթանա միջանկյալ կանգառներով)։
[խմբագրել] Պաշտոնական սահմանումը
Տրված է կշռված ուղղորդված գրաֆ G(V,E) առանց հանգույցների և բացասական կշիռ ունեցող կողմերի։ Գտնել G գրաֆի որևէ a գագաթի ամենակարճ հեռավորությունը այդ գրաֆի մնացաց բոլոր գագաթներից։
[խմբագրել] Ոչ պաշտոնական բացատրություն
Օրինակ
Ալգորիթմ
Նայել նաև
Հղումներ
Գրականություն
նշումներ
