68
правок
Изменения
м
Нет описания правки
Пусть дан ациклический ориентированный взвешенный граф. Требуется найти вес кратчайшего пути из '''u''' в '''v'''
{{Определение|definition= '''Кратчайший путь''' из вершины '''u''' в вершину '''v''' – это такой путь из вершины '''u '''в вершину '''v''', что его суммарный вес входящих в него ребер минимален}}
==Решение==
Пусть <tex>d</tex> — функция, где <tex>d(i)</tex> — вес кратчайшего пути из <tex>u</tex> в <tex>i</tex>. Ясно, что <tex>d(u)</tex> равен <tex>0</tex>. Пусть <tex>w(i, j)</tex> - вес ребра из <tex>i</tex> в <tex>j</tex>. Будем обходить граф в порядке [[Использование_обхода_в_глубину_для_топологической_сортировки | топологической сортировки]]. Получаем следующие соотношения: <br />
