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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм)
(Псевдокод)
Строка 25: Строка 25:
  
 
== Псевдокод ==
 
== Псевдокод ==
 +
 +
'''for''' u <tex>\in</tex> V ''':'''
 +
    <tex>d_v \gets</tex> <tex>\infty</tex>
 +
<tex>d_s \gets 0</tex>
 +
 +
<tex>M_1^{''}</tex>.add(s)
 +
'''for''' u <tex>\neq</tex> s <tex>\in</tex> V ''':'''
 +
    <tex>M_2</tex>.add(u)
 +
 +
'''while''' <tex>M_1 \neq \varnothing</tex> ''':'''
 +
    '''if''' <tex>M_1^{''} \neq \varnothing</tex> ''':'''
 +
      u <tex>\gets</tex> <tex>M_1^{''}</tex>.pop()
 +
    '''else :'''
 +
      u <tex>\gets</tex> <tex>M_1{'}</tex>.pop()
 +
 +
    '''for''' uv <tex>\in</tex> E ''':'''
 +
      '''if''' v <tex>\in M_2</tex> ''':'''
 +
          <tex>M_1^{'}</tex>.push(v)
 +
          relax(uv)
 +
      '''if''' v <tex>\in M_1</tex> ''':'''
 +
          relax(uv)
 +
      '''if''' v <tex>\in M_0</tex> '''and''' <tex>d_v > d_u + w_{uv}</tex> ''':'''
 +
          relax(uv)
 +
          <tex>M_1^{''}</tex>.push(v)
 +
 +
    <tex>M_0</tex>.add(u)
  
 
== Сложность ==
 
== Сложность ==

Версия 14:14, 19 октября 2013

Алгоритм Левита находит расстояние от заданной вершины [math]s[/math] до всех остальных. Данный алгоритм является модификацией алгоритмы Дейкстры, которая позволяет работать с ребрами отрицательного веса.

Алгоритм

Пусть [math]d_i[/math] — текущая длина кратчайшего пути до вершины [math]i[/math]. Изначально, для всех [math]i \neq s : d_i \gets \infty[/math]; [math]d_s \gets 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]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] :
   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)
         relax(uv)
      if v [math]\in M_1[/math] :
         relax(uv)
      if v [math]\in M_0[/math] and [math]d_v \gt  d_u + w_{uv}[/math] :
         relax(uv)
         [math]M_1^{''}[/math].push(v)

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

Сложность

См. также

Источники