Рубрики

Обнаружить отрицательный цикл на графике | (Беллман Форд)

Нам дан ориентированный граф. Нам нужно вычислить, имеет ли граф отрицательный цикл или нет. Отрицательный цикл — это тот, в котором общая сумма цикла становится отрицательной.


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

Примеры:

Input : 4 4
        0 1 1
        1 2 -1
        2 3 -1
        3 0 -1

Output : Yes
The graph contains a negative cycle.

Идея состоит в том, чтобы использовать алгоритм Беллмана Форда .

Ниже приведен алгоритм поиска, если из заданного источника доступен отрицательный цикл веса.

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

// Программа на C ++ для проверки, содержит ли граф отрицательный
// весовой цикл с использованием алгоритма Беллмана-Форда. Эта программа
// работает, только если все вершины достижимы из источника
// вершина 0.
#include <bits/stdc++.h>

using namespace std;

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

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[graph->E];

    return graph;

}

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

bool isNegCycleBellmanFord(struct Graph* graph,

                           int src)

{

    int V = graph->V;

    int E = graph->E;

    int dist[V];

  

    // Шаг 1: Инициализировать расстояния от источника

    // ко всем остальным вершинам как БЕСКОНЕЧНО

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

            return true;

    }

  

    return false;

}

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

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;

  

    if (isNegCycleBellmanFord(graph, 0))

        cout << "Yes";

    else

        cout << "No";

  

    return 0;

}

Выход :

No

Как это работает?
Как обсуждалось в алгоритме Беллмана Форда , для данного источника он сначала рассчитывает кратчайшие расстояния, которые имеют не более одного ребра на пути. Затем он вычисляет кратчайшие пути с двумя ребрами по крайней мере и так далее. После i-й итерации внешнего цикла вычисляются кратчайшие пути с не более чем i ребрами. Там может быть максимум | V | — 1 ребро в любом простом пути, поэтому внешний цикл выполняет | v | — 1 раз. Если есть отрицательный весовой цикл, то еще одна итерация даст закороченный путь.

Как работать с отключенным графом (если цикл недоступен из источника)?
Приведенный выше алгоритм и программа могут не работать, если данный граф отключен. Это работает, когда все вершины достижимы из исходной вершины 0.

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

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

using namespace std;

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

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[graph->E];

    return graph;

}

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

bool isNegCycleBellmanFord(struct Graph* graph,

                           int src, int dist[])

{

    int V = graph->V;

    int E = graph->E;

  

    // Шаг 1: Инициализировать расстояния от источника

    // ко всем остальным вершинам как БЕСКОНЕЧНО

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

            return true;

    }

  

    return false;

}

  
// Возвращает true, если данный граф имеет отрицательный вес
// цикл.

bool isNegCycleDisconnected(struct Graph* graph)

{

  

    int V = graph->V;

    // Отслеживать посещенные вершины, чтобы избежать

    // пересчеты.

    bool visited[V];

    memset(visited, 0, sizeof(visited));

  

    // Этот массив заполнен Bellman-Ford

    int dist[V];

  

    // Позвоните в Bellman-Ford для всех этих вершин

    // которые не посещены

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

        if (visited[i] == false) {

            // Если цикл найден

            if (isNegCycleBellmanFord(graph, i, dist))

                return true;

  

            // Пометить все посещенные вершины

            // в вызове выше.

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

                if (dist[i] != INT_MAX)

                    visited[i] = true;

        }

    }

  

    return false;

}

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

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;

  

    if (isNegCycleDisconnected(graph))

        cout << "Yes";

    else

        cout << "No";

  

    return 0;

}

Выход :

No


Обнаружение отрицательного цикла с помощью Флойд Варшалл

Эта статья предоставлена kartik . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Обнаружить отрицательный цикл на графике | (Беллман Форд)

0.00 (0%) 0 votes