Изменения

{{ОпределениеЗадача|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{ for all ways p from u to v} ;&if \text{ ---}\mathcal{9} p массив индексов вершин графа в порядке топологической сортировки</font> '''for''' i = 1 .. n d[i] = <tex>\\infty</tex>\mathcal d[u] = 0 <font color=green>// где u {{1---};&if \text{ } \nexists начальная вершина</font><br /> p\\= topSort(w) <font color=green>//топологическая сортировка графа</font>\end{array}\right '''for''' i = 1 ..n '''for''' j: есть ребро из p[i] в j d[j] = min(d[j], d[p[i]] + w[p[i]][j]) <br /tex>}}

==Принцип оптимальности на префиксеАльтернативный способ решения==Префикс оптимального решения сам является оптимальным решением (Решим задачу, используя [[Обход_в_ширину |обход в ширину]]. Для этого заведем массив, в котором будем хранить веса кратчайших расстояний от начальной вершины до всех остальных. Совершая обход по графу, будем в другой подзадаче)<br><tex>a \rightsquigarrow b \rightsquigarrow c </tex> <br>каждой вершине для всех ее потомков проверять, уменьшится ли вес кратчайшего пути до сына, если пройти через текущую вершину. Если 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>Будем обходить вершины в порядке, обратном к топологической сортировке.