48
правок
Изменения
Нет описания правки
==Пример==
[[Файл:Graph_anticycle.jpg|thumb|right|180px|граф из примера]]
Пусть дан граф со следующими весами '''w''' ребер: <br />
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"
| || '''1''' || '''2''' || '''3''' || '''4'''
|-
| '''1''' || 0 || 1 - || 1 - || 41
|-
| '''2''' || - 2 || 0 || - 1 || 2-
|-
| '''3''' || - || - || 0 || 1
| '''4''' || - || - || - || 0
|}
Требуется найти путь из '''1''' в '''4'''. матрица d Матрица p будет выглядеть следующим образом: <br />
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"
|-
| '''1''' || '''2''' || '''3''' || '''4'''
|-
| 0 2 || 1 || 3 || 4|}Матрица d будет выглядеть следующим образом: <br />{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"|-| '''1 ''' || '''2''' || '''3''' || '''4'''|-| 1 || 0 || 2 || 2
|}
Ответ будет равен 2.
==Источники==
* [http://ru.wikipedia.org/wiki/Динамическое_программирование Википедия]
[[Категория: Динамическое программирование ]]
