Форд-Беллман, Флойд (19 ноября)

1. [Java-Code]
2. Форд-Беллман. Тестируем на случайном графе.
1. Стандартная реализация за Θ(VE), V = 10⁵, E = 2 × 10⁵ [code]
2. Реализация с break − 22 итерации [code]
3. Реализация с очередью − 1.31 итерация [code]
3. Задачи
1. Пусть вес пути − максимальное ребро на пути. Насчитать матрицу расстояний.
2. Нужно научиться на запрос "уменьшился вес ребра" за O(n²) пересчитывать матрицу расстояний.
3. Есть n валют и m обменников. i-й обменник предлагает менять валюту a_i на валюту b_i по курсу c_i/d_i. Можно ли, используя сколь угодно большие начальные сбережения и данные m обменников, сломать финансовую систему и бесконечно обогащаться? Считается, что у обменников есть бесконечное количество денег целевой валюты. O(nm).
4. Есть ограф. Нужно найти количество необязательно простых путей из a в b
1. Длины ровно k, здесь k ≤ 10⁹.
2. Длины не более k, здесь k ≤ 10⁹.
3. Длины от l до r, здесь l ≤ r ≤ 10⁹.
5. Цикл минимального среднего веса за O(VElogM)