Дейкстр әдісі бойынша желіде ең қысқа жолды таңдау

№2 есептеу графикалық жұмыс

16-нұсқа

 2.1 Дейкстр әдісі бойынша желіде ең қысқа жолды таңдау.

2.1.1 Нұсқа таңдау:

 - IP желісінің тополгиясына бастапқы мәліметтер, 2.1 - суретте көрсетілген.

[pic 1] 

2.1 сурет – Желінің бастапқы топологиясы.

        2.1.2 Жұмыстың орындалуына әдістемелік нұсқаулар. Дейкстр алгоритмі - бұл графалы алгоритм, 1959 жылы нидерландық ғалым Э.Дейкстр ойлап тапқан. Графтың бір шыңынан басқаларға дейінгі ең қысқа жолдарды табады. Бұл алгоритм программалау мен технологияда кеңінен қолданылады, мысалы, оны OSPF (Open Shortest Path First) және IS-IS (Intermediate System to Intermediate System) хаттамаларын маршрутизаторлар қолданады.                                                                         Сонымен қатар осы алгоритмде графаның әр шыңына белгі қоямыз -, онда маршрутизаторлар орналасқан. Алгоритм қадаммен жұмыс жасайды, әр қадамда ол бір шынға барып және оның белгіленуін кішірейтуге тырысады. Барлық шыңдарға барғаннан кейін алгоритмнің жұмысы аяқталады. 2.2 суретінде берілген мәліметтердің жіберу топология желісінде алгоритмінің орындалу мысалын қарастырайық, ол төрт маршрутизатордан тұрады. Машрутизаторлар арасында арналар болады. Маршрутизаторлар арасындағы арақашықтық әріптермен белгіленген.      

[pic 2]

2.2 сурет – Граф желісі.

        Шыңның бастапқы «а» белгіленуі нөлге теңеледі, қалғандарының белгіленуі шексіздікке тең. Яғни «а» шыңынан басқа шыңдарға дейінгі арақашықтық белгісіз екенін көрсетеді (2.3 сурет).

[pic 3]

2.3 сурет – Нөлдік кезең.

        Нөлдік кезеңнің мақсаты «1» шыңының түпкі түйінің көрсету үшін қолданылады және де оның белгіленуі нөлге тең.                                                 1 шыңы ең аз белгіленуден тұрады. 2 және 3 оның көршілері болып табылады (2.4 сурет).

[pic 4]

2.4 сурет – Бірінші қадам

        Кезек бойынша 1-ші шыңның көршісі - 2 шың, яғни оған дейінгі арақашықтық ең аз (4). Сонымен қатар жолдың ұзындығы 1 шыңына дейін қысқарақ болып табылады, яғни 0+11=11. Бұл мән ағымдағы 2-ші шыңның 29 белгіленуінен азырақ, шексіздіктен, сондықтан 2-1 шыңдарының белгіленуі 11 тең (2.5 сурет).

[pic 5]

2.5 сурет – Бірінші шыңның жаңа белгіленуі.

3 шыңмен аналогтық жүйені жалғастырайық (2.6 сурет)

[pic 6]

2.6 сурет – Екінші шыңның жаңа белгіленуі

1 шыңның барлық кӛршілері қарастырылды. Олардың қарастырылғанын белгілеу үшін оларды графадан сызып тастаймыз (2.7 сурет).

[pic 7]

2.7 сурет – Үшінші шыңның жаңа белгіленуі

Қайтадан қарастырылмаған жақын шыңдарды табамыз. Бұл 2-ші шың ағымдағы оған дейінгі беске тең ең қысқа арақашықтық (2.8 сурет).

[pic 8]

2.8 сурет – 2-ші шыңды қарастыру

Екінші шың арқылы өтіп, таңдалған шыңның көршілерінің белгіленуін қайтадан кішірейтуге тырысамыз. 3 және 5 2-ші шыңның көршілері болып табылады. Кезек бойынша 1-ші шыңның көршісі - 2 шың, бірақ ол қарастырылғандықтан бірінші шыңмен ештеңе жасамаймыз. Келесі көрші бұл 3-ші шың (21)-шыңның ішіндегі ең кіші белгіленуде болғандықтан, яғни ол шыңдардың арасында қарастырылмайды. Егер оған 2-ші шың арқылы баратын болсақ, яғни оның ұзындығы осындай болады: 40 (11+29). Бірақ ағымдағы шыңның 3-ші белгіленуі 21 < 40 , сондықтан белгіленуі өзгермейді.

[pic 9]

2.9 сурет – 2-ші шыңды қарастыру (белгілену өзгермейді)

        2-ші шыңның тағы да бір көршісі ол - 5-ші шың. Оған дейінгі 2-ші шың арқылы жол 47-ге тең. Яғни 47<∞ , 47-ге тең болатын 5-ші шыңға белгілену енгіземіз (2.10 сурет)

[pic 10]

2.10 сурет – Төртінші шыңды қарастыру

2-ші шыңның барлық көршілері қарастырылды. Олардың қарастырылғанын белгілеу үшін оларды графадан сызып тастаймыз (2.11 сурет).

[pic 11]

2.11 сурет – 2-ші шыңды белгіленді деп белгілеу

3-ші шыңды таңдап аналогтық жүйені қайталаймыз (2.12 сурет). 3-ші шыңның 1 және 2-ші көршілерін қарастырдық. Сондықтан тек 4-ші көршісін қараймыз 21+20=41, ал 4-ші шыңнан 5-ші шыңға дейінгі жол 41+26=67.