Изменения
→Пример
{{ОпределениеЗадача|definition= '''Кратчайший путь''' из '''u''' в '''v''' – это любой путь '''p''' из '''u '''в '''v''', для которого <math>\boldsymbol w(p) = \delta(u, v)</math>, где: <br>* <math>\boldsymbol w(p)</math> = сумма весов всех ребер Пусть дан [[Основные_определения_теории_графов |ациклический ориентированный взвешенный граф]]. Требуется найти вес [[Алгоритм_Дейкстры |кратчайшего пути p*]] из <mathtex>\boldsymbol \delta(u,v) = \boldsymbol {min}</mathtex> в <math> \boldsymbol\omega(p)</mathtex> : по всем путям p из u в v, если существует путь u в v <math>\mathcal{1}</mathtex> - в противном случае.
}}
== Решение==Воспользуемся принципом оптимальности на префиксе.<br />Пусть <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 />: <tex> d(i) = \min\limits_{\mathop{j:j \rightsquigarrow i}} (d(j) + w(j, i)) </tex>