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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм)
(Алгоритм)
Строка 5: Строка 5:
 
Пусть <tex>d_i</tex> - текущая длина кратчайшего пути до вершины <tex>i</tex>. Изначально, для всех <tex>i \neq s : d_i = \infty</tex>; <tex>d_s = 0</tex>.
 
Пусть <tex>d_i</tex> - текущая длина кратчайшего пути до вершины <tex>i</tex>. Изначально, для всех <tex>i \neq s : d_i = \infty</tex>; <tex>d_s = 0</tex>.
  
Разделим вершины на три '''множества''':
+
Разделим вершины на три множества:
 
* <tex>M_0</tex> - вершины, расстояние до которых уже вычислено(возможно, не окончательно)
 
* <tex>M_0</tex> - вершины, расстояние до которых уже вычислено(возможно, не окончательно)
 
* <tex>M_1</tex> - вершины, расстояние до которых вычисляется
 
* <tex>M_1</tex> - вершины, расстояние до которых вычисляется

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

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

Алгоритм

Пусть [math]d_i[/math] - текущая длина кратчайшего пути до вершины [math]i[/math]. Изначально, для всех [math]i \neq s : d_i = \infty[/math]; [math]d_s = 0[/math].

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

  • [math]M_0[/math] - вершины, расстояние до которых уже вычислено(возможно, не окончательно)
  • [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_0[/math]. Для каждого ребра [math]uv[/math]:

  • если [math]v \in M_2[/math], то переносим [math]v[/math] в [math]M_1[/math] и релаксируем ребро [math]uv[/math]
  • если [math]v \in M_1[/math], то релаксируем ребро [math]uv[/math]
  • если [math]c \in M_0[/math], то переносим [math]v[/math] в [math]M_1[/math] и релаксируем ребро [math]uv[/math]


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

Псевдокод

Сложность

См. также

Источники