Семинар 7.
1. Алгоритм Дейкстры: ищем минимальный путь из данной вершины до всех остальных
вершин во взвешенном графе с рёбрами неотрицательной длины. В каждой вершине v
храним число d[v] — претендента на длину кратчайшего пути до неё из начальной
вершины. На каждом шаге выбираем необработанную вершину с минимальным d[v],
идём по каждому ребру, ведущему в необработанную вершину u, и пробуем улучшить
число d[u]. После этого, помечаем вершину v как обработанную.
2. В ходе выполнения алгоритма мы поддерживаем такой инвариант: в любой момент
времени в каждой обработанной вершине записано число равное длине кратчайшего
пути до неё из начальной вершины. Доказательство корректности проводится по
индукции. Пусть наш инвариант выполнился для всех обработанных вершин, теперь,
согласно алгоритму, мы выбираем вершину с наименьшим числом d[v], записанным
в ней. Предположим, d[v] больше длины кратчайшего пути из исходной вершины в v
(очевидно, меньше оно быть не может). Рассмотрим этот путь. Найдём в нём первую
необработанную вершину w и предшествующую ей (а значит обработанную) вершину u.
Обозначим за D(v) длину кратчайшего пути до вершины v, а за l(u,v) длину ребра
от u до v. Тогда верно неравенство: d[w] ⩽ d[u] + l(u,w) ⩽ D(v) < d[v]. Откуда
получаем, что мы не должны были выбрать вершину v на текущем шаге, так как есть
необработанная вершина w с меньшим d[w].
3. Алгоритм состоит из выбора вершин с наименьшим d[v] и прохождения по всем
рёбрам. Соответственно, время его работы оценивается количеством рёбер и
временем, затрачиваемым на выбор вершин. Последнее зависит от того, как мы
храним и выбираем вершины. Если это просто список, то время оценивается как
O(E + V^2). Если граф достаточно разрежен, то имеет смысл складывать вершины
в древовидную структуру, например, бинарную кучу. Тогда поиск и вынимание
вершины будет занимать log(V) времени, но зато увеличится время необходимое
на изменение d[v], и, соответственно, обработку одного ребра. Общее время
работы алгоритма тогда оценится через O((E + V) log(V)).
4. Заметим, что в доказательстве мы использовали то что длина пути есть сумма
длин рёбер только в последнем неравенстве. Теперь мы хотим, чтобы длина пути
задавалась произвольной функцией L(P), и мы хотим выяснить, какие условия
нужно наложить на эту функцию, чтобы алгоритм всё ещё правильно работал.
Мы потребуем от L(P) монотонности по пути: если путь P1 является подпутём P2
(P1 ⊂ P2), то L(P1) ⩽ L(P2). Кроме того, мы потребуем такое свойство: если
есть два пути P1 и P2 из вершины u в вершину v, и L(P1) ⩽ L(P2), то для
любого ребра (v,w), также верно: L(P1 + (v,w)) ⩽ L(P2 + (v,w)).
5. Второе свойство функции расстояния гарантирует нам, что минимальный путь до
любой вершины w будет состоять из минимального пути до какой-то вершины v,
соседней с w, и ребра (v,w). Таким образом мы как и раньше можем строить
минимальные пути постепенно — ребро за ребром. При этом, в каждой вершине
вместе с длиной мы храним путь до этой вершины, который имеет такую длину.
И когда пересчитываем значения в соседних с v вершинах, мы рассматриваем
только пути, образованные из пути, хранящемся в v, прибавлением к нему ребра
исходящего из v. Как мы уже заметили, второе свойство функции L гарантирует,
что достаточно рассматривать только такие пути. Теперь мы можем повторить все
рассуждения из доказательства обычного алгоритма Дейкстры. Нашли кратчайший
путь P до вершины v, нашли вершины u и w. Получаем: d[w] ⩽ L(Pu + (u,v)) =
= P(Pv) ⩽ L(P) = D(v) < d[v], где Pv — отрезок пути P от начальной вершины
до вершины v. Здесь мы в одном месте воспользовались монотонностью, а
остальные равенства и неравенства следуют непосредственно из работы алгоритма
и предположения "от противного". Мы опять пришли к противоречию.
6. Примеры функции расстояния: минимум максимального ребра и максимум
минимального ребра на пути.
7. Алгоритм Форда-Беллмана: опять ищем минимальный путь из данной вершины до
всех остальных, только теперь допускаются рёбра отрицательной длины. Для
этого применим метод динамического программирования: обозначим за A_{v,n}
длину кратчайшего пути из стартовой вершины s, до вершины v, содержащего
не более n рёбер. Тогда, имея числа A_{v,n}, можно легко посчитать и числа
A_{v,n+1}. Алгоритм останавливается, когда ни для какой вершины укоротить
путь не получится.
8. Если в графе нет циклов отрицательной длины, достижимых из вершины s, то
алгоритм остановится не более, чем через V-1 шагов. Действительно, в пути
большей длины какая-то вершина обязательно повторится, то есть этот путь
будет содержать цикл, который можно безболезненно выкинуть. Если же такой
цикл есть, то длину какого-то пути можно уменьшать бесконечно, и алгоритм
никогда не остановится. Таким образом, время работы алгоритма Форда-
Беллмана: O(VE). Ещё отсюда вытекает критерий существования в графе цикла
отрицательной длины: если A_{v,n-1} ≠ A_{v,n}, то такой цикл существует и
достижим из стартовой вершины.
9. Заметим, что мы нашли только длину кратчайшего пути. Если же нам нужен и сам
путь, то в A_{v,n} следует записывать длину кратчайшего пути до v, состоящего
ровно из n рёбер. Кроме того, нужно для каждого числа A_{v,n}, хранить ещё и
вершину P_{v,n}, из которой мы пришли в v. Как и раньше, остановиться нужно
либо через V-1 шагов, либо, когда не увидим улучшений ни для какой вершины
(сравнивать нужно со всеми числами A_{v,n}).
<<