1632
правки
Изменения
м
Задачу так же можно решить Решим задачу, используя [[Обход_в_ширину |поиском обход в ширину]]. Для этого заведем массив, в котором будем поддерживать массив кратчайший хранить веса кратчайших расстояний от начальной вершины до текущей вершинывсех остальных. Обходя граф в ширинуСовершая обход по графу, будем в каждой вершине для каждой вершины обновлять ответы у всех ее сыновей как минимум из старого значения и потомков проверять, уменьшится ли вес кратчайшего путидо сына, проходящего если пройти через текущую вершину.Если да, то весу кратчайшего расстояния до сына присваиваем значение, равное сумме веса кратчайшего расстояния до текущей вершины и стоимости прохода по ребру между вершиной и ее сыном.В силу особенности обхода графа, когда происходит обновление весов кратчайших путей до сыновей вершиныпроисходит только тогда, когда для нее самой уже найден оптимальный ответ.
*[[Алгоритм_Дейкстры |Алгоритм Дейкстры]]
*[[Динамическое_программирование#.D0.9F.D1.80.D0.B8.D0.BD.D1.86.D0.B8.D0.BF_.D0.BE.D0.BF.D1.82.D0.B8.D0.BC.D0.B0.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8_.D0.BD.D0.B0_.D0.BF.D1.80.D0.B5.D1.84.D0.B8.D0.BA.D1.81.D0.B5|Принцип оптимальности на префиксе]]* [http://en.wikipedia.org/wiki/Optimal_substructure Принцип оптимальности на подзадаче (в качестве примера разбирается задача поиска кратчайшего пути в ациклическом графе)(англ.)Wikipedia {{---}} Optimal substructure]
rollbackEdits.php mass rollback
{{Задача|definition = Пусть дан [[Основные_определения_теории_графов |ациклический ориентированный взвешенный граф]]. Требуется найти вес [[Алгоритм_Дейкстры |кратчайшего пути ]] из '''<tex>u''' </tex> в '''<tex>v''' </tex>. {{Определение|definition= '''Кратчайший путь''' из вершины '''u''' в вершину '''v''' – это такой путь из вершины '''u '''в вершину '''v''', что его суммарный вес входящих в него ребер минимален}}
==Решение==
Воспользуемся принципом оптимальности на префиксе.<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>
<font color=green>//p {{---}} массив индексов вершин графа в порядке топологической сортировки</font>
'''for''' i = 1 .. n
d[i] = '''infinity'''<tex>\infty</tex>
d[u] = 0 <font color=green>// где u {{---}} начальная вершина</font><br />
p = topSort(w) <font color=green>//топологическая сортировка графа</font>
==Пример==
[[Файл:WayAcyclicGraph.png|thumb|right|500px|Граф из примера]]
Пусть дана матрица смежности графа '''<tex>w''' </tex> со следующими весами ребер: <br />
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"
|-
| || '''1''' || '''2''' || '''3''' || '''4''' || '''5''' || '''6''' || '''7''' || '''8'''
|-
| '''1''' || - || - || - || 5 - || - 2 || - || - || -
|-
| '''2''' || 1 || - || 1 || - || 4 || 3 || - || -
| '''8''' || - || - || - || 1 || - || - || - || -
|}
Требуется найти путь вес кратчайшего пути из '''2''' в '''4'''. <br />Массив <tex>p </tex> будет выглядеть следующим образом: <br />
{| 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</tex> || '''1''' || '''2''' || '''3''' || '''4''' || '''5''' || '''6''' || '''7''' || '''8'''
|-
| <tex>d[i]</tex> || 1 || 0 || 1 || 5 || 3 || 2 || 4 || 4
|}
Ответ равен <tex>5</tex>.
==Альтернативный способ решения==
==Смотри См. также==*[[Обход_в_ширину | Обход в ширину]]
*[[Алгоритм_Флойда_—_Уоршалла |Алгоритм Флойда—Уоршалла]]
*[[Алгоритм_Форда-Беллмана |Алгоритм Форда-Беллмана]]
==Источники информации==
*[http://www.ics.uci.edu/~eppstein/161/960208.html Алгоритмы поиска кратчайшего пути в графе]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]
