188
правок
Изменения
Нет описания правки
Пусть <tex>d[k][u]</tex> {{---}} количество путей длины <tex>k</tex> рёбер, заканчивающихся в вершине <tex>u</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](u, v))</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>
Используя приведенные формулы, алгоритм можно реализовать методом динамического программирования.
'''for''' k = 0 1 '''to''' n <tex>|V| - 21</tex> <font color="green">// вершины нумеруются с единицы</font>
'''for''' <tex>v \in V</tex>
'''for''' <tex> (u, v) \in E </tex>
d[k + 1][u] = min(d[k + 1][u], d[k][v] + <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>
==Корректность==
