Алгоритм Левита — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство)
(Доказательство)
Строка 58: Строка 58:
 
{{Лемма
 
{{Лемма
 
|statement= Алгоритм отработает за конечное время
 
|statement= Алгоритм отработает за конечное время
|proof= Не теряя общности, будем считать, что граф связен. Тогда в конце работы алгоритма все вершины должны оказаться в <tex>M_0.</tex> На каждом шаге мы гарантированно либо уменьшаем расстояние до какой-то вершины (возможно, она перейдет из <tex>M_0</tex> в <tex>M_1^{''}</tex>), либо перемещаем текущую вершину в <tex>M_0</tex>. Так как в графе нет отрицательных циклов, то уменьшить расстояние можно только конечное число раз. Количество вершин тоже конечно. Следовательно, будет произведено конечное число шагов.
+
|proof= Не теряя общности, будем считать, что граф связен. Тогда алгоритм завершит работу, когда в <tex>M_0</tex> окажутся все вершины. Так как в исходном графе нет отрицательных циклов, то для каждой вершины существует кратчайший путь. Тогда расстояние до каждой вершины может уменьшится только конечное число раз и, как следствие, вершина будет переведена из <tex>M_0</tex> в <tex>M_1</tex> тоже конечное число раз. С другой стороны, на каждом шаге текущая вершина гарантированно помещается в <tex>M_0</tex>. Тогда за конечное число шагов все вершины окажутся в <tex>M_0</tex>.
 
}}
 
}}
  
Строка 66: Строка 66:
 
|proof= Предположим обратное. Тогда рассмотрим 2 случая:
 
|proof= Предположим обратное. Тогда рассмотрим 2 случая:
 
# Вершина <tex>u</tex> попала в <tex>M_0</tex> позже <tex>v</tex>. Тогда должна была произойти релаксация ребра <tex>uv</tex> и она была неуспешной. Значит, такого варианта не может быть
 
# Вершина <tex>u</tex> попала в <tex>M_0</tex> позже <tex>v</tex>. Тогда должна была произойти релаксация ребра <tex>uv</tex> и она была неуспешной. Значит, такого варианта не может быть
# Вершина <tex>u</tex> попала в <tex>_0</tex> раньше <tex>v</tex>. Заметим, что с момента последнего попадания <tex>u</tex> в <tex>M_0</tex> расстояние до нее не менялось. Вес ребра <tex>uv</tex> тоже не меняется. Значит, и релаксация ребра <tex>uv</tex> ничего не даст
+
# Вершина <tex>u</tex> попала в <tex>M_0</tex> раньше <tex>v</tex>. Заметим, что с момента последнего попадания <tex>u</tex> в <tex>M_0</tex> расстояние до нее не менялось (иначе, вершина была бы извлечена из <tex>M_0</tex>). Вес ребра <tex>uv</tex> тоже не меняется. Значит, и релаксация ребра <tex>uv</tex> ничего не даст
 
Противоречие.
 
Противоречие.
 
}}
 
}}

Версия 00:00, 10 января 2014

Алгоритм Левита (Levit algorithm) находит расстояние от заданной вершины [math]s[/math] до всех остальных. Позволяет работать с ребрами отрицательного веса при отсутствии отрицательных циклов.

Алгоритм

Пусть [math]d_i[/math] — текущая длина кратчайшего пути до вершины [math]i[/math]. Изначально, все элементы [math]d[/math], кроме [math]s[/math]-го равны бесконечности; [math]d[s] = 0[/math].

Разделим вершины на три множества:

  • [math]M_0[/math] — вершины, расстояние до которых уже вычислено (возможно, не окончательно)
  • [math]M_1[/math] — вершины, расстояние до которых вычисляется. Это множество в свою очередь делится на две очереди:
  1. [math]M_1^{'}[/math] — основная очередь
  2. [math]M_1^{''}[/math] — срочная очередь
  • [math]M_2[/math] — вершины, расстояние до которых еще не вычислено

Изначально все вершины, кроме [math]s[/math] помещаются в множество [math]M_2[/math]. Вершина [math]s[/math] помещается в множество [math]M_1[/math] (в любую из очередей).


Шаг алгоритма: выбирается вершина [math]u[/math] из [math]M_1[/math]. Если очередь [math]M_1^{''}[/math] не пуста, то вершина берется из нее, иначе из [math]M_1^{'}[/math]. Далее, для каждого ребра [math]uv \in E[/math]:

  • если [math]v \in M_2[/math], то [math]v[/math] переводится в конец очереди [math]M_1^{'}[/math]. При этом [math]d_v \gets d_u + w_{uv}[/math] (производится релаксация ребра [math]uv[/math])
  • если [math]v \in M_1[/math], то происходит релаксация ребра [math]uv[/math]
  • если [math]v \in M_0[/math] и [math]d_v \gt d_u + w_{uv}[/math], то происходит релаксация ребра [math]uv[/math] и [math]v[/math] помещается в [math]M_1^{''}[/math]

В конце шага помещаем вершину [math]u[/math] в множество [math]M_0[/math].


Алгоритм заканчивает работу, когда множество [math]M_1[/math] становится пустым.

Псевдокод

for u [math]\in[/math] V :
   [math]d_v \gets[/math] [math]\infty[/math]
[math]d_s \gets 0[/math]

[math]M_1^{''}[/math].add(s)
for u [math]\neq[/math] s [math]\in[/math] V :
   [math]M_2[/math].add(u)

while [math]M_1^{'} \neq \varnothing[/math] and [math]M_1^{''} \neq \varnothing[/math] :
   if [math]M_1^{''} \neq \varnothing[/math] :
      u [math]\gets[/math] [math]M_1^{''}[/math].pop()
   else :
      u [math]\gets[/math] [math]M_1{'}[/math].pop()

   for uv [math]\in[/math] E :
      if v [math]\in M_2[/math] :
         [math]M_1^{'}[/math].push(v)
         [math]M_2[/math].remove(v)
         relax(uv, d)
      if v [math]\in M_1[/math] :
         relax(uv, d)
      if v [math]\in M_0[/math] and [math]d_v \gt  d_u + w_{uv}[/math] :
         [math]M_1^{''}[/math].push(v)
         [math]M_0[/math].remove(v)
         relax(uv, d)

   [math]M_0[/math].add(u)

Доказательство

Лемма:
Алгоритм отработает за конечное время
Доказательство:
[math]\triangleright[/math]
Не теряя общности, будем считать, что граф связен. Тогда алгоритм завершит работу, когда в [math]M_0[/math] окажутся все вершины. Так как в исходном графе нет отрицательных циклов, то для каждой вершины существует кратчайший путь. Тогда расстояние до каждой вершины может уменьшится только конечное число раз и, как следствие, вершина будет переведена из [math]M_0[/math] в [math]M_1[/math] тоже конечное число раз. С другой стороны, на каждом шаге текущая вершина гарантированно помещается в [math]M_0[/math]. Тогда за конечное число шагов все вершины окажутся в [math]M_0[/math].
[math]\triangleleft[/math]


Лемма:
В конце работы алгоритма не найдется такое ребро [math]uv[/math], что его релаксация будет успешной
Доказательство:
[math]\triangleright[/math]

Предположим обратное. Тогда рассмотрим 2 случая:

  1. Вершина [math]u[/math] попала в [math]M_0[/math] позже [math]v[/math]. Тогда должна была произойти релаксация ребра [math]uv[/math] и она была неуспешной. Значит, такого варианта не может быть
  2. Вершина [math]u[/math] попала в [math]M_0[/math] раньше [math]v[/math]. Заметим, что с момента последнего попадания [math]u[/math] в [math]M_0[/math] расстояние до нее не менялось (иначе, вершина была бы извлечена из [math]M_0[/math]). Вес ребра [math]uv[/math] тоже не меняется. Значит, и релаксация ребра [math]uv[/math] ничего не даст
Противоречие.
[math]\triangleleft[/math]


Из двух предыдущих лемм напрямую следует корректность алгоритма.

Сложность

В худшем случае алгоритм Левита работает за экспоненциальное время. Однако, на реальных графах алгоритм Левита работает быстрее, чем алгоритм Форда Беллмана и не многим хуже алгоритма Дейкстры.

Источники