188
правок
Изменения
Нет описания правки
{{Задача|definition=Для заданного взвешенного графа <tex>G = (V, E)</tex> алгоритм находит найти кратчайшие пути из заданной вершины <tex> s </tex> до всех остальных вершин.В, случае, когда в графе <tex>G</tex> содержатся отрицательные циклы, достижимые из <tex>s</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] = +\infty </tex>
{{Лемма
|statement=Если существует кратчайший путь от <tex>s</tex> до <tex>t</tex>, то <tex> \rho(s, \, t) \: = \: \min\limits_{k = 0..n-1} d[k][t]</tex>
{{Лемма
|statement=Пусть <tex>G = (V, E)</tex> — взвешенный ориентированный граф, <tex> s </tex> — стартовая вершина.
Тогда после завершения <tex>k</tex> итераций цикла <tex>\mathrm{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>d[v]</tex> уменьшается до тех пор, пока не станет равным <tex>\delta(s, v)</tex>.
<tex>d[v]</tex> {{- --}} оценка веса кратчайшего пути из вершины <tex>s</tex> в каждую вершину <tex>v \in V</tex>.<br><tex>\delta(s, v)</tex> {{--- }} фактический вес кратчайшего пути из <tex>s</tex> в вершину <tex>v</tex>.
{{Лемма
|statement=Пусть <tex>G = (V, E) </tex> — {{---}} взвешенный ориентированный граф, <tex> s </tex> — {{---}} стартовая вершина. Тогда после завершения <tex> |V| - 1 </tex> итераций цикла для всех вершин, достижимых из <tex>s</tex>, выполняется равенство <tex> d[v] = \delta (s, v) </tex>.
|proof=Рассмотрим произвольную вершину <tex>v</tex>, достижимую из <tex>s</tex>.
Пусть <tex>p = \langle v_0,..., v_{k} \rangle </tex>, где <tex>v_0 = s</tex>, <tex>v_{k} = v</tex> — {{---}} кратчайший ациклический путь из <tex> s </tex> в <tex> v </tex>. Путь <tex> p </tex> содержит не более <tex> |V| - 1 </tex> ребер. Поэтому <tex>k \le |V| - 1</tex>.
Докажем следующее утверждение:
{{Теорема
|statement=Пусть <tex>G = (V, E) </tex> - взвешенный ориентированный граф, <tex> s </tex> — {{---}} стартовая вершина. Если граф <tex> G </tex> не содержит отрицательных циклов, достижимых из вершины <tex> s </tex>, то алгоритм возвращает <tex> true </tex> и для всех <tex> v \in V \ d[v] = \delta (s, v)</tex>. Если граф <tex> G </tex> содержит отрицательные циклы, достижимые из вершины <tex> s </tex>, то алгоритм возвращает <tex> false </tex>.
|proof=Пусть граф <tex> G </tex> не содержит отрицательных циклов, достижимых из вершины <tex> s </tex>.
