48
правок
Изменения
Нет описания правки
==Решение==
Пусть d — матрица, где d[i] — вес кратчайшего пути из '''u''' в '''i'''. Изначально значения d равны бесконечности, кроме d[u], который равен 0. Пусть w[i][j] - вес ребра из '''i''' в '''j'''. Будем обходить граф в порядке топологической сортировки. Получаем следующие соотношения: <br />
Так как мы обходим граф в порядке топологической сортировки, то на i-ом шаге во всех d[j] (j такие, что: /exist ребро из j в i) уже записаны оптимальные ответы, и следовательно в d[i] так же будет записан оптимальный ответ.
==Реализация==
Реализуем данный алгоритм методом "динамика вперед":
//d, w - матрицы как в описании, p - матрица массив индексов вершин графа в порядке топологической сортировки, i, j - счетчики <br />
inputData() //считывание данных <br />
for i = 1 to n
d[i] = infinity <br />
p = topSort() //топологическая сортировка <br />
d[p[u]] = 0 <br />
for i = 1 to n
Ответ равен 2.
==Источники==
* [http://ruen.wikipedia.org/wiki/Динамическое_программирование ВикипедияOptimal_substructure Принцип оптимальности на подзадаче (в качестве примера разбирается задача поиска кратчайшего пути в ациклическом графе)(англ.)]
[[Категория: Динамическое программирование ]]
