Изменения

{{ОпределениеЗадача|definition= '''Кратчайший путь''' Пусть дан [[Основные_определения_теории_графов |ациклический ориентированный взвешенный граф]]. Требуется найти вес [[Алгоритм_Дейкстры |кратчайшего пути]] из '''<tex>u''' </tex> в '''<tex>v''' – это любой путь '''p''' </tex>. }} ==Решение==Воспользуемся принципом оптимальности на префиксе.<br />Пусть <tex>d</tex> — функция, где <tex>d(i)</tex> — вес кратчайшего пути из '''<tex>u '''</tex> в '''v'''<tex>i</tex>. Ясно, для которого что <tex> wd(pu) = \delta</tex> равен <tex>0</tex>. Пусть <tex>w(ui, vj)</tex>, где{{---}} вес ребра из <tex>i</tex> в <tex>j</tex>. Будем обходить граф в порядке [[Использование_обхода_в_глубину_для_топологической_сортировки | топологической сортировки]]. Получаем следующие соотношения: <br/>* : <tex>d(i) = \boldsymbol min\limits_{\mathop{j:j \rightsquigarrow i}} (d(j) + w(pj, i)) </tex> Так как мы обходим граф в порядке [[Использование_обхода_в_глубину_для_топологической_сортировки |топологической сортировки]], то на <tex>i</tex>-ом шаге всем <tex>d(j)</tex> (<tex>j</tex> такие, что существует ребро из <tex>j</tex> в <tex>i</tex>) уже присвоены оптимальные ответы, и, следовательно, <tex>d(i) </tex> также будет присвоен оптимальный ответ. ==Реализация==Реализуем данный алгоритм: <font color= сумма весов всех ребер пути green>//w {{---}} матрица смежности</font> <font color=green>//d {{---}} массив кратчайших расстояний</font> <font color=green>//p {{---}} массив индексов вершин графа в порядке топологической сортировки</font>* '''for''' i = 1 .. n d[i] = <tex>\rm{\delta}(infty</tex> d[u, v) ] = 0 <font color= \left\green>// где u {\begin{array---}{llcl}начальная вершина</font><br /> p = topSort(w) <font color=green>//топологическая сортировка графа</font> '''for''' i = 1 .. n '''for''' j: есть ребро из p[i] в j d[j] = min(d[j], d[p[i]] + w[p[i]][j]) <br />

min \text==Пример==[[Файл:WayAcyclicGraph.png|thumb|right|500px|Граф из примера]]Пусть дана матрица смежности графа <tex>w</tex> со следующими весами ребер: <br />{ } \omega(p) \text{ for all ways p from u to v} &| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;if "|-| || '''1''' || '''2''' || '''3''' || '''4''' || '''5''' || '''6''' || '''7''' || '''8'''|-| '''1''' || - || - || - || - || 2 || - || - || - |-| '''2''' || 1 || - || 1 || - || 4 || 3 || - || - |-| '''3''' || - || - || - || - || - || 1 || - || - |-| '''4''' || - || - || - || - || - || - || - || - |-| '''5''' || - || - || - || 3 || \text{ }\mathcal{9- || - || - || 1 |-| '''6''' || - || - || - || 5 || - || - || 2 || - |-| '''7''' || - || - || - || 2 || - || - || - || - |-| '''8''' || - || - || - || 1 || - || - || - || - |} Требуется найти вес кратчайшего пути из '''2''' в '''4'''. <br />Массив <tex>p \\</tex> будет выглядеть следующим образом: <br />\mathcal{| class="wikitable" cellpadding="4" border="1}&" style="border-collapse: collapse;if \text{ } \nexists "|-| <tex>i</tex> || '''1''' || '''2''' || '''3''' || '''4''' || '''5''' || '''6''' || '''7''' || '''8'''|-| <tex>p\\[i]</tex> || 2 || 3 || 6 || 7 || 1 || 5 || 8 || 4\end{array|}\right.Массив <tex>d</tex> будет выглядеть следующим образом: <br />}}{| class="wikitable" cellpadding=Принцип оптимальности на префиксе"4" border="1" style="border-collapse: collapse;"Префикс оптимального решения сам является оптимальным решением (в другой подзадаче)|-| <tex>i<br/tex>|| '''1''' || '''2''' || '''3''' || '''4''' || '''5''' || '''6''' || '''7''' || '''8'''|-| <tex>a \rightsquigarrow b \rightsquigarrow c d[i]</tex> || 1 || 0 || 1 || 5 || 3 || 2 || 4 || 4|} Ответ равен <brtex>Если ac - оптимальное решение , то и ab (префикс ac) тоже является оптимальным решением.5<br/tex>.

== Альтернативный способ решения==Решим задачу, используя [[Обход_в_ширину |обход в ширину]]. Для этого заведем массив, в котором будем хранить веса кратчайших расстояний от начальной вершины до всех остальных. Совершая обход по графу, будем в каждой вершине для всех ее потомков проверять, уменьшится ли вес кратчайшего пути до сына, если пройти через текущую вершину. Если да, то весу кратчайшего расстояния до сына присваиваем значение, равное сумме веса кратчайшего расстояния до текущей вершины и стоимости прохода по ребру между вершиной и ее сыном.В силу особенности обхода графа, обновление весов кратчайших путей до сыновей вершины происходит только тогда, когда для нее уже найден оптимальный ответ.

Для нахождения кратчайшего пути в графе заведем функцию переменную opt==См. также==*[x[Алгоритм_Флойда_—_Уоршалла |Алгоритм Флойда—Уоршалла]], в которой хранится длина кратчайшего пути до вершины х.<br>В общем случае мы можем написать: <br><tex>opt*[[uАлгоритм_Форда-Беллмана |Алгоритм Форда-Беллмана] = min_{v,u \in E} (opt[v] + cost(vu))</tex>, где cost(vu) - вес ребра из u в v. <br>Будем обходить вершины в порядке, обратном к топологической сортировке.

==Источники информации==*[http://www.ics.uci.edu/~eppstein/161/960208.html Алгоритмы поиска кратчайшего пути в графе]* [http://en.wikipedia.org/wiki/Optimal_substructure Wikipedia {{---}} Optimal substructure][[Категория:Дискретная математика и алгоритмы]][[Категория: Динамическое программирование ]]