147
правок
Изменения
Нет описания правки
{{В разработке}}
==Алгоритм==
:Для заданного взвешенного графа <tex>G = (V, E)</tex> алгоритм находит кратчайшие пути из заданной вершины <tex> s </tex> до всех остальных вершин.<br>
==Введение==
:Сначала стоит вспомнить формулу для пути количества путей длины <tex>k</tex>.
::<tex> d[k][u] = \sum\limits_{v : vu \; \in E} d[k-1][v] </tex>
:Теперь перепишем ее для пути кратчайшей длины. <tex>s</tex> {{---}} стартовая вершина.
::<tex> d[k][u] = \min\limits_{v : vu \; \in E}(d[k-1][v] \: + \: \omega[uv])</tex>, при этом <tex>d[0][s] = 0</tex>, а <tex>d[0][u] = +\inf </tex>
{{Лемма
|statement=Если существует кратчайший путь от <tex>s</tex> до <tex>t</tex>,<br> то <tex> \rho(s, \, t) \: = \: \min\limits_{k = 0..n-1} d[k][t]</tex>
|proof=
}}
==Псевдокод==
:Используя приведенные формулы, алгоритм можно реализовать методом динамического программирования.
'''for''' <tex>(k = 0\; ..\; n-2)</tex>
'''for''' <tex>(v \in V)</tex>
'''for''' <tex>(u : vu \; \in E)</tex>
<tex>d[k+1][u] \gets \min(d[k+1][u], \; d[k][v] + \omega(u,v))</tex>
:Также релаксацию можно свести к одномерному случаю (одномерный массив будем обозначать <tex>d'</tex>):
==Корректность алгоритма Форда-Беллмана==
{{Лемма
|statement=Пусть <tex>G = (V, E) </tex> — взвешенный ориентированный граф, <tex> s </tex> — стартовая вершина.<br>Тогда после завершения <tex>k</tex> итераций цикла <tex>for(k)</tex> выполняется неравенство <tex> \rho(s, u) \leqslant d'[u] \leqslant \min\limits_{i = 0..k} d[i][u]</tex>.
|proof=: Воспользуемся индукцией по <tex>k</tex>:
: '''База индукции.''' При <tex>k = 0</tex> выполнено: <tex>\rho(s, u) \leqslant +\inf \leqslant +\inf </tex>
: '''Индукционный переход.'''
::Сначала докажем, что <tex> \rho(s, u) \leqslant d'[u]</tex>.
::Предположим, что <tex>d'[u] + \omega(vu) \gtr \omega(Path(s \to v) \circ (vu))</tex>
}}
:В этом алгоритме используется релаксация, в результате которой <tex>d[v]</tex> уменьшается до тех пор, пока не станет равным <tex>\delta(s, v)</tex>. <br>
:<tex>d[v]</tex> - оценка веса кратчайшего пути из вершины <tex>s</tex> в каждую вершину <tex>v \in V</tex>.<br>
