Алгоритм Беллмана-Форда

В преддверии старта курса «Алгоритмы для разработчиков» подготовили очередной перевод интересной статьи.

---

Задача: Дан граф и начальная вершина src в графе, необходимо найти кратчайшие пути от src до всех вершин в данном графе. В графе могут присутствовать ребра с отрицательными весами.

Мы уже обсуждали алгоритм Дейкстры в качестве способа решения этой задачи. Алгоритм Дейкстры является жадным алгоритмом, а его сложность равна O(VLogV) (с использованием кучи Фибоначчи). Однако Дейкстра не работает для графов с отрицательными весами ребер, тогда как Беллман-Форд — вполне. Алгоритм Беллмана-Форда даже проще, чем алгоритм Дейкстры, и хорошо подходит для распределенных систем. В то же время сложность его равна O(VE), что больше, чем показатель для алгоритма Дейкстры.

Рекомендация: Прежде, чем двигаться к просмотру решения, попробуйте попрактиковаться самостоятельно.

Алгоритм

Ниже приведены подробно расписанные шаги.

Входные данные: Граф и начальная вершина src.
Выходные данные: Кратчайшее расстояние до всех вершин от src. Если попадается цикл отрицательного веса, то самые короткие расстояния не вычисляются, выводится сообщение о наличии такого цикла.

1. На этом шаге инициализируются расстояния от исходной вершины до всех остальных вершин, как бесконечные, а расстояние до самого src принимается равным 0. Создается массив dist[] размера |V| со всеми значениями равными бесконечности, за исключением элемента dist[src], где src — исходная вершина.
2. Вторым шагом вычисляются самые короткие расстояния. Следующие шаги нужно выполнять |V|-1 раз, где |V| — число вершин в данном графе.
   
   • Произведите следующее действие для каждого ребра u-v:
     Если dist[v] > dist[u] + вес ребра uv, то обновите dist[v]
dist [v] = dist [u] + вес ребра uv
     
3. На этом шаге сообщается, присутствует ли в графе цикл отрицательного веса. Для каждого ребра u-v необходимо выполнить следующее:
   
   • Если dist[v] > dist[u] + вес ребра uv, то в графе присутствует цикл отрицательного веса.
     

Идея шага 3 заключается в том, что шаг 2 гарантирует кратчайшее расстояние, если граф не содержит цикла отрицательного веса. Если мы снова переберем все ребра и получим более короткий путь для любой из вершин, это будет сигналом присутствия цикла отрицательного веса.

Как это работает? Как и в других задачах динамического программирования, алгоритм вычисляет кратчайшие пути снизу вверх. Сначала он вычисляет самые короткие расстояния, то есть пути длиной не более, чем в одно ребро. Затем он вычисляет кратчайшие пути длиной не более двух ребер и так далее. После i-й итерации внешнего цикла вычисляются кратчайшие пути длиной не более i ребер. В любом простом пути может быть максимум |V|-1 ребер, поэтому внешний цикл выполняется именно |V|-1 раз. Идея заключается в том, что если мы вычислили кратчайший путь с не более чем i ребрами, то итерация по всем ребрам гарантирует получение кратчайшего пути с не более чем i + 1 ребрами (доказательство довольно простое, вы можете сослаться на эту лекцию или видеолекцию от MIT)

Пример

Давайте разберемся в алгоритме на следующем примере графа. Изображения взяты отсюда.
Пусть начальная вершина равна 0. Примите все расстояния за бесконечные, кроме расстояния до самой src. Общее число вершин в графе равно 5, поэтому все ребра нужно пройти 4 раза.



Пусть ребра отрабатываются в следующем порядке: (B, E), (D, B), (B, D), (A, B), (A, C), (D, C), (B, C), (E, D). Мы получаем следующие расстояния, когда проход по ребрам был совершен первый раз. Первая строка показывает начальные расстояния, вторая строка показывает расстояния, когда ребра (B, E), (D, B), (B, D) и (A, B) обрабатываются. Третья строка показывает расстояние при обработке (A, C). Четвертая строка показывает, что происходит, когда обрабатываются (D, C), (B, C) и (E, D).



Первая итерация гарантирует, что все самые короткие пути будут не длиннее пути в 1 ребро. Мы получаем следующие расстояния, когда будет совершен второй проход по всем ребрам (в последней строке показаны конечные значения).



Вторая итерация гарантирует, что все кратчайшие пути будут иметь длину не более 2 ребер. Алгоритм проходит по всем ребрам еще 2 раза. Расстояния минимизируются после второй итерации, поэтому третья и четвертая итерации не обновляют значения расстояний.
Реализация:

# Python program for Bellman-Ford's single source 
# shortest path algorithm. 

from collections import defaultdict 

# Class to represent a graph 
class Graph: 

	def __init__(self, vertices): 
		self.V = vertices # No. of vertices 
		self.graph = [] # default dictionary to store graph 

	# function to add an edge to graph 
	def addEdge(self, u, v, w): 
		self.graph.append([u, v, w]) 
		
	# utility function used to print the solution 
	def printArr(self, dist): 
		print("Vertex Distance from Source") 
		for i in range(self.V): 
			print("% d \t\t % d" % (i, dist[i])) 
	
	# The main function that finds shortest distances from src to 
	# all other vertices using Bellman-Ford algorithm. The function 
	# also detects negative weight cycle 
	def BellmanFord(self, src): 

		# Step 1: Initialize distances from src to all other vertices 
		# as INFINITE 
		dist = [float("Inf")] * self.V 
		dist[src] = 0


		# Step 2: Relax all edges |V| - 1 times. A simple shortest 
		# path from src to any other vertex can have at-most |V| - 1 
		# edges 
		for i in range(self.V - 1): 
			# Update dist value and parent index of the adjacent vertices of 
			# the picked vertex. Consider only those vertices which are still in 
			# queue 
			for u, v, w in self.graph: 
				if dist[u] != float("Inf") and dist[u] + w < dist[v]: 
						dist[v] = dist[u] + w 

		# Step 3: check for negative-weight cycles. The above step 
		# guarantees shortest distances if graph doesn't contain 
		# negative weight cycle. If we get a shorter path, then there 
		# is a cycle. 

		for u, v, w in self.graph: 
				if dist[u] != float("Inf") and dist[u] + w < dist[v]: 
						print "Graph contains negative weight cycle"
						return
						
		# print all distance 
		self.printArr(dist) 

g = Graph(5) 
g.addEdge(0, 1, -1) 
g.addEdge(0, 2, 4) 
g.addEdge(1, 2, 3) 
g.addEdge(1, 3, 2) 
g.addEdge(1, 4, 2) 
g.addEdge(3, 2, 5) 
g.addEdge(3, 1, 1) 
g.addEdge(4, 3, -3) 

# Print the solution 
g.BellmanFord(0) 

# This code is contributed by Neelam Yadav 

Выходные значения:



Примечания:

1. Отрицательные веса встречаются в различных применениях графов. Например, вместо того чтобы увеличивать стоимость пути, мы можем получить выгоду, следуя по определенному пути.
2. Алгоритм Беллмана-Форда работает лучше для распределенных систем (лучше, чем алгоритм Дейкстры). В отличие от Дейкстры, где нам нужно найти минимальное значение всех вершин, в Беллмане-Форде ребра рассматриваются по одному.

Упражнения:

1. Стандартный алгоритм Беллмана-Форда сообщает кратчайшие пути только в том случае, если в нем нет циклов отрицательного веса. Измените его таким образом, чтобы он сообщал о кратчайших путях даже при наличии такого цикла.
2. Можем ли мы использовать алгоритм Дейкстры для поиска кратчайших путей в графе с отрицательными весами? Есть такая идея: вычислить минимальное значение веса, прибавить положительное значение (равное модулю значения минимального веса) ко всем весам и запустить алгоритм Дейкстры для модифицированного графа. Сработает ли такой алгоритм?

Простая реализация алгоритма Беллмана-Форда

Источники:

www.youtube.com/watch?v=Ttezuzs39nk
en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
www.cs.arizona.edu/classes/cs445/spring07/ShortestPath2.prn.pdf