4 І. Негізгі бөлім
жүктеу/скачать 3,23 Mb.
|
- Бұл бет үшін навигация:
- ,0
| 1.3. Дейкстра алгоритмі
Алгоритм салмағы берілген графтар үшін v1 төбесінен vп төбесіне дейінгі ең қысқа ара қашықтықты анықтайды. Әрбір төбеге ,0 реттелген парын сәйкестікке қоямыз. vi (m,vr) төбесінің бірінші координатасы v1 төбесінен vi төбесіне дейінгі тағайындалған ара қашықтықты, ал екінші координата v1 төбесінен vi төбесіне дейінгі жолдың алдыңғы төбесін білдіреді. (1) v1 ,0 төбесінен бастау керек, оны v1 0,0 деп өзгертіп, тұрақты ретінде алу керек. Басқа төбелер бұл кезде уақытша болып қалады. (2) vk төбесіне сыбайлас болатын әрбір vj төбесі үшін vk (m,vr) төбесі тұрақты болған кезде vk төбесінен vj төбесіне дейінгі қашықтыққа т шамасын қосу керек. Егер алынған мән vj төбесіне тағайындалған ағымдағы қашықтықтан аз болса, онда ағымдағы қашақтықты осы қосындымен алмастыру керек және екінші координатаны vk төбесі деп өзгерту қажет. (3) Уақытша төбелерге жазылған қашықтықтардың ішінен ең аз (минимум) мәнді табу керек. Осындай қашықтықтағы төбелердің біріншісін тұрақты ретінде алу керек. (4) Егер vп - тұрақты төбе болмаса, онда (2) пунктке қайта оралу керек. (5) Егер vп - тұрақты төбе болса, онда vп төбесіне тағайындалған қашықтық v1 төбесінен vп төбесіне дейінгі ең қысқа ара қашықтық болып табылады. (6) Жолды табу үшін vп төбесінен бастау керек, жолдың алдыңғы төбесін (екінші координата) табу керек. Жолдың әрбір vj төбесі үшін оның алдында тұрған жол төбесін v1 төбесіне жеткеше табу керек. Керісінше реттегі төбелерді алмастыру ең қысқа жолды береді. [2,3] Мысал. 1-суретте келтірілген салмақты графтың А төбесінен F төбесіне дейінгі ең қысқа ара қашықтықты табу керек. Шешуі. Әрбір төбеге ,0 реттелген парын сәйкестікке қоямыз да, берілген графты 2-суретте көрсетілгендей түрге келтіреміз. А төбесінен басқа төбелерге дейінгі жолды тұрғызу керек. Реттелген пардың бірінші компоненті төбеге жеткен уақыттағы ең қысқа жолдың ұзындығын көрсетеді, ал екінші компонент қысқа жолдың алдыңғы төбесін көрсетеді. Жол табылғанша бірінші компонент құрамында , ал екіншіде 0 болады. Тұрақты болған төбе қою шрифтімен бөлініп белгіленіп тұрады. Алгоритмнің 1 қадамын орындап, 3-суретте көрсетілгендей граф аламыз. В және С төбелері А төбесімен сыбайлас болғандықтан, 2 қадамды орындаймыз және В төбесінің реттелген парына (5, А) мәнін береміз, ал, С төбесінің реттелген парына (6, А) мәнін тағайындаймыз. (Шындығында, төбе координаталары жаңа ара қашықтық бұрынғы ара қашықтықтан аз болғанда ғана өзгертіледі, бірақ В және С төбелеріне дейінгі бұрынғы ара қашықтық ∞-ке тең, берілген жағдайда бұл маңызды емес.) 3 қадамды орындап, уақытша тағайындалған мәндердің ішінен ең кішісін таңдаймыз. Бұл жағдайда А төбесіне дейінгі бұл ара қашықтық 5-ке тең, осы В(5, А) төбесін тұрақты етіп аламыз. Сонда берілген граф 4-суретте көрсетілгендей болады. 2 қадамға қайтып келіп, В төбесімен сыбайлас болатын С, D, E, F уақытша төбелерін қарастырамыз. Әрбір жағдайда да В төбесінен берілген төбеге дейінгі қашықтыққа А төбесінен В төбесіне дейінгі қашықтықты қосып отырамыз. Сонда, С төбесі үшін бұл 5+3=8 болады, сол сияқты D төбесі үшін 5+7=12, E төбесі үшін 5+2=7, F төбесі үшін 5+10=15 болады. С төбесіне дейінгі соңғы алынған 8-ге тең ара қашықтық бұл төбеге тағайындалған бұрынғы 6-ға тең ара қашықтықтан кіші (аз) болмағандықтан С төбесінің С(6, А) реттелген парын бұрынғыша өзгеріссіз қалдырамыз. Соңғы алынған D, E, F төбелеріне дейінгі ара қашықтық бұл төбелерге тағайындалған бұрынғы ара қашықтықтардан кіші болғандықтан, оларға В төбесінен шығатын жол арқылы алынған мәндерді береміз, яғни оларды D(12, В), E(7, В), F(15, В) мәндерімен алмастырамыз. 3 қадамды орындап, уақытша төбелерге берілген ара қашықтықтардың ішінен ең кішісін табамыз, сондықтан min{6, 12, 15, 7}=6 мәнін аламыз. С төбесінің ара қашықтығы осы 6 болғандықтан, енді осы С(6, А) төбесін тұрақты етіп аламыз. Нәтижесінде берілген граф 5-суретте көрсетілгендей болады. Енді жаңа тұрақты С төбесін алып, 2 қадамды орындағанда, төбелердің реттелген парларында өзгерістер болмайды, себебі соңғы алынған ара қашықтықтар алдыңғы берілген ара қашықтықтардан кіші емес (С(6, А) тұрақты төбесімен сыбайлас болатын төбе Е төбесі, С төбесінен Е төбесіне дейінгі қашықтыққа 6 саны қосылады, яғни, Е төбесі үшін 6+7=13, Е(13, С) болады, бұл мән бұрынғы тағайындалған Е(7, В) мәнінен кіші емес, ендеше бұрынғы E(7, В) мәні өзгеріссіз қалады), төбелер мына түрде болады: D(12, В), E(7, В), F(15, В). 3 қадамды орындап, уақытша төбелерге берілген ара қашықтықтардың ішінен ең кішісін табамыз, сондықтан min{12, 15, 7}=7 мәнін аламыз. Е төбесінің ара қашықтығы осы 7 болғандықтан, енді осы Е(7, В) төбесін тұрақты етіп аламыз. Граф төбелеріне сәйкесті реттелген парлар 6 суретте келтірілген. Е төбесін тұрақты етіп алып, 2 қадамды орындаймыз. F төбесінің реттелген пары бұрын F(15, В) болатын, енді ара қашықтықты Е төбесі арқылы тапсақ F төбесінің бірінші координатасы 7+4=11 болады, яғни F(11, Е). 3 қадам бойынша min{15, 11}=11 болады, ендеше F(11, Е) төбесін тұрақты етіп аламыз. Бұл өзгерістен кейінгі граф кескіні 7-суретте берілген. F төбесі тұрақты болған соң процесс аяқталады, яғни 11 - А төбесінен F төбесіне дейінгі ең қысқа ара қашықтық болып табылады. Ең қысқа жолды табу үшін F төбесінің алдында орналасқан төбе Е, Е төбесінің алдындағы төбе В, ал В төбесінің алдында орналасқан А төбесі екендігін ескереміз. Сондықтан ең қысқа жол ABEF болады. жүктеу/скачать 3,23 Mb. Достарыңызбен бөлісу:
|