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

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

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

Рубрика: 

51
3.1.4. Îïèñàíèå ìàøèííîãî àëãîðèòìà Ôîðäà
Ïîñêîëüêó çàäà÷à ìîæåò èìåòü íåñêîëüêî âàðèàíòîâ ðåøåíèÿ, òî âîç-
ìîæíûé àëãîðèòì ìîæåò âêëþ÷àòü ñëåäóþùèå îñíîâíûå øàãè.
1. Ââîä ìàòðèöû äëèí äóã ãðàôà (L) è åå ðàçìåðà (n).
2. Óñòàíîâêà íà÷àëüíûõ çíà÷åíèé: 1) âåêòîðà ìåòîê: Ì
0
=0; i=1(1)n1,
Ì
i
=max; ãäå max ìàêñèìàëüíî äîïóñòèìîå ÷èñëî äàííîãî òèïà; 2)
îáíóëåíèå âñïîìîãàòåëüíîãî âåêòîðà âåðøèí, âõîäÿùèõ â êðèòè÷åñêèå
ïóòè, V è ìàòðèöû êðàò÷àéøèõ ïóòåé Ê.
Ïðÿìîé õîä
(Ðåàëèçàöèÿ ïðàâèë 3 è 4 àëãîðèòìà Ôîðäà  öèêëû ïîèñêà ñìåæíûõ
âåðøèí ãðàôà ïî ñòðîêàì i è ñòîëáöàì j è îáíîâëåíèå ìåòîê âåðøèí):
3. Öèêë i=0(1)n1 (ïî ñòðîêàì ìàòðèöû L)
4. Öèêë j=0(1)n1 (ïî ñòîëáöàì ìàòðèöû L)
åñëè (L
ij
>0 è Ì
j
Ì
i
>L
ij
) (åñòü ìåòêà,
òðåáóþùàÿ èçìåíåíèÿ, òî)
{ MN=M
i
+ L
ij
; (âû÷èñëåíèå íîâîé ìåòêè (MN) âåðøèíû j)
åñëè (MN < M
j
) (íîâàÿ ìåòêà ìåíüøå ñòàðîé, òî)
Ì
j
=MN; (èçìåíåíèå ìåòêè âåðøèíû j)
}
Îáðàòíûé õîä
(Ðåàëèçàöèÿ ïðàâèëà 5 àëãîðèòìà Ôîðäà ïîèñê âåðøèí êðàò÷àé-
øèõ ïóòåé):
5. V
n-1
=1; (êîíå÷íàÿ âåðøèíà êðàò÷àéøåãî ïóòè)
6. Öèêë j=n1(1)0 (îáðàòíûé öèêë ïî âåðøèíàì,
íà÷èíàÿ ñ ïîñëåäíåé)
åñëè (V
j
=1) (âåðøèíà âõîäèò â êðàò÷àéøèé ïóòü, òî)
7. Öèêë i=0(1)n1 (ïîèñê ïðåäøåñòâóþùèõ âåðøèí i,
ñìåæíûõ ñ âåðøèíîé j)
{åñëè (L
ij
>0 è Ì
j
Ì
i
=L
ij
) (ðàçíîñòü ìåòîê ñìåæíûõ
âåðøèí ðàâíà äëèíå äóãè ìåæäó íèìè, òî)
{ K
ij
= L
ij
; (çàïîëíåíèå ìàòðèöû êðàò÷àéøèõ ïóòåé)
V
i
=1; (âêëþ÷åíèå âåðøèíû i â âåêòîð V)
}
} (êîíåö öèêëîâ i è j)
8. Âûâîä ìàòðèöû ñìåæíîñòè Ê ( ïîäãðàôà êðàò÷àéøèõ ïóòåé) è
âåêòîðà ìåòîê âåðøèí M (äëèí êðàò÷àéøèõ ïóòåé îò âåðøèíû V
0
).
Ïî ìàòðèöå Ê íåîáõîäèìî ïîñòðîèòü äëÿ èñõîäíîãî ãðàôà ïîäãðàô
êðàò÷àéøèõ ïóòåé îò âåðøèíû v
0
ê v
n.

Страницы