«Дискретті математика»

жүктеу/скачать 445,27 Kb.

бет	2/7
Дата	21.10.2023
өлшемі	445,27 Kb.
	#120208

1 2 3 4 5 6 7

Байланысты:
Дийкстра алгоритмі

Алгоритм қадамы
Алғашқы қадам. 1 шыңында минималды белгі бар.Оның көршілері 2,3 және 6 шыңдары.

Инициализация
А шыңының белгісінің өзі 0-ге, басқа шыңдардың белгілері шексіздікке орнатылады.
Бұл а-дан басқа шыңдарға дейінгі қашықтықтардың әлі белгісіз екенін көрсетеді.
Графтың барлық шыңдары қаралмаған деп белгіленген.

Алгоритм қадамы
Егер барлық шыңдар бар болса, алгоритм аяқталады.
Әйтпесе, әлі бармаған шыңдардан ең аз белгісі бар u шыңы таңдалады.
Біз u соңғы нүкте болатын барлық мүмкін жолдарды қарастырамыз. U нүктесінен шеттері шығатын төбелер осы төбенің көршілері деп аталады. Барған деп белгіленгендерден басқа u төбесінің әрбір көршісі үшін ағымдағы u белгісінің мәндерінің қосындысына және осы көршімен u қосатын жиектің ұзындығына тең жаңа жол ұзындығын қарастырыңыз. Алынған ұзындық мәні көршінің белгі мәнінен аз болса, жапсырма мәнін алынған ұзындық мәнімен ауыстырыңыз. Барлық көршілерді қарастырып, u шыңын барған деп белгілеп, алгоритм қадамын қайталаңыз.

Мысал

Алгоритмнің орындалуын суретте көрсетілген Графтың мысалы арқылы қарастырайық.
Сізге 1-ші шыңнан барлық басқаларға дейінгі ең қысқа қашықтықтарды табу керек делік.

Шеңберлер шыңдарды, сызықтар олардың арасындағы жолдарды (Графтың шеттерін) көрсетеді. Шеңберлерде шыңдардың сандары көрсетілген, олардың салмағы шеттердің үстінде - жолдың ұзындығы көрсетілген. Әрбір шыңның жанында 1 төбесінен осы шыңға ең қысқа жолдың ұзындығын көрсететін қызыл белгі бар.
Алғашқы қадам. 1 шыңында минималды белгі бар.Оның көршілері 2,3 және 6 шыңдары.
1-төбенің бірінші көршісі 2-төбе, өйткені оған баратын жолдың ұзындығы минималды. 1 шыңы арқылы оған кіретін жолдың ұзындығы 1 төбесі белгісінің мәні мен 1-ден 2-ге дейінгі жиектің ұзындығының қосындысына тең, яғни 0 + 7 = 7. Бұл 2 шыңының ағымдағы белгісінен аз, шексіздік, сондықтан 2 шыңының жаңа белгісі 7 болады.

Біз ұқсас операцияны 1-ші шыңның басқа екі көршілерімен - 3-ші және 6-шы нүктелермен орындаймыз.
1 шыңының барлық көршілері тексеріледі. 1 шыңына дейінгі ағымдағы ең аз қашықтық түпкілікті болып саналады және оны қайта қарау мүмкін емес. Осы шыңға барғанын белгілеу үшін оны Графтен сызып алайық.

жүктеу/скачать 445,27 Kb.

Достарыңызбен бөлісу:

1 2 3 4 5 6 7