Математические методы в экономике. Копылов Г.Н - 40 стр.

åìêîñòü ýòîãî àëãîðèòìà Ñn2, ãäå n — ÷èñëî âåðøèí, Ñ — êîí-
ñòàíòà.
      ðåàëüíûõ ýêîíîìè÷åñêèõ çàäà÷àõ ìîãóò âîçíèêàòü ñèòóà-
öèè, êîãäà íåêîòîðûå ðåáðà èìåþò îòðèöàòåëüíóþ äëèíó. Íà-
ïðèìåð, ïðè ïåðåâîçêå ïîïóòíîãî ãðóçà èç i â j ìîæíî íå òîëüêî
íå òðàòèòü äåíåã íà ïåðååçä, íî è ïîëó÷àòü ïðèáûëü.  ýòîì ñëó-
÷àå, íåîáõîäèìî îïðåäåëèòü íàëè÷èå â ãðàôå öèêëîâ îòðèöà-
òåëüíîé äëèíû. Åñëè òàêèõ öèêëîâ íåò, òî àëãîðèòì ìîæíî ïðè-
ìåíÿòü ïðàêòè÷åñêè áåç èçìåíåíèé. Îòëè÷èå ñîñòîèò â òîì, ÷òî
ìîæåò èçìåíèòüñÿ ìåòêà ñî çíà÷êîì *.  ãðàôå áåç îòðèöàòåëüíûõ
äëèí ðåáåð òàêèå ìåòêè ìû íàçûâàëè ïîñòîÿííûìè, è îíè íå
ìîãëè ìåíÿòüñÿ. Çäåñü òàêàÿ ìåòêà ìîæåò èçìåíèòüñÿ. Â ýòîì ñëó-
÷àå ìû óáèðàåì ó íåå * è ïðîäîëæàåì ðàáîòó àëãîðèòìà. Åñëè æå
â ãðàôå ñóùåñòâóåò öèêë îòðèöàòåëüíîé äëèíû (ñì. ÷åðòåæ), òî
êðàò÷àéøåãî ïóòè ìîæåò íå ñóùåñòâîâàòü.
     Ðàññìîòðèì ïðèìåð, ïîêàçûâàþùèé, êàê ýòî ìîæåò ïðî-
èçîéòè.
                                D
                              -1        -1
                          C        -1        E
                     20                          20

                     А             10             В
     Íà ðèñóíêå âèäíî, ÷òî äëèíà ïóòè èç À â Â, ñîñòîÿùåãî èç
îäíîãî ðåáðà, ðàâíà 10. Åñëè æå ñíà÷àëà ïîéòè èç À â Ñ, çàòåì N
ðàç ïðîéòè ïî öèêëó CDE, à ëèøü ïîòîì ïîéòè â Â, òî äëèíà
ïóòè áóäåò ðàâíà (38 — 3N). Ïîïàäàÿ íà öèêë, ìîæåì ïðîêðó÷è-
âàòüñÿ ïî íåìó íåîäíîêðàòíî, ïîëó÷àÿ òåì ñàìûì äëèíó ïóòè èç
À â  ìåíüøå ëþáîãî, íàïåðåä çàäàííîãî, ÷èñëà.

          Çàäà÷è äëÿ ñàìîñòîÿòåëüíîãî ðåøåíèÿ
     Çàäàí ãðàô ñ 20 âåðøèíàìè, ðàñïîëîæåííûìè â âèäå ïðÿ-
ìîóãîëüíèêà 4×5 è èçîáðàæåííûìè êðóæî÷êàìè. Êàæäàÿ âåðøè-
íà ñîåäèíåíà ñ ñîñåäÿìè ñïðàâà, ñëåâà, ñíèçó, ñâåðõó íåîðèåí-
òèðîâàííûìè ðåáðàìè. Äëèíû ðåáåð óêàçàíû ÷èñëàìè, íàõîäÿ-
ùèìèñÿ ìåæäó âåðøèíàìè. Íàéòè äëèíû êðàò÷àéøèõ ïóòåé èç
ëåâîé âåðõíåé âåðøèíû â êàæäóþ âåðøèíó ãðàôà.



                                   40