Вам дан взвешенный график. Вы знаете источник и вам нужно добраться до всех остальных вершин по кратчайшему пути. Что вы делаете для решения этой проблемы? Вы выбираете алгоритм Дейкстры. Но что, если включены отрицательные веса? Тогда Дейкстра не сможет решить эту проблему. Теперь нам нужен новый алгоритм.

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

МЯГКИЙ ГРАФИК

Мрачный граф - это то, что я называю графом с отрицательными весами. Это на самом деле не так называется, но так называются костюмы, не так ли? Отрицательный вес подобен положительному весу, значению на вершине края. Итак, зачем кому-то граф с отрицательными весами? Потому что они не так бесполезны, как могут показаться. Отрицательные веса могут объяснить множество явлений, например, ваши сбережения, когда положительное преимущество может означать потраченные деньги, а отрицательное преимущество - это то, что вы хотели бы взять, поскольку оно будет представлять накопленные деньги или тепловые реакции, где будет стоять каждый положительный вес. для рассеивания тепла каждый отрицательный вес будет показывать поглощение тепла, и необходимо рассчитать набор реакций, при которых найдена минимальная энергия.

Но как насчет мрачной части? Вот оно. Дайте дорогу отрицательным циклам. Это то, чего следует остерегаться. Цикл - это путь, в котором первая и последняя вершины совпадают, то есть это замкнутый путь. Таким образом, отрицательный цикл становится циклом, который суммируется до отрицательного значения. Алгоритмы кратчайшего пути не могут обнаруживать такие циклы и давать неверные результаты. Это то, что не может победить даже алгоритм Беллмана-Форда. Посмотрите на эту иллюстрацию ниже, чтобы лучше понять.

На этом изображении вершины B, C и D образуют цикл, в котором начальным узлом является B, который также является конечным узлом. Кроме того, этот цикл действует как отрицательный цикл, потому что общее значение суммируется до отрицательного значения -1.

АЛГОРИТМ

Первое, что нужно знать об алгоритме, это то, что он не работает с таким жадным алгоритмом, как Дейкстра. Да, они похожи, но не одинаковы, да! Для реализации этой программы используется подход динамического программирования. Переходим к пониманию этого алгоритма подробнее.

function bellmanFord(G, S)
	for each vertex V in G
			D[V] <- infinite
			
	D[S] <- 0
	for each vertex V in G				
		for each edge (U,V) in G
		  tempDistance <- D[U] + edge_weight(U,V)
			if tempDistance < D[V]
			   D[V] <- tempDistance
			   
	for each edge (U,V) in G
		If D[U] + edge_weight(U, V) < D[V]
			Error: Negative Cycle Exists
                        return
	print D[]

Только не впадайте в панический режим. Обсудим все до мелочей.

Сначала сообщая определение, алгоритм Беллмана-Форда работает, сначала переоценивая длину пути от начальной вершины ко всем остальным вершинам. Затем он итеративно ослабляет эти оценки, находя новые пути, которые короче, чем ранее оцененные пути. Наконец, он проверяет наличие отрицательных циклов

Проще говоря, пусть V - количество вершин, E - количество ребер, S - начальный узел, а D - массив, который отслеживает наилучшее расстояние между исходным узлом и остальными вершинами. Хорошо?

После шага переоценки мы устанавливаем каждую запись в массиве на + бесконечность, как и в случае с Дейкстрой. Это связано с тем, что расстояние до каждого узла изначально неизвестно, поэтому мы присваиваем максимально возможное значение. Теперь мы присваиваем D [S] = 0 по очевидным причинам, так как минимальное расстояние от источника до источника равно, прикинуть? очевидно 0. Итак, мы достигли состояния, показанного ниже.

for each vertex V in G
			D[V] <- infinite
			previous[V] <- NULL
	distance[S] <- 0

Сейчас бесконечные уровни для нас слишком высоки, напряжение накапливается. Пришло время relaaaaax! На этом этапе мы стремимся найти то, что искали, - кратчайший путь к каждой вершине. Мы запускаем цикл, который будет выполняться V раз для каждого ребра, потому что в худшем случае длина пути вершины может нуждаться в корректировке V раз. В цикле для каждого ребра мы берем значение вершины, с которой начинается ребро (D [U]), и добавляем его к стоимости ребра. Эта добавленная стоимость сравнивается со значением вершины, в которой заканчивается ребро (D [V]). Если значение суммы оказывается меньше, значение конечной вершины (D [V]) становится равным сумме.

for each vertex V in G				
		for each edge (U,V) in G
		  tempDistance <- D[U] + edge_weight(U,V)
			if tempDistance < D[V]
			   D[V] <- tempDistance

Взяв пример, мы сделаем несколько шагов, чтобы понять принцип работы.

В этом графе 0 считается исходной вершиной. Начиная цикл, первое ребро, которое мы берем, равно 0 → 1, после чего 1 присваивается значение 5. Затем берутся ребра 1 → 2, 1 → 5 и 1 → 6, в результате чего значение 6 становится ( 5 + 60, т.е. стоимость исходной вершины 1 добавляется к стоимости ребра, 60) = 65, 2 становится (5 + 20) = 25, а 5 становится (5 + 30) = 35. Точно так же значение 3 становится 35.

После определения стоимости 3 мы берем следующие ребра: 3 → 2 и 2 → 4. Это делает значение 2 равным (35-15) = 20, а значение 4 - 100. 20 - это уменьшенное значение по сравнению с предыдущими 25.

Продолжая цикл, край 4 → 9 делает значение 9 равным 200. Теперь еще один момент оптимизации, на который следует обратить внимание. Мы берем край 5 → 6, что дает значение 6 (35+ 5) = 40. Аналогично, переход от 5 к 4 дает суммарное значение от 4 до 60. Эти значения менее или более оптимизированы, чем предыдущие значения.

Вот как работает шаг расслабления

Переходя к третьему и последнему шагу, Обнаружение нашего врага, отрицательные циклы. Теперь, почему наш алгоритм терпит неудачу перед отрицательными циклами? Это потому, что Bellman ford расслабляет все грани. Он находит глобальное оптимальное решение, поэтому при отрицательном цикле алгоритм будет работать бесконечно. Он всегда будет находить более оптимизированное, то есть более отрицательное значение, чем раньше. Поэтому необходимо идентифицировать эти циклы. Но как?

Повторяем ту же петлю снова, взяв края и расслабив их. Поскольку мы уже достигли оптимизированного значения, поэтому, если мы можем снова ослабить край, это означает, что мы столкнулись с отрицательным циклом. Как только это происходит, условие IF становится истинным и выполняется оператор return, завершая функцию, иначе будет напечатан массив D.

for each edge (U,V) in G
		If D[U] + edge_weight(U, V) < D[V]
			Error: Negative Cycle Exists
                        return
print D[]

Мы успешно завершили алгоритм Беллмана-Форда. Ура!

СРАВНЕНИЕ DJIKSTRA И BELLMAN-FORD

Мы уже рассмотрели основные отличия, которые

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

Разница, которую мы пока не затронули, заключается в

  • Джикстра быстр. Временная сложность Bellman ford выше, чем у Djikstra. Но если оптимальное время не является наивысшим приоритетом, то, без сомнения, Bellman Ford - лучший алгоритм кратчайшего пути.

На этом наше путешествие по алгоритму Беллмана-Форда завершено. Я уверен, что Ричард Беллман и Лестер Форд-младший гордились бы вами, просто спите и улыбнитесь в своих могилах. (Да, я тут немного притащил исторический факт!).

Надеюсь, вам понравился этот блог. Оставьте отзыв, я очень этого жду. Наслаждаться!