1. Ïîëîæèòü l(s)+=0, ò.å. ñ÷èòàòü ýòó ìåòêó ïîñòîÿíîé, è l(v)= äëÿ âñåõ , ñ÷èòàÿ ýòè ìåòêè âðåìåííûìè. Ïðèíÿòü u=s.

     2. Äëÿ âñåõ  ñ âðåìåííûìè ìåòêàìè âûïîëíèòü: åñëè l(v)>l(u)+f(x) è (v)=u. Èíà÷å l(v) è (v) íå ìåíÿòü.

     3. Ïóñü V' - ìíîæåñòâî âåðøèí ñ âðåìåííûìè ìåòêàìè l. Íàéòè âåðøèíó v*, òàêóþ, ÷òî

     Ñ÷èòàòü ìåòêó l(v*)+ ïîñòîÿííîé ìåòêîé âåðøèíû v*; (v*)+.

     4. u=v*. Åñëè u=t, òî ïåðåéòè ê ï.5 (l(t)+ - âåñ êðàò÷àéøåãî  (s,t) - ïóòè). Èíà÷å ïåðåéòè ê ï.2.

     5. Ïî ïîñòîÿííûì - ìåòêàì óêàçûâàåòñÿ êðàò÷àéøèé (s,t) - ïóòü. Êîíåö.

     Ïóíêò 4 ìîæíî ìîäèôèöèðîâàòü òàê, ÷òîáû àëãîðèòì çàêàí÷èâàë ðàáîòó ïîñëå ïîëó÷åíèÿ âñåìè âåðøèíàìè ãðàôà G ïîñòîÿííûõ ìåòîê, ò.å. íàõîäÿòñÿ êðàò÷àéøèå ïóòè èç s âî âñå âåðøèíû ãðàôà. Àëãîðèòì îïðåäåëèò îñòîâíîå äåðåâî D êðàò÷àéøèõ ïóòåé èç âåðøèíû s. Äëÿ ëþáîé âåðøèíû v åäèíñòâåííûé (s,v) - ïóòü â äåðåâå D áóäåò êðàò÷àéøèì (s,v) - ïóòåì â ãðàôå G.

4. Ñïèñîê ëèòåpàòópû

     1  Èñìàãèëîâ Ð.Ñ., Êàëèíêèí À.Â. Ìàòåpèàëû ê ïpàêòè÷åñêèì çàíÿòèÿì ïî êópñó: Äèñêpåòíàÿ ìàòåìàòèêà ïî òåìå: Àëãîpèòìû íà ãpàôàõ. - Ì.: ÌÃÒÓ, 1995, 24 ñ.

     2  Ãàâpèëîâ Ã.Ï., Ñàïîæåíêî À.À. Çàäà÷è è óïpàæíåíèÿ ïî êópñó äèñêpåòíîé ìàòåìàòèêè. - Ì.: Hàóêà, 1992, 408 ñ.

     3  Ñìîëüÿêîâ Ý.Ð. Ââåäåíèå â òåîpèþ ãpàôîâ. Ì.: ÌÃÒÓ, 1992, 32 ñ.

     4  Hå÷åïópåíêî Ì.È. Àëãîpèòìû è ïpîãpàììû påøåíèÿ çàäà÷ íà ãpàôàõ è ñåòÿõ. - Hîâîñèáèpñê: Hàóêà, 1990, 515 ñ.

     5  Ðîìàíîâñêèé È.Â. Àëãîpèòìû påøåíèÿ ýêñòpåìàëüíûõ çàäà÷. - Ì.: Hàóêà, 1977, 352 ñ.

     6  Håôåäîâ Â.H., Îñèïîâà Â.À. Êópñ äèñêpåòíîé ìàòåìàòèêè. - Ì.: ÌÀÈ, 1992, 264 ñ.

     7  Ïèññàíåöêè Ñ. Òåõíîëîãèÿ ðàçðåæåííûõ ìàòðèö. - Ì.: Ìèð, 1988, 412 ñ.

     8  Ãíåäåíêî Á.Â. Êóðñ òåîðèè âåðîÿòíîñòåé. - Ì.: Íàóêà, 1988, 448 ñ.

     9  Âåíòöåëü Å.Ñ., Îâ÷àðîâ Ë.À. Òåîðèÿ âåðîÿòíîñòåé. - Ì.: Íàóêà, 1969, 367 ñ.

     10  Çóáêîâ À.Ì., Ñåâàñòüÿíîâ Á.À., ×èñòÿêîâ Â.Ï. - Ñáîðíèê çàäà÷ ïî òåîðèè âåðîÿòíîñòåé. - Ì.: Íàóêà, 1989, 320 ñ.

     11  Ñåâàñòüÿíîâ Á.À. Âåðîÿòíîñòíûå ìîäåëè. - Ì.: Íàóêà, 1992, 176 ñ.

     12  Áî÷àðîâ Ï.Ï., Ïå÷èíêèí À.Â. Òåîðèÿ âåðîÿòíîñòåé. - Ì.: Èçä-âî ÐÓÄÍ, 1994, 172 ñ.

     13  Áî÷àðîâ Ï.Ï., Ïå÷èíêèí À.Â. Ìàòåìàòè÷åñêàÿ ñòàòèñòèêà. - Ì.: Èçä-âî ÐÓÄÍ, 1994, 164 ñ.

     14  Êîëìîãîðîâ À.Í., Ôîìèí Ñ.Â. Ýëåìåíòû òåîðèè ôóíêöèé è ôóíêöèîíàëüíîãî àíàëèçà. - Ì.: Íàóêà, 1989, 624 ñ.

Страницы: 1, 2, 3, 4, 5, 6, 7