Դիյքստրան ալգորիթմը եւ դրա իրականացումը

Կա մի առանձին տարածքը կոչվում գրաֆների տեսություն մաթեմատիկայի եւ համակարգչային գիտության. Որպես իր փաթեթի եւ լուծել տարբեր խնդիրներ, ինչպիսիք են գտնելու ամենակարճ ուղին միջեւ vertices: Մեկ տարածված մաթեմատիկոսներից լուծման ուղիների այս խնդիրը երկար ժամանակ եղել է Դիյքստրան ալգորիթմը:

Թե ինչ է մաթեմատիկական գրաֆիկի

Ենթադրվում է, որ այդ հասկացությունը գրաֆիկի շահագործման է հանձնվել են տասնութերորդ դարում Leonardom Eylerom: Այն էր, նա, ով հայտարարել է, որ ձեւակերպումը եւ լուծումը մեկի դասական խնդիրներ այս տեսության - ի յոթ կամուրջների Քյոնիգսբերգ: Որպեսզի բացատրել օբյեկտը այս տեսության հաճախ օգտագործել այս նմանակը որպես շարժման միջեւ տարբեր քաղաքներում: Ապա գրաֆիկի հարթության վրա պետք է լինի ամբողջ երթուղին դիագրամ, որտեղ vertices դառնալ հատուկ իրեր (օրինակ, քաղաքներում), իսկ եզրեր - Ճանապարհ մեկ vertex մեկ այլ (անալոգային ճանապարհի քաղաքների միջեւ): Դիյքստրան ալգորիթմը, ի լրումն այլ մեթոդների, կարող է ապահովել մի լուծում այս հարցին:

Գտնելով ամենակարճ ուղին

Մեկը ընդհանուր խնդիրներից է Գրաֆների տեսության մեկն է, որը դուք պետք է որոշելու օպտիմալ ծախսերի ուղին երկու կետերի միջեւ: Դա հնարավոր է նվազեցնել ինքնաթիռը որոշմամբ գրաֆիկի, որի գագաթները քաղաքներ - փոխկապակցված են կողոսկրերը, ինչը հնարավոր ճանապարհը. Յուրաքանչյուր ճանապարհային ունի իր սեփական երկարությունը, հետեւաբար, ճանապարհորդել դրա վրա պետք է ծախսել որոշակի գումար: Այս գումարը համարժեք է ծանրությունից եզրեր է գրաֆիկի: Ապա այդ խնդիրը գործնականում կարելի է ձեւակերպել հետեւյալ կերպ `ինչպես հարթել ճանապարհը մի քաղաքից մյուսը, կծախսվի ճանապարհի վրա նվազագույն միջոցներով:

լուծման ուղիները

Որպեսզի լուծել այս խնդիրը մենք արդեն հորինել են որոշ ալգորիթմներ, որոնք դարձել լայնորեն հայտնի է գիտական աշխարհում. Օրինակ, Floyd ալգորիթմ - Uorshella, Ford - Bellman. Որ դասական միջոց գտնելու լուծումներ է նաեւ Դիյքստրան ալգորիթմը: Այն կարող է օգտագործվել կշռված (հայտնի քաշը յուրաքանչյուր ծայրին) գրաֆիկի, եւ նոսրացնել: Գտնել վերջնական ճանապարհը դուք պետք է անել մի քանի քայլեր:

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

Բանն այն է, այս մեթոդի կայանում է նրանում, որ բոլոր գագաթները արժեքի, սկսած տրված, ջրով կը հեղեղեմ երկիրը յուրաքանչյուր թեգը, որը նշանակվում է որոշակի արժեք: Ապա արդյունքը ներառում է vertices որոնց պիտակներ են նվազագույն: Գագաթին առաջին նախնական քայլ կլինի պիտակները մի արժեք 0. Այնուհետեւ, բոլոր հետեւյալ պիկերի են համարվում, այսինքն, նրանք, որոնք կարելի է հասնել աղբյուրից: Նրանք, որոնք պիտակավորված, որի արժեքը որոշվում է որպես գումարի կոդով եւ կշիռը ուղիների. From վերեւում հաջորդ քայլ, ընտրեք մեկը, որ ունի ամենափոքր արժեքը պիտակի, եւ ուսումնասիրվել բոլոր vertices է, որ այն, որ մենք կարող ենք գնալ առանց օգտագործելով միջանկյալ հանգույցների. Նշեք մի նոր պիտակ, որը հավասար է պիտակի Սեղաներեսներ - ելակետային կոդը գումարած կշիռը ճանապարհին. Եթե արժեքը պակաս է սկիզբ պիտակի, պիտակը փոխվել: Հակառակ դեպքում, դա մնում է օրիգինալ արժեքը: Միեւնույն ժամանակ, մի առանձին զանգված, որի չափն է, հավասար է թվի գագաթների, որ պահում է օպտիմալացման արդյունքում, որի եւ վճռական ճանապարհով: Իրականացնել մի մեթոդ, ինչպես օրինակ Դիյքստրան ի ալգորիթմ, Պասկալ առաջարկում է շատ հարմար միջոցներ: Ալգորիթմը ունի առավելություն, որ այն կարող է հեշտությամբ է հիմք մի ծրագիր, որը ունի մի փոքր չափը: Օրինակներ նման ծրագրային արտադրանքի հեշտ է գտնել ինտերնետում.

Դլե լուծումներ տարբեր գործիքներ, դուք կարող եք օգտագործել խնդիրն է գտնել օպտիմալ ուղին: Համար լուծումներ, ինչպիսիք են Դիյքստրան ի ալգորիթմ, Delphi կստեղծի հարմար ձեւ տեսողական տվյալների մուտքագրման եւ ելքային վերջնական արդյունք: