Изменения
Нет описания правки
# Приведите пример графа, в котором алгоритм из предыдущего задания рабоатает экспоненциальное время.
# Предложите граф, в котором алгоритм Дейкстры делает $\Omega(E)$ успешных релаксаций
# Доказать теорему об отсутствии кратчайшего пути на базе алгоритма Форда-Беллмана. (от $s$ до $v$ нет кратчайшего пути тогда и только тогда, когда она достижима из $u$, такой что после выполнения алгоритма Форда-Беллмана найдется ребро $xu$, для которого $d[x] + w(xu) < d[u]$)
# Разработать алгоритм на базе Форда-Беллмана, который ищет в графе отрицательный цикл.
# Укажите способ построить для некоторых $c_1, c_2 >0$ и любых V, E, где $c_1 V \le E \le c_2 V^2$ граф, на котором алгоритм Форда-Беллмана с очередью работает за $\Omega(VE)$.
# Пусть в графе $G$ есть вершина $s$, из которой достижимы все вершины. Обозначим как $\mu^*$ минимальный средний вес цикла в графе. Докажите, что $\mu^* = \min_v\max_k\frac{d_n(v)-d_k(v)}{n-k}$, где $d_i(v)$ - длина кратчайшего пути из $s$ до $v$, содержащего ровно $i$ ребер.
# Модифицируйте алгоритм Форда-Беллмана так, чтобы он находил в графе циклы минимального среднего веса за $O(VE)$ и $O(V^2)$ памяти.
# Модифицируйте алгоритм Флойда, чтобы найти в графе отрицательный цикл.
# Петя перепутал и написал в алгоритме Флойда "for i: for j: for k: relax(d[i][j], d[i][k]+d[k][j])". Постройте тест, на котором получившийся алгоритм работает неверно.
# Петя перепутал и написал в алгоритме Флойда "for i: for j: for k: relax(d[i][j], d[i][k]+d[k][j])". Заметив, что это работает неверно, он запустил этот алгоритм два раза. Будет ли получившийся алгоритм "for t from 1 to 2: for i: for j: for k: relax(d[i][j], d[i][k]+d[k][j])" корректным?
