Алгоритм беллмана форда и дейкстры отличия

Обновлено: 04.05.2024

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

Алгоритм
Ниже приведены подробные шаги.

1) Этот шаг инициализирует расстояния от источника до всех вершин как бесконечные и расстояние до самого источника как 0. Создайте массив dist [] размера | V | со всеми значениями как бесконечными, кроме dist [src], где src — исходная вершина.

2) Этот шаг рассчитывает кратчайшие расстояния. Выполните | V | -1 раз, где | V | количество вершин в данном графе.
… .. а) Делайте следующее для каждого края уф
……………… Если dist [v]> dist [u] + вес края uv, то обновите dist [v]
………………… .dist [v] = dist [u] + вес края уф

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

пример
Давайте разберем алгоритм на следующем примере графа. Изображения взяты из этого источника.

Пусть заданная вершина источника равна 0. Инициализируйте все расстояния как бесконечные, кроме расстояния до самого источника. Общее количество вершин в графе 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 раза. Расстояния минимизируются после второй итерации, поэтому третья и четвертая итерации не обновляют расстояния.

Реализация:

// структура для представления взвешенного ребра в графе

int src, dest, weight;

// структура для представления связанных, направленных и
// взвешенный график

// V-> Количество вершин, E-> Количество ребер

// график представлен в виде массива ребер.

struct Edge* edge;

// Создаем граф с V вершинами и E ребрами

struct Graph* createGraph( int V, int E)

struct Graph* graph = new Graph;

graph->edge = new Edge[E];

// Утилита, используемая для печати решения

void printArr( int dist[], int n)

printf ( "Vertex Distance from Source\n" );

for ( int i = 0; i

printf ( "%d \t\t %d\n" , i, dist[i]);

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

void BellmanFord( struct Graph* graph, int src)

// Шаг 1: Инициализировать расстояния от src до всех остальных вершин

for ( int i = 0; i

// Шаг 2: ослабить все ребра | V | - 1 раз. Простой кратчайший

// путь от src до любой другой вершины может иметь самое большее | V | - 1

for ( int i = 1; i

for ( int j = 0; j

int u = graph->edge[j].src;

int v = graph->edge[j].dest;

int weight = graph->edge[j].weight;

if (dist[u] != INT_MAX && dist[u] + weight

dist[v] = dist[u] + weight;

// Шаг 3: проверка циклов с отрицательным весом. Вышеуказанный шаг

// гарантирует кратчайшие расстояния, если граф не содержит

// отрицательный весовой цикл. Если мы получим более короткий путь, то там

for ( int i = 0; i

int u = graph->edge[i].src;

int v = graph->edge[i].dest;

int weight = graph->edge[i].weight;

if (dist[u] != INT_MAX && dist[u] + weight

printf ( "Graph contains negative weight cycle" );

return ; // Если обнаружен отрицательный цикл, просто вернемся

// Программа драйвера для проверки вышеуказанных функций

/ * Давайте создадим график, приведенный в примере выше * /

int V = 5; // Количество вершин в графе

int E = 8; // Количество ребер в графе

struct Graph* graph = createGraph(V, E);

// добавляем ребро 0-1 (или AB на рисунке выше)

// добавляем ребро 0-2 (или AC на рисунке выше)

// добавить ребро 1-2 (или BC на рисунке выше)

// добавляем ребро 1-3 (или BD на рисунке выше)

// добавить ребро 1-4 (или AE на рисунке выше)

// добавляем ребро 3-2 (или DC на рисунке выше)

// добавляем ребро 3-1 (или DB на рисунке выше)

// добавить ребро 4-3 (или ED на рисунке выше)

// Java-программа для кратчайшего пути Беллмана-Форда
// алгоритм.

// Класс для представления связного, ориентированного и взвешенного графа

// Класс для представления взвешенного ребра в графе

int src, dest, weight;

src = dest = weight = 0 ;

// Создаем граф с V вершинами и E ребрами

Graph( int v, int e)

edge = new Edge[e];

for ( int i = 0 ; i

edge[i] = new Edge();

// Основная функция, которая находит кратчайшие расстояния от src

// ко всем остальным вершинам, используя алгоритм Беллмана-Форда.

// функция также обнаруживает отрицательный весовой цикл

void BellmanFord(Graph graph, int src)

int V = graph.V, E = graph.E;

int dist[] = new int [V];

// Шаг 1: Инициализировать расстояния от src до всех остальных

// вершины как БЕСКОНЕЧНЫЕ

for ( int i = 0 ; i

// Шаг 2: ослабить все ребра | V | - 1 раз. Простой

// кратчайший путь от src до любой другой вершины

// иметь самое большее | V | - 1 ребро

for ( int i = 1 ; i

for ( int j = 0 ; j

int u = graph.edge[j].src;

int v = graph.edge[j].dest;

int weight = graph.edge[j].weight;

if (dist[u] != Integer.MAX_VALUE && dist[u] + weight

dist[v] = dist[u] + weight;

// Шаг 3: проверка циклов с отрицательным весом. Над

// шаг гарантирует кратчайшие расстояния, если граф не

// содержат отрицательный весовой цикл. Если мы получим короче

// путь, то есть цикл.

for ( int j = 0 ; j

int u = graph.edge[j].src;

int v = graph.edge[j].dest;

int weight = graph.edge[j].weight;

if (dist[u] != Integer.MAX_VALUE && dist[u] + weight

System.out.println( "Graph contains negative weight cycle" );

// Утилита, используемая для печати решения

void printArr( int dist[], int V)

System.out.println( "Vertex Distance from Source" );

for ( int i = 0 ; i

System.out.println(i + "\t\t" + dist[i]);

// Метод драйвера для проверки вышеуказанной функции

public static void main(String[] args)

int V = 5 ; // Количество вершин в графе

int E = 8 ; // Количество ребер в графе

Graph graph = new Graph(V, E);

// добавляем ребро 0-1 (или AB на рисунке выше)

graph.edge[ 0 ].src = 0 ;

graph.edge[ 0 ].dest = 1 ;

graph.edge[ 0 ].weight = - 1 ;

// добавляем ребро 0-2 (или AC на рисунке выше)

graph.edge[ 1 ].src = 0 ;

graph.edge[ 1 ].dest = 2 ;

graph.edge[ 1 ].weight = 4 ;

// добавить ребро 1-2 (или BC на рисунке выше)

graph.edge[ 2 ].src = 1 ;

graph.edge[ 2 ].dest = 2 ;

graph.edge[ 2 ].weight = 3 ;

// добавляем ребро 1-3 (или BD на рисунке выше)

graph.edge[ 3 ].src = 1 ;

graph.edge[ 3 ].dest = 3 ;

graph.edge[ 3 ].weight = 2 ;

// добавить ребро 1-4 (или AE на рисунке выше)

graph.edge[ 4 ].src = 1 ;

graph.edge[ 4 ].dest = 4 ;

graph.edge[ 4 ].weight = 2 ;

// добавляем ребро 3-2 (или DC на рисунке выше)

graph.edge[ 5 ].src = 3 ;

graph.edge[ 5 ].dest = 2 ;

graph.edge[ 5 ].weight = 5 ;

// добавляем ребро 3-1 (или DB на рисунке выше)

graph.edge[ 6 ].src = 3 ;

graph.edge[ 6 ].dest = 1 ;

graph.edge[ 6 ].weight = 1 ;

// добавить ребро 4-3 (или ED на рисунке выше)

graph.edge[ 7 ].src = 4 ;

graph.edge[ 7 ].dest = 3 ;

graph.edge[ 7 ].weight = - 3 ;

from collections import defaultdict

def __init__( self , vertices):

def addEdge( self , u, v, w):

self .graph.append([u, v, w])

def printArr( self , dist):

print ( "Vertex Distance from Source" )

for i in range ( self .V):

print ( "% d \t\t % d" % (i, dist[i]))

def BellmanFord( self , src):

dist = [ float ( "Inf" )] * self .V

for i in range ( self .V - 1 ):

for u, v, w in self .graph:

if dist[u] ! = float ( "Inf" ) and dist[u] + w

dist[v] = dist[u] + w

for u, v, w in self .graph:

if dist[u] ! = float ( "Inf" ) and dist[u] + w

print "Graph contains negative weight cycle"

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 )

// Класс для представления связного, ориентированного и взвешенного графа

// Класс для представления взвешенного ребра в графе

public int src, dest, weight;

src = dest = weight = 0;

// Создаем граф с V вершинами и E ребрами

Graph( int v, int e)

edge = new Edge[e];

for ( int i = 0; i

edge[i] = new Edge();

// Основная функция, которая находит кратчайшие расстояния от src

// ко всем остальным вершинам, используя алгоритм Беллмана-Форда.

// функция также обнаруживает отрицательный весовой цикл

void BellmanFord(Graph graph, int src)

int V = graph.V, E = graph.E;

int [] dist = new int [V];

// Шаг 1: Инициализировать расстояния от src до всех остальных

// вершины как БЕСКОНЕЧНЫЕ

for ( int i = 0; i

dist[i] = int .MaxValue;

// Шаг 2: ослабить все ребра | V | - 1 раз. Простой

// кратчайший путь от src до любой другой вершины

// иметь самое большее | V | - 1 ребро

for ( int i = 1; i

for ( int j = 0; j

int u = graph.edge[j].src;

int v = graph.edge[j].dest;

int weight = graph.edge[j].weight;

if (dist[u] != int .MaxValue && dist[u] + weight

dist[v] = dist[u] + weight;

// Шаг 3: проверка циклов с отрицательным весом. Над

// шаг гарантирует кратчайшие расстояния, если граф не

// содержат отрицательный весовой цикл. Если мы получим короче

// путь, то есть цикл.

for ( int j = 0; j

int u = graph.edge[j].src;

int v = graph.edge[j].dest;

int weight = graph.edge[j].weight;

if (dist[u] != int .MaxValue && dist[u] + weight

Console.WriteLine( "Graph contains negative weight cycle" );

// Утилита, используемая для печати решения

void printArr( int [] dist, int V)

Console.WriteLine( "Vertex Distance from Source" );

for ( int i = 0; i

Console.WriteLine(i + "\t\t" + dist[i]);

// Метод драйвера для проверки вышеуказанной функции

public static void Main()

int V = 5; // Количество вершин в графе

int E = 8; // Количество ребер в графе

Graph graph = new Graph(V, E);

// добавляем ребро 0-1 (или AB на рисунке выше)

// добавляем ребро 0-2 (или AC на рисунке выше)

// добавить ребро 1-2 (или BC на рисунке выше)

// добавляем ребро 1-3 (или BD на рисунке выше)

// добавить ребро 1-4 (или AE на рисунке выше)

// добавляем ребро 3-2 (или DC на рисунке выше)

// добавляем ребро 3-1 (или DB на рисунке выше)

// добавить ребро 4-3 (или ED на рисунке выше)

// Этот код предоставлен Ryuga

Примечания
1) Отрицательные веса встречаются в различных приложениях графов. Например, вместо того, чтобы платить за путь, мы можем получить некоторое преимущество, если будем следовать по пути.

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

Упражнение
1) Стандартный алгоритм Беллмана-Форда сообщает о кратчайшем пути, только если нет отрицательных циклов веса. Измените его так, чтобы он отображал минимальные расстояния, даже если есть отрицательный весовой цикл.

2) Можем ли мы использовать алгоритм Дейксры для кратчайших путей для графов с отрицательными весами — одна идея может состоять в том, чтобы вычислить минимальное значение веса, добавить положительное значение (равное абсолютному значению минимального значения веса) ко всем весам и запустить алгоритм Дейксры для модифицированный граф. Будет ли этот алгоритм работать?

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Поиск в орграфе кратчайших путей от одной вершины до всех остальных при неотрицательных ребрах.

Инициализация. Метка вершины aполагается = 0, метки остальных — бесконечности (т.е. расстояния отaпока неизвестны, и они помечаются как непосещённые)

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

Алгоритм Беллмана–Форда — алгоритм поиска кратчайшего пути во взвешенном графе. За время O(|V| × |E|) алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана–Форда допускает рёбра с отрицательным весом.

Алгоритм носит имя двух американских учёных: Ричарда Беллмана (Richard Bellman) и Лестера Форда (Lester Ford). Форд фактически изобрёл этот алгоритм в 1956 г. при изучении другой математической задачи, подзадача которой свелась к поиску кратчайшего пути в графе, и Форд дал набросок решающего эту задачу алгоритма. Беллман в 1958 г. опубликовал статью, посвящённую конкретно задаче нахождения кратчайшего пути, и в этой статье он чётко сформулировал алгоритм в том виде, в котором он известен нам сейчас.

Алгоритм маршрутизации RIP (алгоритм Беллмана–Форда) был впервые разработан в 1969 году, как основной для сети ARPANET.

Дан ор. или неор. граф G со взвешенными рёбрами. Длина пути - сумма весов рёбер, входящих в этот путь. Найти кратчайшие пути от выделенной вершины sдо всех вершин графа (их м. не существовать, т.к., в графе, содерж. цикл с отрицат. суммарным весом, существует сколь угодно короткий путь от одной вершины этого цикла до другой) Цикл, сумма весов рёбер которого отрицательна, называется отрицательным циклом.

А. Б.–Ф. позволяет оч. просто определить, существует ли в графе G отрицательный цикл, достижимый из вершины s. Достаточно произвести внешнюю итерацию цикла не | V | − 1, a ровно |V| раз. Если при исполнении последней итерации длина кратчайшего пути до к.-л. В-ы строго уменьшилась, то в графе есть отрицат. цикл, достижимый изs. На основе этого м. предложить след. Оптимизацию: отслеживать изменения в графе и, как только они закончатся, дальнейшие итерации будут бессмысленны. Значит м. сделать выход из цикла.

Решение задачи на графе без отрицательных циклов

Для нахождения кратчайших путей от одной вершины до всех остальных, восп-ся методом динамического программирования. На входе - матрица Aij, содержащая длина дуг (ребер) между смежными вершинами. На выходе – вектор с кратчайшими расстояниями от выбранной вершины до всех остальных и указание об отсутствии отрицательных циклов.

1 2 3 4 5 0 6 ∞ 7 ∞

1 ∞ 6 ∞ 7 ∞ от 1 1 0 6 4 7 2

2 ∞ ∞ 1 8 -4 от след. 2 (от 2-й и 4-й) 0 2 4 7 -2

3 ∞ -2 ∞ ∞ ∞ 3 0 2 4 7 -2

Ребра перебираются по порядку

1) (2 - 3) (2 - 4) (2 - 5) (4 - 3) (4 - 5)

2) (3 - 2) (2 - 4) (2 – 5) (4 - 3) (4 - 5)

3) (5 - 3) (5 - 1) (1 - 2) (1 - 4)

Похоже на поиск в ширину от всех смежных вершин

Procedure Bellman_Ford (G,w,S) - алгоритм Беллмана –Форда O(VE)

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

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

Начнём с того, что все исходящие ребра записываются в таблице в алфавитном порядке.

Как и в алгоритме Дейкстры, создаётся таблица, в которой записывается расстояние до каждой вершины и предыдущая вершина. Расстояния для всех вершин, кроме исходной, инициализируются значением бесконечности. Расстояние обозначено переменной d, а предыдущая вершина — переменной π.

Алгоритм Беллмана-Форда проходит итеративный путь через все рёбра. Всего рёбер 9, поэтому путь этот будет насчитывать до 9 итераций. Во время каждой итерации какое-то одно ребро ослабляется. Во время первой итерации при переходе из вершины A в вершину C вес соответствующего ребра АС составляет -3. Текущее расстояние от исходной вершины до А равно бесконечности. При добавлении -3 к бесконечности результатом будет бесконечность, поэтому значение C будет равно бесконечности. Аналогично, при переходе от А до Е вес соответствующего ребра АЕ составляет 2. Но, так как расстояние до А бесконечно, значение Е будет равно бесконечности. То же верно и в отношении рёбер BF, CB, CH, FG, GB и HD. Все они дают один и тот же результат — бесконечность. И только последнее ребро, SA, даёт другой результат. Вес ребра SA равен 5. Текущее расстояние до S равно 0, поэтому расстояние от S до A составит 0 + 5 = 5. Вершина, предыдущая по отношению к вершине A, — это вершина S. После первой итерации алгоритм Беллмана-Форда нашёл путь от S до А.

Так как все рёбра были ослаблены, алгоритм начинает вторую итерацию. Нам важны рёбра, отходящие от S и A, поскольку расстояние до этих вершин уже известно. Расстояние до всех остальных вершин равно бесконечности. Обращаясь к таблице, содержащей рёбра, мы начинаем с ослабления ребра АС.

Вес ребра АС равен -3. Текущее расстояние до вершины А равно 5 (через ребро SA), поэтому расстояние до вершины С составит 5 + (-3) = 2. Вершина-предшественница С — это вершина А. Вес ребра АЕ равен 2. Расстояние до E составит 5 + 2 = 7 (через ребро SA). Вершиной, предыдущей по отношению к вершине E, становится теперь вершина A. Ребро BF пока ещё не может быть ослаблено.

Ребро CB может быть ослаблено, так как мы знаем расстояние до C. Расстояние до B составит 2 + 7 = 9, а вершина, предыдущая по отношению к вершине В, — это вершина C. Ребро CH может быть ослаблено, так как мы знаем расстояние до C. Расстояние до H составит 2 + (-3) = -1, а вершина-предшественница Н — это вершина C.

Ребро FG ещё не может быть ослаблено. Ребро GВ тоже не может быть ослаблено. А вот ребро HD можно ослабить, так как мы знаем, что расстояние до вершины H равно -1. Расстояние до вершины D составит -1 + 1 = 0, а вершина, предыдущая по отношению к вершине D, — это вершина H.

Расстояние до A от ребра SA уже посчитано и равно 5, так что никаких обновлений здесь не требуется. На этом заканчивается итерация 2.

Во время третьей итерации алгоритм Беллмана-Форда снова перебирает все рёбра. Ребра AC и AE дают одинаковые результаты. Ребро BF теперь можно ослабить. Расстояние до B равно 9, поэтому расстояние до вершины F составит 9 + (-5) = 4. Вершина-предшественница F — это вершина В.

Рёбра CB и CH дают одинаковые результаты, поэтому таблица остаётся прежней. Ребро FG теперь можно ослабить. Расстояние до вершины F равно 4, поэтому расстояние до вершины G составит 4 + 2 = 6. Вершина, предыдущая по отношению к вершине G, — это вершина F.

Ребро GB теперь можно ослабить. Расстояние до вершины G равно 6, поэтому расстояние до B составит 6 + 4 = 10. Так как до вершины B можно добраться более коротким путём (через ребро CB), таблица остаётся прежней.

Во время четвёртой итерации перебираются все рёбра. Алгоритм видит, что изменений нет, поэтому на четвёртой итерации он завершается.

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

Строится таблица с расстояниями и вершинами-предшественницами. Расстояния инициализируются значением бесконечности для вершин A, B и C. Расстояние до S равно 0.

Видим, что первое ребро АВ ещё не может быть ослаблено, так же как и рёбра BC и СА. Зато может быть ослаблено ребро SA. Расстояние до S равно 0, поэтому расстояние до A составит 0 + 3 = 3. Вершина, предыдущая по отношению к вершине А, — это вершина S.

Ребро SB тоже можно ослабить. Расстояние до вершины B составит 0 + 6 = 6. Вершина-предшественница B — это вершина S.

Первая итерация завершена. Во время второй итерации снова перебираются все рёбра.

Ребро AB может быть ослаблено во время второй итерации. Расстояние до A равно 3, поэтому расстояние до вершины B составит 3 + 5 = 8. Так как расстояние до B уже меньше нового значения, значение B сохраняется. До ребра BC можно добраться, пройдя расстояние 6 + 2 = 8. Вершина, предыдущая по отношению к вершине С, — это вершина В.

Дальше перебирается ребро СА. Расстояние до C равно 8 единицам, поэтому расстояние до А (через ребро BC) составит 8 + (-10) = -2. Так как расстояние до А через ребро CA меньше, чем через ребро SA, расстояние до А обновляется.

Рёбра SA и SB не дают ничего лучшего, поэтому вторая итерация завершена. Начинается третья итерация.

Ребро АВ ослаблено. Расстояние до A в настоящее время равно -2, поэтому расстояние до B через ребро AB составит -2 + 5 = 3. Так как расстояние до B через AB меньше, чем через SB, расстояние становится теперь равным 3. Вершиной, предыдущей по отношению к вершине В, становится теперь вершина A.

Дальше ослабляется ребро BC. Текущее расстояние до B равно 3, поэтому расстояние до C составит 3 + 2 = 5. Расстояние до C становится теперь равным 5.

Ребро СА ослабляется. Расстояние до C составит 5 + (-10) = -5. Расстояние до вершины А обновляется на -5 единиц.

Рёбра SA и SB не дают результатов лучше. В это время все кратчайшие пути должны были быть найдены. В других итерациях никаких изменений быть не должно.

Ребро АВ ослаблено. Расстояние до A равно -5, поэтому расстояние до B составит -5 + 5 = 0. Расстояние до В становится теперь равным 0. Так как значение меняется на n-й итерации, значения будут меняться и на n+1-й итерации. Значения будут продолжать меняться неопределённое время. Если мы внимательно изучим граф, то увидим, что ABC даёт отрицательное значение: 5 + 2 + (-10) = -3.

Целькратчайший путьнайти кратчайший путь от начальной вершины до вершины цели. Мы широко используем алгоритмы для решения проблемы кратчайших путей от конкурентного программирования до поиска направлений в Google Картах. Поняв ключевое понятие «расслабление края”, Действительно легче понять конкретные алгоритмы, скажем алгоритм Дийсктры или алгоритм Беллмана-Форда. Другими словами, может быть трудно сделать эти алгоритмы своими, не понимая ослабления границ. В этом посте я сосредоточусь на релаксации ребер и объясню общую структуру для решения проблемы кратчайших путей. Кроме того, мы рассмотрим простой алгоритм и его реализацию для лучшего понимания. Я использую Python для реализации. Этот пост структурирован следующим образом:

В чем проблема кратчайших путей?
Что такое крайнее расслабление?
Порядок релаксации
Кратчайший путь по DAG и его реализация

Обратите внимание, что мы не рассматриваем алгоритм Дейкстры или алгоритм Беллмана-Форда.

На графике ниже давайте подумаем о кратчайших путях от начальной вершины S до других вершин A и B.

Здесь я объясню важное и обычно используемое понятие релаксации краев для решения проблемы кратчайших путей. Как правило, вы можете решить все проблемы кратчайших путей с помощью рельефа. Релаксация края - это операция для расчета стоимости достижения вершины ниже. Конкретнее, операция станет:

ВершиныUа такжеvстоять соседей в графе иd[U] а такжеd[v] выдержать стоимость достижения вершинUа такжеvсоответственно. Также,вес(U,v) стоит вес ребра от вершиныUв вершинуv, Подводя итог, мы можем сделать этот рисунок ниже.

Теперь мы знаем, что можем достичь вершиныUот начальной вершины S через две вершины, и этот путь стоитd[U]. Также мы можем добраться до вершиныvот начальной вершины S до четырех вершин, и этот путь стоитd[v].

Здесь, крайние обновления релаксацииd[v] кd[U] +вес(U,v) когдаd[U] +вес(U,v) меньше чемd[v]. Другими словами, он обновляет текущую стоимость достижения вершиныv(d[v]) к более низкой стоимости достижения (d[U] +вес(U,v)). Причина, по которой он обновляет стоимость, состоит в том, что путь через вершинуUможет быть короче, потому что стоимость достижения пути через вершинуUбудет ниже, чем стоимость текущего пути. На самом деле,алгоритмы для задачи о кратчайших путях решают проблему путем многократного использования краевой релаксации,

Я покажу пример того, как мы можем решить проблему кратчайших путей, многократно используя граничную релаксацию. Давайте найдем кратчайшие пути для того же графа, что и раньше, с помощью релаксации ребер. Я предполагаю начальную вершину S и применяю релаксацию ребер к графу, чтобы получить кратчайшие пути к вершинам A и B.

Чтобы применить ослабление ребер, нам нужно знать стоимость достижения, но нет способа узнать это до поиска, поэтому мы инициализируем затраты достижения для вершин A и B как бесконечность (∞). Стоимость бесконечности для вершины означает, что мы не можем достичь этой вершины. С другой стороны, стоимость достижения от начальной вершины до начальной вершины равна нулю, поэтому мы устанавливаемdзначение вершины S как 0.

Сначала мы выбираем и ослабляем ребра, выходящие из вершины S, затем ребро, выходящие из вершины A. Прежде всего, применяем ослабление ребер к ребру SA.

Край СА удовлетворяетd[S] +вес(S, A)

Ребро SB удовлетворяетd[S] +вес(S, B)

Ребро AB удовлетворяетd[А] +вес(A, B)

Во-первых, давайте расслабим края прямой линии слева направо.

Далее мы расслабляем край EG.

Затем мы расслабляем край СЕ.

Здесь вы можете обнаружить, что мы можем снова расслабить край EG.

Кроме того, когда мы ослабляем ребро AC, мы можем снова расслабить ребра CE и EG. Поэтому, если мы не будем обращать внимание на порядок, мы бы снова и снова ослабляли один и тот же край. В приведенном выше примере мы можем эффективно ослабить края, если ослабим их слева направо. Однако есть слишком плотные графики для визуализации, как в примере выше. Поэтому кажется нереальным найти эффективный заказ заранее. Это причина, почему мы должны заботиться о расслабляющем порядке.

Ну как надо выбирать и расслаблять края. Фактически, алгоритмы кратчайших путей, такие как алгоритм Дейкстры или алгоритм Беллмана-Форда, дают нам расслабляющий порядок. Что это значиткаждый алгоритм кратчайших путей в основном повторяет ослабление ребер и создает расслабляющий порядок в зависимости от характера графа(положительные или отрицательные веса, DAG, . и т. д.). Другими словами, мы должны искать способ выбора и расслабления краев, наблюдая за характером графика. Таким образом, каждый алгоритм кратчайших путей имеет следующую общую структуру:

В предыдущем разделе я сказал, что мы должны выбрать способ релаксации краев, наблюдая за характером графика. Здесь я объясню простой и легкий алгоритм кратчайших путей для DAG (Направленный ациклический граф) с реализацией Python. ДАГ это график не имеет циклического. В этом разделе я объясню алгоритм, как вы знаететопологический порядок.Если вы не знакомы с этим, проверьте мою статью:Понимание поиска в глубину и топологической сортировки с Python?

В алгоритме кратчайших путей на DAG мы можем получить кратчайшие пути, выбирая и ослабляя исходящие ребра в топологическом порядке. Это конкретный алгоритм следующим образом:

Давайте посмотрим, как работает алгоритм. Я показываю график, который я инициализировалdи топологически отсортированы следующим образом. Я предполагаю, что начальная вершина - B. Давайте попробуем решить проблему кратчайших путей.

Каждая вершина отсортирована по топологии, поэтому мы просто ослабляем исходящие ребра слева направо. Мы не можем ослабить выходящий край из самой левой вершины А, поэтому мы не обновляемd,

Затем мы ослабляем исходящие ребра из вершины B, то есть BC и BD. Как только мы ослабим края, мы обновляем Π. Мы устанавливаем Π [C] как B и Π [D] как B

Затем мы ослабляем исходящие ребра из вершины C. Мы не можем ослабить выходящие ребра до вершины D, поэтому мы только обновляемd[E] иd[F]. Кроме того, мы обновляем Π [E] как C, Π [F] как C.

Мы обновляем исходящий край из вершины D. Мы только обновляемd[E] и Π [E] как D.

Мы обновляем выходящий край из вершины E. Мы также обновляем Π [F] как E.

От вершины F нет выходящего ребра. Завершаем релаксацию ребра. Наконец, мы получаем кратчайшие расстояния следующим образом: мы не проверяем, работает ли он здесь, но мы можем восстановить кратчайшие пути из Π.

Впоследствии, давайте реализуем алгоритм кратчайших путей на DAG в Python для лучшего понимания. Реализация приведена ниже: В этой реализации этот код решает проблему кратчайших путей на графе, использованном в приведенном выше объяснении. Этот код оцениваетdи Π решить проблему. Я предполагаю, что мы уже знали топологический порядок заранее.

Во-первых, давайте посмотрим, как выражается график и его веса. В приведенном выше коде график реализован следующим образом:

Соответствующий рисунок для графика ниже:

Например, когда мы смотрим на вершину C,график[‘C’] возвращает [‘D’, ‘E’, ‘F’], которые являются достижимыми соседями из вершины C. Таким образом, эти вершины образуют исходящие ребра из вершины C. Кроме того, вы обнаружите, чтовеса[U,v] соответствует весу ребраультрафиолетовый,

Далее, давайте посмотрим на роль каждой линииdag_shortest_pathполучить кратчайшие пути. Строки от 2 до 4 - это инициализация следующим образом:dначальной вершины как 0, остальные вершины как ∞. Кроме того, эти строки инициализируют Π, чтобы восстановить путь.

Линии от 9 до 12 соответствуют краевой релаксации.d_tempd[v] в коде соответствуетd[U] +вес(U,v) d[v] в состоянии краевой релаксации. Когда это условие выполнено, оно обновляетd[v]. Как только он обновляетdтакже обновляет Π.

Код повторяет этот процесс для исходящих ребер из каждой вершины в топологическом порядке. Этот повторяющийся процесс отрабатывается двумя циклами for.torderсодержит вершины в топологическом порядке. Так жеграфиквозвращает вершины для построения исходящих ребер из вершины. Итак, мы получаем преимуществоультрафиолетовыйрассматривая вершину изtorderкакUиграфик[U] какv,

Это все для объяснения кода. Мы не проверяем результат, но вы можете выполнить код с помощью следующей команды в своем терминале: вы узнаете, что можете получитьdи Π правильно.

Наконец, давайте подумаем о временной сложности этого алгоритма. В этом алгоритме есть две основные вычислительные части. Один для топологической сортировки. Другой для расслабления края. В приведенном выше коде мы не делаем топологическую сортировку, но на самом деле нам нужно это сделать. Поэтому мы должны принять это во внимание. Мы можем выполнить топологическую сортировку с помощью поиска в глубину, поэтому сложность времениО(|В| + |Е|). Количество циклов влияет только на временную сложность релаксации ребер, поскольку процессы в цикле протекают в постоянном времени. Количество петель дляtorderэто |В| и количество петель дляграфик[U] это |Е|. Таким образом, временная сложность краевой релаксацииО(|В| + |Е|). Таким образом, вся временная сложность алгоритмаО(|В| + |Е|).

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

Перед началом статьи хочу сказать, что еще больше полезной и нужной информации вы найдете в нашем Telegram-канале. Канал уже очень близок к отметке в 1000 подписчиков, сможем устроить новогодний подарок? Подпишитесь, мне будет очень приятно.

Начнём с того, что все исходящие ребра записываются в таблице в алфавитном порядке.

Читайте также: