Изменения

{{ОпределениеЗадача|definition= '''Кратчайший путь''' Пусть дан [[Основные_определения_теории_графов |ациклический ориентированный взвешенный граф]]. Требуется найти вес [[Алгоритм_Дейкстры |кратчайшего пути]] из '''<tex>u''' </tex> в '''<tex>v''' – это любой путь '''p''' </tex>. }} ==Решение==Воспользуемся принципом оптимальности на префиксе.<br />Пусть <tex>d</tex> — функция, где <tex>d(i)</tex> — вес кратчайшего пути из '''<tex>u '''</tex> в '''v'''<tex>i</tex>. Ясно, для которого что <tex> w(p) = \deltad(u, v)</tex>, где: равен <tex>0<br/tex>* . Пусть <tex>\boldsymbol w(pi, j) </tex> = сумма весов всех ребер пути p {{---}} вес ребра из <tex>i</tex> в <tex>j</tex>. Будем обходить граф в порядке [[Использование_обхода_в_глубину_для_топологической_сортировки | топологической сортировки]]. Получаем следующие соотношения: <br />*: <tex>\rm{\delta}d(u, vi) = \leftmin\limits_{\beginmathop{arrayj:j \rightsquigarrow i}{llcl}(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> также будет присвоен оптимальный ответ.

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

== См. также==*[[Алгоритм_Флойда_—_Уоршалла |Алгоритм Флойда—Уоршалла]]*[[Алгоритм_Форда-Беллмана |Алгоритм Форда-Беллмана]]

Для нахождения ==Источники информации==*[http://www.ics.uci.edu/~eppstein/161/960208.html Алгоритмы поиска кратчайшего пути в графе заведем функцию переменную opt]* [xhttp://en.wikipedia.org/wiki/Optimal_substructure Wikipedia {{---}} Optimal substructure], в которой хранится длина кратчайшего пути до вершины х.<br>В общем случае мы можем написать[[Категория: <br>Дискретная математика и алгоритмы]]<tex>opt[u[Категория:Динамическое программирование] = min_{v,u \in E} (opt[v] + cost(vu))</tex>, где cost(vu) - вес ребра из u в v. <br>Будем обходить вершины в порядке, обратном к топологической сортировке.