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>
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>
