Лекция 5. Задача маршрутизации. Алгоритм Флойда-Уоршалла_ Туэга_ Мерлина-Сигалла_ Чанди-Мисры, страница 2

(î äåðåâå îïòèìàëüíûõ ïóòåé).u ∈ V ñâÿçíîãî ãðàôà G ñóùåñòâóåòTu = (V , Eu ), Eu ⊆ E , â êîòîðîì äëÿ ëþáîéâåðøèíû v ∈ V , åäèíñòâåííûé ïóòü èç v â u â äåðåâå Tuÿâëÿåòñÿ îïòèìàëüíûì ïóòåì èç v â u â ãðàôå G .Äëÿ êàæäîé âåðøèíûòàêîå äåðåâîÄîêàçàòåëüñòâî.V = {v1 , . . . , vN } . ÏîñòðîèìTi = (Vi , Ei ), i = 0, . . . , N , ÷òîÏóñòüèíäóêòèâíî òàêèå äåðåâüÿÌàðøðóòèçàöèÿ íà îñíîâå óçëîâ-àäðåñàòîâÒåîðåìà 5.1. (î äåðåâå îïòèìàëüíûõ ïóòåé).u ∈ V ñâÿçíîãî ãðàôà G ñóùåñòâóåòTu = (V , Eu ), Eu ⊆ E , â êîòîðîì äëÿ ëþáîéâåðøèíû v ∈ V , åäèíñòâåííûé ïóòü èç v â u â äåðåâå Tuÿâëÿåòñÿ îïòèìàëüíûì ïóòåì èç v â u â ãðàôå G .Äëÿ êàæäîé âåðøèíûòàêîå äåðåâîÄîêàçàòåëüñòâî.V = {v1 , .

. . , vN } . ÏîñòðîèìTi = (Vi , Ei ), i = 0, . . . , N , ÷òîÏóñòü1. Êàæäîå äåðåâîTièíäóêòèâíî òàêèå äåðåâüÿÿâëÿåòñÿ ïîäãðàôîì ãðàôàG.Ìàðøðóòèçàöèÿ íà îñíîâå óçëîâ-àäðåñàòîâÒåîðåìà 5.1. (î äåðåâå îïòèìàëüíûõ ïóòåé).u ∈ V ñâÿçíîãî ãðàôà G ñóùåñòâóåòTu = (V , Eu ), Eu ⊆ E , â êîòîðîì äëÿ ëþáîéâåðøèíû v ∈ V , åäèíñòâåííûé ïóòü èç v â u â äåðåâå Tuÿâëÿåòñÿ îïòèìàëüíûì ïóòåì èç v â u â ãðàôå G .Äëÿ êàæäîé âåðøèíûòàêîå äåðåâîÄîêàçàòåëüñòâî.V = {v1 , . . . , vN } . ÏîñòðîèìTi = (Vi , Ei ), i = 0, .

. . , N , ÷òîÏóñòüèíäóêòèâíî òàêèå äåðåâüÿ1. Êàæäîå äåðåâîTiÿâëÿåòñÿ ïîäãðàôîì ãðàôà2. Êàæäîå äåðåâîTi ïîääåðåâî äåðåâàTi+1.G.Ìàðøðóòèçàöèÿ íà îñíîâå óçëîâ-àäðåñàòîâÒåîðåìà 5.1. (î äåðåâå îïòèìàëüíûõ ïóòåé).u ∈ V ñâÿçíîãî ãðàôà G ñóùåñòâóåòTu = (V , Eu ), Eu ⊆ E , â êîòîðîì äëÿ ëþáîéâåðøèíû v ∈ V , åäèíñòâåííûé ïóòü èç v â u â äåðåâå Tuÿâëÿåòñÿ îïòèìàëüíûì ïóòåì èç v â u â ãðàôå G .Äëÿ êàæäîé âåðøèíûòàêîå äåðåâîÄîêàçàòåëüñòâî.V = {v1 , . . . , vN } .

ÏîñòðîèìTi = (Vi , Ei ), i = 0, . . . , N , ÷òîÏóñòüèíäóêòèâíî òàêèå äåðåâüÿ1. Êàæäîå äåðåâîTiÿâëÿåòñÿ ïîäãðàôîì ãðàôà2. Êàæäîå äåðåâîTi ïîääåðåâî äåðåâà3. Äëÿ êàæäîãîi >0, âûïîëíÿþòñÿTi+1vi ∈ VièG..u ∈ Vi.Ìàðøðóòèçàöèÿ íà îñíîâå óçëîâ-àäðåñàòîâÒåîðåìà 5.1. (î äåðåâå îïòèìàëüíûõ ïóòåé).u ∈ V ñâÿçíîãî ãðàôà G ñóùåñòâóåòTu = (V , Eu ), Eu ⊆ E , â êîòîðîì äëÿ ëþáîéâåðøèíû v ∈ V , åäèíñòâåííûé ïóòü èç v â u â äåðåâå Tuÿâëÿåòñÿ îïòèìàëüíûì ïóòåì èç v â u â ãðàôå G .Äëÿ êàæäîé âåðøèíûòàêîå äåðåâîÄîêàçàòåëüñòâî.V = {v1 , . .

. , vN } . ÏîñòðîèìTi = (Vi , Ei ), i = 0, . . . , N , ÷òîÏóñòüèíäóêòèâíî òàêèå äåðåâüÿ1. Êàæäîå äåðåâîTiÿâëÿåòñÿ ïîäãðàôîì ãðàôà2. Êàæäîå äåðåâîTi ïîääåðåâî äåðåâà3. Äëÿ êàæäîãîi >0, âûïîëíÿþòñÿ4. Äëÿ êàæäîé âåðøèíûw ∈ Vivi ∈ Viïóòü èçÿâëÿåòñÿ îïòèìàëüíûì ïóòåì èçTi+1wâèG..u ∈ Vi.w â u â äåðåâå Tiu â ãðàôå G .Ìàðøðóòèçàöèÿ íà îñíîâå óçëîâ-àäðåñàòîâÒåîðåìà 5.1. (î äåðåâå îïòèìàëüíûõ ïóòåé).u ∈ V ñâÿçíîãî ãðàôà G ñóùåñòâóåòTu = (V , Eu ), Eu ⊆ E , â êîòîðîì äëÿ ëþáîéâåðøèíû v ∈ V , åäèíñòâåííûé ïóòü èç v â u â äåðåâå Tuÿâëÿåòñÿ îïòèìàëüíûì ïóòåì èç v â u â ãðàôå G .Äëÿ êàæäîé âåðøèíûòàêîå äåðåâîÄîêàçàòåëüñòâî.V = {v1 , . . .

, vN } . ÏîñòðîèìTi = (Vi , Ei ), i = 0, . . . , N , ÷òîÏóñòüèíäóêòèâíî òàêèå äåðåâüÿ1. Êàæäîå äåðåâîTiÿâëÿåòñÿ ïîäãðàôîì ãðàôà2. Êàæäîå äåðåâîTi ïîääåðåâî äåðåâà3. Äëÿ êàæäîãîi >0, âûïîëíÿþòñÿ4. Äëÿ êàæäîé âåðøèíûw ∈ Vißñíî, ÷òî äåðåâîTNvi ∈ Viïóòü èçÿâëÿåòñÿ îïòèìàëüíûì ïóòåì èçáóäåò èñêîìûì.Ti+1wâèG..u ∈ Vi.w â u â äåðåâå Tiu â ãðàôå G .Ìàðøðóòèçàöèÿ íà îñíîâå óçëîâ-àäðåñàòîâÄîêàçàòåëüñòâî.ÏîëîæèìV0 = {u}èE0 = ∅.Ìàðøðóòèçàöèÿ íà îñíîâå óçëîâ-àäðåñàòîâÄîêàçàòåëüñòâî.V0 = {u} è E0 = ∅ .Ti+1 ñòðîèòñÿ òàê. Âûáèðàåòñÿ îïòèìàëüíûé ïðîñòîéïóòü P = hu0 , . . .

, uk i èç vi+1 â u . Ïóñòü ` íàèìåíüøèéèíäåêñ, äëÿ êîòîðîãî u` ∈ Ti . ÏîëîæèìÏîëîæèìÄåðåâîVi+1 = Vi ∪ {uj : j < `}èEi+1 = Ei ∪ {(uj , uj+1 ) : j < `}.Ìàðøðóòèçàöèÿ íà îñíîâå óçëîâ-àäðåñàòîâÄîêàçàòåëüñòâî.V0 = {u} è E0 = ∅ .Ti+1 ñòðîèòñÿ òàê. Âûáèðàåòñÿ îïòèìàëüíûé ïðîñòîéïóòü P = hu0 , . .

. , uk i èç vi+1 â u . Ïóñòü ` íàèìåíüøèéèíäåêñ, äëÿ êîòîðîãî u` ∈ Ti . ÏîëîæèìÏîëîæèìÄåðåâîVi+1 = Vi ∪ {uj : j < `}ßñíî, ÷òîÃðàôTi+1TièEi+1 = Ei ∪ {(uj , uj+1 ) : j < `}.ÿâëÿåòñÿ ïîääåðåâîì ãðàôàTi+1, èvi+1 ∈ Vi+1Ti+1ÿâëÿåòñÿ äåðåâîì, ïîñêîëüêó ïî ïîñòðîåíèþÿâëÿåòñÿ ñâÿçíûì ãðàôîì, è ÷èñëî âåðøèí â íåì ïðåâîñõîäèò÷èñëî ðåáåð â òî÷íîñòè íà åäèíèöó..Ìàðøðóòèçàöèÿ íà îñíîâå óçëîâ-àäðåñàòîâvvvvvi+1 vvH.v.

H. . . . . . .vH..HH.v ..A .v..A ....A.v.v`AA..vd ````u``vv!!Ti. . . .PTi+1!!!!Ðèñ.: Ïîñòðîåíèå äåðåâàTi+1 .Ìàðøðóòèçàöèÿ íà îñíîâå óçëîâ-àäðåñàòîâÄîêàçàòåëüñòâî.w ∈ Vi+1 ïóòü èç w â u âïóòåì èç w â u â ãðàôå G .Ïîêàæåì, ÷òî äëÿ âñåõ âåðøèíTi+1ÿâëÿåòñÿ îïòèìàëüíûìäåðåâåÌàðøðóòèçàöèÿ íà îñíîâå óçëîâ-àäðåñàòîâÄîêàçàòåëüñòâî.w ∈ Vi+1 ïóòü èç w â u âTi+1 ÿâëÿåòñÿ îïòèìàëüíûì ïóòåì èç w â u â ãðàôå G .Äëÿ âåðøèí w ∈ Vi ⊂ Vi+1 ýòî âåðíî, ò.ê. Ti ÿâëÿåòñÿïîääåðåâîì äåðåâà Ti+1 .Ïîêàæåì, ÷òî äëÿ âñåõ âåðøèíäåðåâåÌàðøðóòèçàöèÿ íà îñíîâå óçëîâ-àäðåñàòîâÄîêàçàòåëüñòâî.w ∈ Vi+1 ïóòü èç w â u â äåðåâåTi+1 ÿâëÿåòñÿ îïòèìàëüíûì ïóòåì èç w â u â ãðàôå G .Äëÿ âåðøèí w ∈ Vi ⊂ Vi+1 ýòî âåðíî, ò.ê. Ti ÿâëÿåòñÿïîääåðåâîì äåðåâà Ti+1 .00Ïóñòü w = uj , j < ` , ïðèíàäëåæèò Vi+1 \ Vi , è ïóñòü Q ïóòü èç u` â u â äåðåâå Ti .

Òîãäà â äåðåâå Ti+1 èç âåðøèíû ujâ âåðøèíó u âåäåò ïóòü, ïîëó÷åííûé â ðåçóëüòàòå ñîåäèíåíèÿ000ïóòè Q = huj , . . . , u` i è ïóòè Q .Ïîêàæåì, ÷òî äëÿ âñåõ âåðøèíÌàðøðóòèçàöèÿ íà îñíîâå óçëîâ-àäðåñàòîâÄîêàçàòåëüñòâî.w ∈ Vi+1 ïóòü èç w â u â äåðåâåTi+1 ÿâëÿåòñÿ îïòèìàëüíûì ïóòåì èç w â u â ãðàôå G .Äëÿ âåðøèí w ∈ Vi ⊂ Vi+1 ýòî âåðíî, ò.ê. Ti ÿâëÿåòñÿïîääåðåâîì äåðåâà Ti+1 .00Ïóñòü w = uj , j < ` , ïðèíàäëåæèò Vi+1 \ Vi , è ïóñòü Q ïóòü èç u` â u â äåðåâå Ti . Òîãäà â äåðåâå Ti+1 èç âåðøèíû ujâ âåðøèíó u âåäåò ïóòü, ïîëó÷åííûé â ðåçóëüòàòå ñîåäèíåíèÿ000ïóòè Q = huj , . . .

, u` i è ïóòè Q .0 00Îñòàåòñÿ ïîêàçàòü, ÷òî ïóòü Q = Q Q ÿâëÿåòñÿ îïòèìàëüíûìâ ãðàôå G .Ïîêàæåì, ÷òî äëÿ âñåõ âåðøèíÌàðøðóòèçàöèÿ íà îñíîâå óçëîâ-àäðåñàòîâvvvPvQ0ujvvH.v. H. . . . . . .vH..HH.v ..0. A .v..00 A ...A.v.v`AA..vd ````u``vTi. . . .PQv!!Ti+1!!!!Ðèñ.: Ïîñòðîåíèå äåðåâàTi+1 .Ìàðøðóòèçàöèÿ íà îñíîâå óçëîâ-àäðåñàòîâÄîêàçàòåëüñòâî.P 0 = hu` , . . . , uk i ïóòè P ÿâëÿåòñÿ0îïòèìàëüíûì ïóòåì èç u` â u . Ïîýòîìó C (P ) = C (Q) .

Ýòîñëåäóåò èç îïòèìàëüíîñòè ïóòåé Q è P (ó÷èòûâàÿ ñâîéñòâîÇàìåòèì, ÷òî ñóôôèêñàääèòèâíîñòè ñòîèìîñòè ïóòåé).Ìàðøðóòèçàöèÿ íà îñíîâå óçëîâ-àäðåñàòîâÄîêàçàòåëüñòâî.P 0 = hu` , . . . , uk i ïóòè P ÿâëÿåòñÿ0îïòèìàëüíûì ïóòåì èç u` â u . Ïîýòîìó C (P ) = C (Q) . Ýòîñëåäóåò èç îïòèìàëüíîñòè ïóòåé Q è P (ó÷èòûâàÿ ñâîéñòâîÇàìåòèì, ÷òî ñóôôèêñàääèòèâíîñòè ñòîèìîñòè ïóòåé).Äîïóñòèì, ÷òî åñòü ïóòüRèçuj â u ìåíüøåé ñòîèìîñòè, ÷åìR ìåíüøå, ÷åì ñòîèìîñòü ïóòèïóòüQ 0 Q 00Q 0P 0, à ýòî îçíà÷àåò (ó÷èòûâàÿ ñâîéñòâî àääèòèâíîñòè.

Òîãäà ñòîèìîñòüñòîèìîñòè ïóòåé), ÷òî ïóòü, îáðàçîâàííûé ïðèñîåäèíåíèåì êïóòèhu0 , . . . , uj iïóòèîïòèìàëüíûé ïóòüP.R, èìååò ìåíüøóþ ñòîèìîñòü, ÷åìÌàðøðóòèçàöèÿ íà îñíîâå óçëîâ-àäðåñàòîâÎñòîâíîå äåðåâî, êîðíåì êîòîðîãî ñëóæèò âåðøèíàíàçûâàåòñÿ âõîäíûì äåðåâîì äëÿuu,, à äåðåâî,óäîâëåòâîðÿþùåå òåîðåìå î äåðåâå îïòèìàëüíûõ ïóòåéíàçûâàåòñÿ îïòèìàëüíûì âõîäíûì äåðåâîì .Ñóùåñòâîâàíèå îïòèìàëüíîãî âõîäíîãî äåðåâà îçíà÷àåò, ÷òîàëãîðèòì îïòèìàëüíîé ìàðøðóòèçàöèè ìîæåò ðàáîòàòü ñèñïîëüçîâàíèåì ñëåäóþùåé ëîêàëüíîé ïðîöåäóðûtable_lookupv .Ìàðøðóòèçàöèÿ íà îñíîâå óçëîâ-àäðåñàòîâÎñòîâíîå äåðåâî, êîðíåì êîòîðîãî ñëóæèò âåðøèíàíàçûâàåòñÿ âõîäíûì äåðåâîì äëÿuu,, à äåðåâî,óäîâëåòâîðÿþùåå òåîðåìå î äåðåâå îïòèìàëüíûõ ïóòåéíàçûâàåòñÿ îïòèìàëüíûì âõîäíûì äåðåâîì .Ñóùåñòâîâàíèå îïòèìàëüíîãî âõîäíîãî äåðåâà îçíà÷àåò, ÷òîàëãîðèòì îïòèìàëüíîé ìàðøðóòèçàöèè ìîæåò ðàáîòàòü ñèñïîëüçîâàíèåì ñëåäóþùåé ëîêàëüíîé ïðîöåäóðûtable_lookupv .Ïðîöåäóðà table_lookupv èìååò îäèí àðãóìåíò è âûáèðàåòîäíîãî èç ñîñåäåé âåðøèíûóçëóuv.

Ò.ê. âñå ïàêåòû, àäðåñîâàííûåîïòèìàëüíî íàïðàâèòü ïî îñòîâíîìó äåðåâóTu,ïðîäâèæåíèå ïàêåòà áóäåò îïòèìàëüíûì, åñëè äëÿ êàæäîéâåðøèíûv 6= uïðîöåäóðàtable_lookupv (u) áóäåò âû÷èñëÿòüðîäèòåëüñêóþ âåðøèíó óçëàvâ äåðåâåTu.Ìàðøðóòèçàöèÿ íà îñíîâå óçëîâ-àäðåñàòîâ(* Ïàêåò, àäðåñîâàííûé âåðøèíåâ âåðøèíåuu,áûë ïîëó÷åí èëè ñôîðìèðîâàí*)if v = uthen äîñòàâèòü ïàêåò ëîêàëüíûìèelse îòïðàâèòü ïàêåò âåðøèíåñðåäñòâàìètable_lookupv (u)Àëãîðèòì îïòèìàëüíîãî ïðîäâèæåíèÿ ïàêåòîâ.Ìàðøðóòèçàöèÿ íà îñíîâå óçëîâ-àäðåñàòîâÍî âïîëíå âîçìîæíà ¾ìàëåíüêàÿ íåïðèÿòíîñòü¿: ðàçíûå óçëûìîãóò èìåòü â âèäó ðàçíûå âõîäíûå äåðåâüÿ. Íå ñëó÷èòñÿ ëèòàê, ÷òî ïàêåò áóäåò ¾ïåðåäàâàòüñÿ ïî êðóãó¿?Ìàðøðóòèçàöèÿ íà îñíîâå óçëîâ-àäðåñàòîâÍî âïîëíå âîçìîæíà ¾ìàëåíüêàÿ íåïðèÿòíîñòü¿: ðàçíûå óçëûìîãóò èìåòü â âèäó ðàçíûå âõîäíûå äåðåâüÿ.

Íå ñëó÷èòñÿ ëèòàê, ÷òî ïàêåò áóäåò ¾ïåðåäàâàòüñÿ ïî êðóãó¿?Äëÿ äîêàçàòåëüñòâà êîððåêòíîñòè òàáëèö ìàðøðóòèçàöèèïîëåçåí ñëåäóþùèé ðåçóëüòàò. Áóäåì ãîâîðèòü, ÷òî òàáëèöûu ) ñîäåðæàòu1 , . . . , uk , ÷òîìàðøðóòèçàöèè (äëÿ óçëà-àäðåñàòàñóùåñòâóþò òàêèå âåðøèíûIIIui 6= uäëÿ âñåõiöèêë , åñëè,table_lookupu (u) = ui+1 äëÿ âñåõ i < k ètable_lookupu (u) = u1 .ikÒàáëèöû íàçûâàþòñÿ àöèêëè÷åñêèìè , åñëè îíè íå ñîäåðæàòöèêëà íè äëÿ îäíîé âåðøèíûu.Ìàðøðóòèçàöèÿ íà îñíîâå óçëîâ-àäðåñàòîâÍî âïîëíå âîçìîæíà ¾ìàëåíüêàÿ íåïðèÿòíîñòü¿: ðàçíûå óçëûìîãóò èìåòü â âèäó ðàçíûå âõîäíûå äåðåâüÿ.

Íå ñëó÷èòñÿ ëèòàê, ÷òî ïàêåò áóäåò ¾ïåðåäàâàòüñÿ ïî êðóãó¿?Äëÿ äîêàçàòåëüñòâà êîððåêòíîñòè òàáëèö ìàðøðóòèçàöèèïîëåçåí ñëåäóþùèé ðåçóëüòàò. Áóäåì ãîâîðèòü, ÷òî òàáëèöûu ) ñîäåðæàòu1 , . . . , uk , ÷òîìàðøðóòèçàöèè (äëÿ óçëà-àäðåñàòàñóùåñòâóþò òàêèå âåðøèíûIIIui 6= uäëÿ âñåõiöèêë , åñëè,table_lookupu (u) = ui+1 äëÿ âñåõ i < k ètable_lookupu (u) = u1 .ikÒàáëèöû íàçûâàþòñÿ àöèêëè÷åñêèìè , åñëè îíè íå ñîäåðæàòöèêëà íè äëÿ îäíîé âåðøèíûu.Ëåììà 5.2. (îá àöèêëè÷åñêèõ òàáëèöàõ)Ìåõàíèçì ïðîäâèæåíèÿ äîñòàâëÿåò êàæäûé ïàêåò ïîíàçíà÷åíèþ â òîì è òîëüêî òîì ñëó÷àå, êîãäà òàáëèöûìàðøðóòèçàöèè ÿâëÿþòñÿ àöèêëè÷åñêèìè.Ìàðøðóòèçàöèÿ íà îñíîâå óçëîâ-àäðåñàòîâÄîêàçàòåëüñòâîÅñëè òàáëèöû ìàðøðóòèçàöèè ñîäåðæàò öèêë äëÿ íåêîòîðîãîóçëà-àäðåñàòàu, òî ïàêåò, àäðåñîâàííûé ïðîöåññóu, íèêîãäàíå áóäåò äîñòàâëåí ïî íàçíà÷åíèþ èç óçëà, âõîäÿùåãî â öèêë.Ïðåäïîëîæèì, ÷òî òàáëèöû ÿâëÿþòñÿ àöèêëè÷åñêèìè, è ïàêåò,ïðåäíàçíà÷åííûé óçëó-àäðåñàòóóçëà-èñòî÷íèêàu0uè îòïðàâëåííûé èç, ïðîäâèíóëñÿ ÷åðåç âåðøèíûu0 , u1 , u2 , .

. .Åñëè îäíà è òà æå âåðøèíà âñòðå÷àåòñÿ â ýòîéïîñëåäîâàòåëüíîñòè äâàæäû, òî òàáëèöû ñîäåðæàò öèêëâîïðåêè ïðåäïîëîæåíèþ îá àöèêëè÷íîñòè òàáëèö.Çíà÷èò êàæäàÿ âåðøèíà âñòðå÷àåòñÿ â ïîñëåäîâàòåëüíîñòè íåáîëåå îäíîãî ðàçà. Ïîýòîìó ýòà ïîñëåäîâàòåëüíîñòü ÿâëÿåòñÿêîíå÷íîé, è îêàí÷èâàåòñÿ íåêîòîðîé âåðøèíîéuk (k < N). ñîîòâåòñòâèè ñ îïèñàíèåì ïðîöåäóðû ïðîäâèæåíèÿ ïàêåòàóêàçàííàÿ ïîñëåäîâàòåëüíîñòü ìîæåò îêàí÷èâàòüñÿ òîëüêîâåðøèíîéu..Ìàðøðóòèçàöèÿ íà îñíîâå óçëîâ-àäðåñàòîâÇàäà÷à.Äîïóñòèì, ÷òî òàáëèöû ìàðøðóòèçàöèè òàê îáíîâëÿþòñÿ ïîñëåêàæäîãî èçìåíåíèÿ òîïîëîãè÷åñêîé ñòðóêòóðû ñåòè, ÷òî îíèîñòàþòñÿ àöèêëè÷åñêèìè ïî õîäó îáíîâëåíèÿ.

Ìîæåò ëè ýòîñëóæèòü ãàðàíòèåé òîãî, ÷òî ïàêåòû âñåãäà äîñòàâëÿþòñÿ ïîàäðåñó äàæå â òîì ñëó÷àå, êîãäà ñåòü ïðåòåðïåâàåò áåñêîíå÷íîáîëüøîå êîëè÷åñòâî òîïîëîãè÷åñêèõ èçìåíåíèé?Äîêàæèòå, ÷òî íè îäèí àëãîðèòì ìàðøðóòèçàöèè íå ñïîñîáåíîáåñïå÷èòü äîñòàâêó ïàêåòîâ ïî àäðåñó, åñëè ñåòü èñïûòûâàåòíåïðåðûâíûå èçìåíåíèÿ òîïîëîãèè.Çàäà÷à ïîñòðîåíèÿ êðàò÷àéøèõ ïóòåé äëÿ âñåõïàð âåðøèíÄëÿ êàæäîé ïàðû âåðøèí(u, v )àëãîðèòì äîëæåí âû÷èñëèòüäëèíó êðàò÷àéøåãî ïóòè èç âåðøèíûïàìÿòü ïðîöåññàuuâ âåðøèíóïåðâûé êàíàë ýòîãî ïóòè.vè çàíåñòè âÇàäà÷à ïîñòðîåíèÿ êðàò÷àéøèõ ïóòåé äëÿ âñåõïàð âåðøèíÄëÿ êàæäîé ïàðû âåðøèí(u, v )àëãîðèòì äîëæåí âû÷èñëèòüäëèíó êðàò÷àéøåãî ïóòè èç âåðøèíûïàìÿòü ïðîöåññàuuâ âåðøèíóvè çàíåñòè âïåðâûé êàíàë ýòîãî ïóòè.Ìû ðàññìîòðèì àëãîðèòì Òóýãà (Toueg) ñîâìåñòíîãîðàñïðåäåëåííîãî âû÷èñëåíèÿ òàáëèö ìàðøðóòèçàöèè äëÿ âñåõóçëîâ ñåòè.  îñíîâó ýòîãî àëãîðèòìà ïîëîæåíöåíòðàëèçîâàííûé àëãîðèòì ÔëîéäàÓîðøàëëà.Àëãîðèòì ÔëîéäàÓîðøàëëàG = (V , E )Ïðåäïîëîæèì, ÷òî èìååòñÿ âçâåøåííûé ãðàôêîòîðîì êàæäîìó ðåáðóuvïðèïèñàí âåñωuv, â.Ìû áóäåì ñ÷èòàòü, ÷òî â ãðàôå îòñóòñòâóþò öèêëûîòðèöàòåëüíîãî âåñà.Âå ïóòèhu0 , .