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