Изменения

Сначала стоит вспомнить формулу для количества Количество путей длины <tex>k</tex>можно найти с помощью метода [[Динамическое_программирование|динамического программирования]].<br>Пусть <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])</tex>, при этом <tex>d[0][s] = 0</tex>, а <tex>d[0][u] = +\infty </tex>

<tex>d'[u] \gets = \min(d'[u], \; d'[v] + \omega(vu))</tex>

'''if''' d[v] > d[u] + <tex>\omega(u, v)</tex> <font color="green">// <tex>\omega(u, v)</tex> {{- --}} вес ребра uv</font>

ans.add(v) <font color="green">// добавим вершину к ответу</font>

* Томас Х. Кормен, ТЧарльз И., Лейзерсон, ЧРональд Л., Ривест, Р., Клиффорд Штайн, К. Алгоритмы: построение и анализ / пер. с англ. — изд. 2-е изд — М.: Издательский дом «Вильямс», 2009. — с.672 — 676. — ISBN 978-5-8459-0857-5.* [http://e-maxx.ru/algo/export_ford_bellman ford_bellman MAXimal :: algo :: Алгоритм Форда-Беллмана]