147
правок
Изменения
Переделывание под изложение как на лекции
:Для заданного взвешенного графа <tex>G = (V, E)</tex> алгоритм находит кратчайшие пути из заданной вершины <tex> s </tex> до всех остальных вершин.<br>
:В случае когда в графе <tex> G </tex> содержатся отрицательные циклы достижимые из <tex> s </tex> алгоритм сообщает, что кратчайших путей не существует.
==Введение==
:Сначала стоит вспомнить формулу для пути длины <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>
==Псевдокод==
:Используя приведенные формулы, алгоритм можно реализовать методом динамического программирования.
'''for''' <tex>(k = 0..n-2)</tex>
'''for''' <tex>(v \in V)</tex>
'''for''' <tex>(u : vu \; \in E)</tex>
<tex>d[k][u] \gets \min(d[k+1][u], \; d[k][v] + \omega(u,v))</tex>
==Корректность алгоритма Форда-Беллмана==
