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

“Ғ.Дәукеев атындағы АЛМАТЫ ЭНЕРГЕТИКА ЖӘНЕ БАЙЛАНЫС УНИВЕРСИТЕТІ”

Коммерциялық емес акционерлік қоғам

 ТИТ кафедрасы

ЕСЕПТЕУ-ГРАФИКАЛЫҚ ЖҰМЫС №2

                                                        НҰСҚА-19

Пәні: IP-телефония және ағындық технологиялар

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

Мамандығы: «6В07111-Ғарыштық техника және технологиялар»

Орындаған: Төлеубай А.Ж.                                          Тобы: КТТк-20-1

                      (тегі, аты-жөні)

Қабылдаған: аға-оқытушы Накисбекова Б.Р.                                              

                                 (ғылыми дәрежесі, атағы, аты-жөні)

________      _________ «____» __________20___ж.

                      (бағасы)           (қолы)

                                             Алматы 2020

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

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

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

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

[pic 1]

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

- Дейкстр әдісі бойынша IP желісімен маршрутизатор арасындағыең

қысқажолды таңдау.;

Дейкстр алгоритмі - бұл графалы алгоритм, 1959 жылынидерландық ғалым

Э.Дейкстр ойлаптапқан. Графтың бір шыңынан басқаларға дейінгі ең қысқа

 жолдарды табады. Бұл алгоритм программалау мен технологияда кеңінен

қолданылады, мысалы, оны OSPF (Open Shortest Path First) және IS-IS

(Intermediate System to Intermediate System) хаттамаларын маршрутизаторлар

қолданады.

Сонымен қатар осы алгоритмдеграфаның әр шыңына белгі қоямыз -,

онда маршрутизаторлар орналасқан.Алгоритм қадаммен жұмыс жасайды, әр

қадамда ол бір шынға барыпжәне оның белгіленуін кішірейтуге тырысады.

Барлық шыңдарға барғаннан кейін алгоритмнің жұмысы аяқталады.

[pic 2]

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

Шыңның бастапқы «а» белгіленуі нөлге теңеледі, қалғандарының белгіленуі

шексіздіккетең. Яғни «а» шыңынан басқа шыңдарға дейінгі арақашықтық

белгісіз екенінкөрсетеді (2.3 сурет).

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

1 шыңыең аз белгіленуден тұрады. 2 және 3 оның көршілері болып табылады.

[pic 3]

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

Кезек бойынша 1-ші шыңның көршісі - 2 шың, яғни оған дейінгі

арақашықтық ең аз (14). Сонымен қатар жолдың ұзындығы 1 шыңына дейін

қысқарақ болып табылады, яғни 0+14=14. Бұл мән ағымдағы 2-ші шыңның 42

белгіленуінен азырақ, шексіздіктен, сондықтан 2-1 шыңдарының белгіленуі 14 ке тең.

[pic 4]

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

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

[pic 5]

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

1 шыңның барлық көршілері қарастырылды. Олардың қарастырылғанын