1632
правки
Изменения
м
rollbackEdits.php mass rollback
{{Задача
|definition=Для заданного взвешенного [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графа]] <tex>G = (V, E)</tex> найти кратчайшие пути из заданной вершины <tex> s </tex> до всех остальных вершин.
В случае, когда в графе <tex>G</tex> содержатся отрицательные [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|циклы]]с отрицательным суммарным весом, достижимые из <tex>s</tex>, сообщить, что кратчайших путей не существует.
}}
Используя приведенные формулы, алгоритм можно реализовать методом динамического программирования.
'''for''' k = 1 0 '''to''' <tex>|V| - 12</tex> <font color="green">// вершины нумеруются с единицы</font>
'''for''' <tex>v \in V</tex>
'''for''' <tex> (u, v) \in E </tex>
d[k + 1][uv] = min(d[k + 1][uv], d[k][vu] + <tex>\omega(u, v)</tex>) <font color="green">// <tex>\omega(u, v)</tex> {{---}} вес ребра uv</font>
Также релаксацию можно свести к одномерному случаю, если не хранить длину пути в рёбрах. Одномерный массив будем обозначать <tex>d'</tex>, тогда <tex>d'[u] = \min(d'[u], \; d'[v] + \omega(vu))</tex>
p[v] = -1
d[s] = 0
'''for''' i = 0 1 '''to''' <tex>|V| - 1</tex>
'''for''' <tex> (u, v) \in E </tex>
'''if''' d[v] > d[u] + <tex>\omega(u, v)</tex>
