Изменения
→Пример
{{Задача
|definition =
Пусть дан [[Основные_определения_теории_графов |ациклический ориентированный взвешенный граф]]. Требуется найти вес [[Алгоритм_Дейкстры |кратчайшего пути ]] из <tex>u</tex> в <tex>v</tex>.
}}
==Решение==
Воспользуемся принципом оптимальности на префиксе.<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>
| || '''1''' || '''2''' || '''3''' || '''4''' || '''5''' || '''6''' || '''7''' || '''8'''
|-
| '''1''' || - || - || - || 5 - || - 2 || - || - || -
|-
| '''2''' || 1 || - || 1 || - || 4 || 3 || - || -
==См. также==
*[[Алгоритм_Флойда_—_Уоршалла |Алгоритм Флойда—Уоршалла]]
*[[Алгоритм_Форда-Беллмана |Алгоритм Форда-Беллмана]]
==Источники информации==
*[http://www.ics.uci.edu/~eppstein/161/960208.html Алгоритмы поиска кратчайшего пути в графе]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]
