276
правок
Изменения
→способ убрать \texttt{log} \frac{1}{\varepsilon} из оценки
Такой алгоритм будет работать за <tex>O(\texttt{log} \frac{1}{\varepsilon} \cdot EV)</tex>, где <tex>\varepsilon</tex> {{---}} точность выбора величины среднего веса цикла.
===способ убрать <tex>\texttt{log} \frac{1}{\varepsilon}</tex> из оценкиПродвинутый алгоритм===
Добавим к нашему графу вершину <tex>s</tex> и ребра из нее во все остальные вершины.
Рассмотрим [[алгоритм Форда-Беллмана ]] и попросим его построить нам следущую квадратную матрицу:
<code>
d[i][u] // длина минимального пути от s до u ровно из i ребер
