4551
правка
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 58: | Строка 58: | ||
r, t := 0, d | r, t := 0, d | ||
do <math>\{ P0 \and P1 \} \;</math> | do <math>\{ P0 \and P1 \} \;</math> | ||
<math> \neg P2 \to update \; t</math> | |||
<math> \neg P3 \to update \; r</math> | |||
do <math>\{ P0 \and P1 \and P2 \and P3 \} \;</math>. | |||
Первую команду цикла можно переписать в виде <math>\exist (u, v) \in E: r[u] - r[v] = w[u, v] \and t[v] - t[u] < d[v] \to t[v] := t[u] + d[v] \;</math>. | |||
Фактически это релаксация алгоритма Беллмана-Форда для вычисления самых длинных путей. | Фактически это релаксация алгоритма Беллмана-Форда для вычисления самых длинных путей. |
правка