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

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

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

1 2 3 4 5 6 7

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

Тағы да біз таңдалған шыңның көршілерінің белгілерін азайтуға тырысамыз, оларға 2-ші шың арқылы өтуге тырысамыз. 2 төбенің көршілері 1, 3 және 4 төбелері болып табылады.
2 төбесінің бірінші (ретімен) көршісі - 1 шыңы. Бірақ ол әлдеқашан барылған, сондықтан біз 1-ші шыңмен ештеңе істемейміз. Келесі көрші - 3 шыңы, өйткені оның минималды белгісі бар.
Егер сіз оған 2 арқылы барсаңыз, онда мұндай жолдың ұзындығы 17-ге тең болады (7 + 10 = 17). Бірақ үшінші шыңның ағымдағы белгісі 9, ол 17-ден аз, сондықтан белгі өзгермейді.
Үшінші қадам. 3 шыңын таңдай отырып, алгоритм қадамын қайталаймыз. Оны «өңдеуден» кейін біз келесі нәтижелерді аламыз

Екінші қадам. Тағы да біз қаралмаған шыңдардың «ең жақынын» табамыз. Бұл 7 белгісі бар 2 шыңы.

Тағы да біз таңдалған шыңның көршілерінің белгілерін азайтуға тырысамыз, оларға 2-ші шың арқылы өтуге тырысамыз. 2 төбенің көршілері 1, 3 және 4 төбелері болып табылады. 2 төбесінің бірінші (ретімен) көршісі - 1 шыңы. Бірақ ол әлдеқашан барылған, сондықтан біз 1-ші шыңмен ештеңе істемейміз. Келесі көрші - 3 шыңы, өйткені оның минималды белгісі бар. Егер сіз оған 2 арқылы барсаңыз, онда мұндай жолдың ұзындығы 17-ге тең болады (7 + 10 = 17). Бірақ үшінші шыңның ағымдағы белгісі 9, ол 17-ден аз, сондықтан белгі өзгермейді.
2-төбенің тағы бір көршісі 4-төбе болып табылады. Егер сіз оған 2-ші арқылы барсаңыз, онда мұндай жолдың ұзындығы 2-ші төбеге дейінгі ең қысқа қашықтықтың және 2 және 4 шыңдар арасындағы қашықтықтың қосындысына тең болады, яғни 22 (7 + 15 = 22) . 22<∞ болғандықтан, 4 төбесінің белгісін 22-ге орнаттық.
2 шыңының барлық көршілері қаралды, біз оған дейінгі қашықтықты қатайтып, оны барған деп белгілейміз.
Үшінші қадам. 3 шыңын таңдай отырып, алгоритм қадамын қайталаймыз. Оны «өңдеуден» кейін біз келесі нәтижелерді аламыз:

Келесі қадамдар.
Қалған шыңдар үшін алгоритм қадамын қайталаймыз. Бұл бұйрыққа сәйкес 6, 4 және 5 шыңдары болады.

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

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

1 2 3 4 5 6 7