48
правок
Изменения
Нет описания правки
{{Определение|definition= '''Кратчайший путь''' из '''u''' в '''v''' – это такой путь из '''u '''в '''v''', что его вес меньше или равен веса любого другого пути из '''u''' в '''v'''}}
==Решение==
Пусть d — матрицамассив, где d[i] — вес кратчайшего пути из u в i. Изначально значения d равны бесконечности, кроме d[u], который равен 0. Пусть w[i][j] - вес ребра из i в j. Будем обходить граф в порядке топологической сортировки. Получаем следующие соотношения: <br />
: <tex> d[i] = \min\limits_{\mathop{j:j \rightsquigarrow i}} (d[j] + w[j][i]) </tex>
for i = 1 to n
d[i] = infinity <br />
p = topSort(w) //топологическая сортировка графа <br />
d[p[u]] = 0 <br />
for i = 1 to n
for j: <tex> \exists p[i] \rightsquigarrow смежно с j </tex>
d[j] = min(d[j], d[p[i]] + w[p[i]][j]) <br />
writeData(); // запись данных
==Источники==
*[http://www.ics.uci.edu/~eppstein/161/960208.html Алгоритмы поиска кратчайшего пути в графе]
*[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 Принцип оптимальности на подзадаче (в качестве примера разбирается задача поиска кратчайшего пути в ациклическом графе)(англ.)]
[[Категория: Динамическое программирование ]]
