Что делает: находит кратчайшие расстояния от одной вершины до всех остальных в взвешенном ориентированном графе

Чего Точная оценка Почему
Время O(VE) O([V-1]*E + E) == O(VE): V-1 раз проходимся по всем рёбрам релаксируя (релаксация за O(1)) ⇒ O([V-1]*E) + O(E) - проверка на отрицательные циклы
Память O(V) похуй

Общая идея:

Для каждой вершины прорелаксировать рёбра со всеми остальными вершинами. Из-за леммы о том, что часть кратчайшего расстояния == кратчайшее расстояние, все классно работает (на каждой итерации 100% правильно релаксируем одно ребро)

Также алгоритм может определить циклы отрицательного веса: после всех релаксаций, прорелаксировать каждое ребро ещё один раз, и если хоть одно изменится ⇒ существует цикл отрицательного веса

Реализация:

int main() {
	for u из G(V) do {
		u.distance = INF
		u.parent = NULL
	}
	s.distance = 0 // инициализируем стартовую вершину
	
	for i = 1 to (|V|-1) do
		for edge(u,v) из edges do
			Relax(edge(u,v)) // передаем u -> v and weight
	
	for edge(u,v) из edges do
		if v.distance > u.distance + weight(u,v)
			return "Цикл отрицательного веса!"
}

void Relax(edge) {
	v.distance = min(v.distance, u.distance + edge.weight)
	if v.distance changes:
		v.parent = u
}

‼ Особенности алгоритма Беллмана-Форда:

  1. может вычислить цикл отрицательного веса и прекратить работу если найдет такой
  2. если в основном цикле релаксаций хотя бы один раз подряд расстояния не изменятся, можно выйти из цикла, т.к. уже найдены кратчайшие расстояния

Визуализация: этим я займусь чуть попозже