48
правок
Изменения
Нет описания правки
Пусть дан ациклический ориентированный взвешенный граф. Требуется найти вес кратчайшего пути из '''u''' в '''v'''
{{Определение|definition= '''Кратчайший путь''' из '''u''' в '''v''' – это такой путь из '''u '''в '''v''', что его вес меньше или равен веса любого другого пути из '''u''' в '''v'''}}
==Решение==
==Реализация==
Реализуем данный алгоритм методом "динамика вперед":
//d, w - матрицы как в описании, d - массив как в описании, p - массив индексов вершин графа в порядке топологической сортировки, i, j - счетчики <br />
inputData() //считывание данных <br />
for i = 1 to n
*[http://neerc.ifmo.ru/mediawiki/index.php/%D0%9F%D1%80%D0%B8%D0%BD%D1%86%D0%B8%D0%BF_%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D0%BD%D0%B0_%D0%BF%D1%80%D0%B5%D1%84%D0%B8%D0%BA%D1%81%D0%B5 Принцип оптимальности на префиксе]
* [http://en.wikipedia.org/wiki/Optimal_substructure Принцип оптимальности на подзадаче (в качестве примера разбирается задача поиска кратчайшего пути в ациклическом графе)(англ.)]
[[Категория: Динамическое программирование ]] [[Категория: Дискретная математика и алгоритмы]]
