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

ñóììå äëèí ðåáåð, âõîäÿùèõ â ýòîò ïóòü. Íåîáõîäèìî íàéòè êðàò-
÷àéøèé èç ïóòåé, âåäóùèõ èç âåðøèíû À â âåðøèíó Â.
      Òàêàÿ çàäà÷à ìîæåò âîçíèêíóòü â ðàçëè÷íûõ ñèòóàöèÿõ. Íà-
ïðèìåð, åñëè ìû çàõîòèì ïåðåâåçòè ãðóç, òî ðåáðà ãðàôà — ýòî
äîðîãè, à âåðøèíû ãðàôà — ãîðîäà, ñòîÿùèå íà ïåðåêðåñòêàõ
ïóòåé. Äëèíû ðåáåð îïðåäåëÿþòñÿ óñëîâèÿìè çàäà÷è. Åñëè ìû
õîòèì íàéòè ñàìûé äåøåâûé ïóòü, òî çà äëèíó ðåáðà íóæíî
âçÿòü ñòîèìîñòü ïåðåâîçêè ãðóçà ïî ýòîìó ðåáðó. Åñëè ìû õîòèì
íàéòè ñàìûé áûñòðûé ïóòü, òî â êà÷åñòâå äëèíû íàäî âçÿòü
âðåìÿ ïðîåçäà. Åñëè ñàìûé êîðîòêèé — ðàññòîÿíèÿ ìåæäó ñîîò-
âåòñòâóþùèìè ãîðîäàìè.
       ÷àñòíîñòè, çàäà÷à î êðàò÷àéøåì ïóòè âîçíèêàåò ïðè ðàñ-
ñìîòðåíèè çàäà÷è îá èñïîëüçîâàíèè îáîðóäîâàíèÿ.
      Ðàññìîòðèì ïðèìåð. Ïóñòü íàøå ïðîèçâîäñòâî â òå÷åíèå ãîäà
íóæäàåòñÿ â àâòîìîáèëå. Íàì ïðåäñòàâëÿþòñÿ ðàçëè÷íûå âîçìîæ-
íîñòè. Íàïðèìåð, ìû ìîæåì àðåíäîâàòü àâòîìîáèëü íà îïðåäå-
ëåííûé ñðîê ïî îïðåäåëåííîé ñòîèìîñòè. Ìû ìîæåì êóïèòü àâ-
òîìîáèëü, êàêîå-òî âðåìÿ èì ïîëüçîâàòüñÿ, à çàòåì ïðîäàòü,
è ò. ä. Ñòàâèòñÿ çàäà÷à ðàçðàáîòàòü ñàìûé äåøåâûé ïëàí èñïîëü-
çîâàíèÿ îáîðóäîâàíèÿ íà óêàçàííûé ïåðèîä âðåìåíè. Çäåñü âåð-
øèíàì ãðàôà ñîîòâåòñòâóþò ìîìåíòû âðåìåíè, à êàæäîé èìåþ-
ùåéñÿ âîçìîæíîñòè (â êàæäûé ìîìåíò âðåìåíè) áóäåò ñîîòâåò-
ñòâîâàòü ðåáðî ãðàôà. Ìîæåò áûòü íåñêîëüêî ðåáåð, ñîåäèíÿþ-
ùèõ îäíó è òó æå ïàðó âåðøèí. Çà äëèíó ðåáðà íóæíî ïðèíÿòü
ñòîèìîñòü âûáðàííîãî âàðèàíòà. Ìîæíî ïðîèëëþñòðèðîâàòü ñêà-
çàííîå ñëåäóþùèì ðèñóíêîì. Çäåñü òî÷êè íà ïðÿìîé ñîîòâåò-
ñòâóþò ïîñëåäîâàòåëüíûì ìîìåíòàì âðåìåíè, îòðåçêè è äóãè
ñîîòâåòñòâóþò íàëè÷èþ ðåáðà (âàðèàíòà), aij ñòîèìîñòü ñîîòâåò-
ñòâóþùåãî âàðèàíòà èñïîëüçîâàíèÿ àâòîìîáèëÿ íà èíòåðâàëå âðå-
ìåíè [i, j].
                                             aij
         А                      В       i             j
               Àëãîðèòì ðàññòàíîâêè ìåòîê
     Ïðåäëîæåííûé íèæå àëãîðèòì íàõîæäåíèÿ êðàò÷àéøåãî ïóòè
ñîñòîèò èç äâóõ ÷àñòåé. Ñíà÷àëà îïðåäåëÿþòñÿ äëèíû êðàò÷àéøèõ
ïóòåé èç âåðøèíû À âî âñå âåðøèíû ãðàôà, çàòåì, çíàÿ äëèíû,
íàõîäèì êðàò÷àéøèé ïóòü, òî åñòü ñïèñîê âåðøèí, ÷åðåç êîòî-
ðûå îí ïðîõîäèò.

                              36