Рубрики

Алгоритм Беллмана – Форда | DP-23

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

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

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

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

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

3) Этот шаг сообщает, есть ли отрицательный весовой цикл на графике. Делайте следующее для каждого края уф
…… Если dist [v]> dist [u] + вес ребра uv, то «График содержит отрицательный весовой цикл»
Идея шага 3 заключается в том, что шаг 2 гарантирует кратчайшие расстояния, если график не содержит отрицательный весовой цикл. Если мы повторим все ребра еще раз и получим более короткий путь для любой вершины, тогда будет отрицательный весовой цикл

Как это работает? Как и другие проблемы динамического программирования, алгоритм вычисляет кратчайшие пути снизу вверх. Сначала он рассчитывает кратчайшие расстояния, которые имеют не более одного ребра на пути. Затем он вычисляет кратчайшие пути не более чем с 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 раза. Расстояния минимизируются после второй итерации, поэтому третья и четвертая итерации не обновляют расстояния.

Реализация:

C ++

// Программа на C ++ для единственного источника Беллмана-Форда
// алгоритм кратчайшего пути.
#include <bits/stdc++.h>

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

struct Edge {

    int src, dest, weight;

};

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

struct Graph {

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

    int V, E;

  

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

    struct Edge* edge;

};

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

struct Graph* createGraph(int V, int E)

{

    struct Graph* graph = new Graph;

    graph->V = V;

    graph->E = E;

    graph->edge = new Edge[E];

    return graph;

}

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

void printArr(int dist[], int n)

{

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

    for (int i = 0; i < n; ++i)

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

}

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

void BellmanFord(struct Graph* graph, int src)

{

    int V = graph->V;

    int E = graph->E;

    int dist[V];

  

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

    // как БЕСКОНЕЧНО

    for (int i = 0; i < V; i++)

        dist[i] = INT_MAX;

    dist[src] = 0;

  

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

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

    // края

    for (int i = 1; i <= V - 1; i++) {

        for (int j = 0; j < E; 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[v] = dist[u] + weight;

        }

    }

  

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

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

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

    // это цикл.

    for (int i = 0; i < E; 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 < dist[v]) {

            printf("Graph contains negative weight cycle");

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

        }

    }

  

    printArr(dist, V);

  

    return;

}

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

int main()

{

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

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

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

    struct Graph* graph = createGraph(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;

  

    BellmanFord(graph, 0);

  

    return 0;

}

Джава

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

import java.util.*;

import java.lang.*;

import java.io.*;

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

class Graph {

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

    class Edge {

        int src, dest, weight;

        Edge()

        {

            src = dest = weight = 0;

        }

    };

  

    int V, E;

    Edge edge[];

  

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

    Graph(int v, int e)

    {

        V = v;

        E = e;

        edge = new Edge[e];

        for (int i = 0; i < e; ++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 < V; ++i)

            dist[i] = Integer.MAX_VALUE;

        dist[src] = 0;

  

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

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

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

        for (int i = 1; i < V; ++i) {

            for (int j = 0; j < E; ++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[v] = dist[u] + weight;

            }

        }

  

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

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

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

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

        for (int j = 0; j < E; ++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]) {

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

                return;

            }

        }

        printArr(dist, V);

    }

  

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

    void printArr(int dist[], int V)

    {

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

        for (int i = 0; i < V; ++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;

  

        graph.BellmanFord(graph, 0);

    }

}
// Аакаш Хасия

питон

# Программа Python для единственного источника Беллмана-Форда
# алгоритм кратчайшего пути.

  

from collections import defaultdict

  
# Класс для представления графика

class Graph:

  

    def __init__(self, vertices):

        self.V = vertices # Количество вершин

        self.graph = [] # словарь по умолчанию для хранения графика

   

    # функция для добавления ребра на график

    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):

  

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

        # как бесконечный

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

        dist[src] = 0 

  

  

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

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

        # ребра

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

            # Обновление значения dist и родительского индекса смежных вершин

            # выбранная вершина. Рассмотрим только те вершины, которые все еще находятся в

            # очередь

            for u, v, w in self.graph:

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

                        dist[v] = dist[u] + w

  

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

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

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

        # это цикл.

  

        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

                          

        # распечатать все расстояние

        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)

  
# Распечатать решение

g.BellmanFord(0)

  
# Этот код предоставлен Neelam Yadav

C #

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

  

using System;

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

class Graph {

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

    class Edge {

        public int src, dest, weight;

        public Edge()

        {

            src = dest = weight = 0;

        }

    };

  

    int V, E;

    Edge[] edge;

  

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

    Graph(int v, int e)

    {

        V = v;

        E = e;

        edge = new Edge[e];

        for (int i = 0; i < e; ++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 < V; ++i)

            dist[i] = int.MaxValue;

        dist[src] = 0;

  

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

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

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

        for (int i = 1; i < V; ++i) {

            for (int j = 0; j < E; ++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[v] = dist[u] + weight;

            }

        }

  

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

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

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

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

        for (int j = 0; j < E; ++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]) {

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

                return;

            }

        }

        printArr(dist, V);

    }

  

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

    void printArr(int[] dist, int V)

    {

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

        for (int i = 0; i < V; ++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 на рисунке выше)

        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;

  

        graph.BellmanFord(graph, 0);

    }

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

}


Выход:

Vertex   Distance from Source
0                0
1                -1
2                2
3                -2
4                1

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

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

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

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


Алгоритм Беллмана Форда (простая реализация)

Ссылки:
http://www.youtube.com/watch?v=Ttezuzs39nk
http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
http://www.cs.arizona.edu/classes/cs445/spring07/ShortestPath2.prn.pdf

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

Рекомендуемые посты:

Алгоритм Беллмана – Форда | DP-23

0.00 (0%) 0 votes