68
правок
Изменения
Нет описания правки
{{Задача
|definition =
Пусть дан [[Основные_определения_теории_графов |ациклический ориентированный взвешенный граф]]. Требуется найти вес [[Алгоритм_Дейкстры |кратчайшего пути ]] из <tex>u</tex> в <tex>v</tex>.
}}
==Решение==
Пусть <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 />
==См. также==
*[[Алгоритм_Флойда_—_Уоршалла |Алгоритм Флойда—Уоршалла]]
*[[Алгоритм_Форда-Беллмана |Алгоритм Форда-Беллмана]]
