Հատված
Մեր ծրագրում մեկ հանգույցն ունի մի քանի կարևոր հատկություններ. Այն տարբերում է բոլոր մյուսներից, ունի եզրեր, որոնք այն կապում են մյուսների հետ, հատկություն, որը ցույց կտա՝ արդյոք այցելե՞լ ենք հանգույցը, թե ոչ, դրա կոորդինատները օգտագործվում է դրա գրաֆիկական ներկայացման մեջ և ընդհանուր արժեքը: Եզրը գրաֆիկի երկու հանգույցների կապն է: Գոյություն ունեն երկու տեսակի եզրեր`ուղղորդված և չուղղորդված: Ուղղորդված ծայրը կարելի է դիտարկել որպես միակողմանի փողոց: Դա ցույց է տալիս, որ չնայած A հանգույցից դեպի B հանգույց ուղի կա, հակառակ ուղղությամբ անցնելը (B- ից A) հնարավոր չէ: Դա անելու համար մեզ պետք է մեկ և մյուս եզրը, որը կապում է A և B և որի ուղղությունը ցույց է տալիս դեպի A: Անուղղակի եզրը, մյուս կողմից, չի սահմանափակում այդպիսի սահմանափակումներով և թույլ է տալիս մեզ գնալ երկու ուղղություններով: Եզրին կարևոր հատկություններն այն վերջնական հանգույցներն են, որոնք այն կապում է, անկախ նրանից, թե այդ եզրը այցելված է, թե ոչ, դրա քաշը և ուղղությունը, եթե այդպիսիք կան:Ընդհանրապես, գրաֆն ունի միայն մեկ տեսակի եզր: Կախված գրաֆի եզրերի տեսակից, այն որակվում է որպես ուղղորդված կամ չուղղորդված: Այս ծրագրում մենք կքննարկենք չուղղորդված գրաֆները: Այս երկու տարրերը ծրագրում ունեն իրենց համապատասխան իրականացումը. Node և Edge դասերը: Բացի այդ, կան տվյալների ևս երկու կառույցներ, որոնք մեզ օգնում են ալգորիթմի կատարման հարցում միևնույն ժամանակ պարզության և արագության տեսանկյունից. ReachableNode և ReachableNodeList դասերը: Օժանդակ այս երկու դասերը թույլ կտան մեզ արագ տեսակավորել չայցելված հանգույցներն ըստ իրենց ընդհանուր արժեքի և ընտրել լավագույնը և դա անել ամենաարդյունավետ ձևով: Գրաֆի երկու հանգույցների միջև ամենակարճ ուղին գտնելու համար Դիկստրայի ալգորիթմը սովորաբար բնութագրվում է որպես «ագահ» ալգորիթմ: Այսինքն, ճանապարհի յուրաքանչյուր քայլափոխի ալգորիթմը կընտրի այն հանգույցը, որն ունի ամենացածր ընդհանուր արժեքը և որը չի այցելվել: Վերցնենք մի պարզ օրինակ և փորձենք ձեռքով գործարկել ալգորիթմը ՝ տեսնելու, թե ինչ է հարկավոր անել յուրաքանչյուր քայլ առ քայլ: Պատկերացնենք, որ մենք ուզում ենք 1-ին հանգույցից անցնել 8-րդ հանգույց: Մենք սկսում ենք հաշվի առնելով բոլոր հարևանները (կամ ինչպես նշված է կոդի նմուշներում — հասանելի իրերի հանգույցները) դեպի մեկնարկային հանգույցը `2, 4 և 5 հանգույցները:
Գրականության ցանկ
1. Diestel R. Graph Theory — Springer, 2005 — 410 pages.
2. Graph Theory with Applications, 487 Pages • 2007 , by C. Vasudev
3. Алексеев, В. Е. Графы и алгоритмы. Структуры данных. Модели вычислений / В.Е. Алексеев, В.А. Таланов. — М.: Бином. Лаборатория знаний, Интернет-университет информационных технологий, 2009. — 320 c.
4. Алексеев В.Е., Таланов В.А. — Графы. Модели вычислений. Структуры данных, Глава 3.4 Нахождение кратчайших путей в графе — Нижний Новгород, 2005;
5. Олифер В.Г. Олифер Н.А. — Основы компьютерных сетей — Питер, 2009;
6. Харари Ф., Палмер Э. Перечисление графов — М.: Мир, 1977. — 324 с.
7. …