Дискретная математика: Основы теории графов и алгоритмизация задач. Прокушев Л.А. - 52 стр.

UptoLike

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

52
Íà ðèñ. 3.4 ïðåäñòàâëåíû ðåçóëüòàòû îáðàáîòêè ìàòðèöû äëèí äóã L
(ðèñ. 3.3) èñõîäíîãî ãðàôà íà ðèñ. 3.2 â ñîîòâåòñòâèè ñ àëãîðèòìîì Ôîðäà.
3.2. Ïîèñê ìàêñèìàëüíîãî ïóòè â ãðàôå áåç êîíòóðîâ
Àëãîðèòì Ôîðäà ìîæåò áûòü èñïîëüçîâàí äëÿ îòûñêàíèÿ ìàêñèìàëü-
íîãî ïóòè (èëè êðèòè÷åñêîãî ïóòè â çàäà÷å ñåòåâîãî ïëàíèðîâàíèÿ è óï-
ðàâëåíèÿ) â àöèêëè÷åñêîì ãðàôå. Äîñòàòî÷íî ïîëîæèòü íà÷àëüíûå ìåòêè
âåðøèí λ
i
=0, i=0, 1, 2, , n, à çàòåì çàìåíÿòü λ
j
íà λ'
j
=λ
i
+L(v
i,
v
j
), åñëè
λ'
j
>λ
j
, äî òåõ ïîð, ïîêà âîçìîæíî óâåëè÷èâàòü λ
j
.
v
$
[19]
4
2
4
v
"
[11]v
[7]
v
[0]
v
#
[13]
6
8
7
9
v
!
[9]
M:
ûíèøðå 0123456
èêòåÌ0789113191
à)
á)
â)
Ðèñ. 3.4. Ðåçóëüòàòû ïîèñêà ìèíèìàëüíûõ ïóòåé â ãðàôå: à âåêòîð ìåòîê
M (äëèí êðàò÷àéøèõ ïóòåé îò âåðøèíû v
0
äî îñòàëüíûõ); á ïîäãðàô êðàò-
÷àéøèõ ïóòåé îò âåðøèíû v
0
äî v
6
; â ìàòðèöà äëèí ïóòåé (Ê) ïîäãðàôà
K :
0 E 23456
00709000
10000400
20000000
30000240
40000008
50000006
60000000
1