Элементы теории графов. Домнин Л.Н. - 92 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

[c
i,j
]
(v
i
, v
j
)
i<j,
s
t
s t.
l(v
j
) v
j
v
i
∈Γ
−
(v
j
),
v
j
.
l(v
j
) = min
v
i
∈Γ
−
(v
j
)
[l(v
i
)+c
i,j
] ,
|Γ
−
(v
j
)|<j,
l(s)=l(v
1
)=0,
l(v
2
)=l(v
1
)+c
1,2
=c
1,2
, v
2
l(v
3
) =
= min
v
i
∈Γ
−
(v
3
)
[l(v
i
)+c
i,3
] l(v
4
)=
= min
v
i
∈Γ
−
(v
4
)
[l(v
i
)+c
i,4
]
s
v
1
v
13
    4.4.3. Àöèêëè÷åñêèå îðãðàôû
    Êðàò÷àéøèé ïóòü. Çàäà÷à îòûñêàíèÿ êðàò÷àéøåãî ïó-
òè â àöèêëè÷åñêîì îðãðàôå âïîëíå ìîæåò áûòü ðåøåíà ñ ïî-
ìîùüþ àëãîðèòìà Äåéêñòðû. Îäíàêî ñóùåñòâóåò áîëåå ýêîíî-
ìè÷íûé ñïîñîá, èñïîëüçóþùèé ñïåöèôèêó òàêèõ ãðàôîâ.
    Ïóñòü â àöèêëè÷åñêîì îðãðàôå ñ ìàòðèöåé âåñîâ [ci,j ] âåð-
øèíû ïðîíóìåðîâàíû òàê, ÷òî äëÿ ëþáîé äóãè (vi , vj ) âûïîë-
íÿåòñÿ îòíîøåíèå i

Страницы