Рубрики

Кратчайший путь в направленном ациклическом графе

Учитывая взвешенный направленный ациклический граф и исходную вершину в графе, найдите кратчайшие пути от данного источника ко всем остальным вершинам.

Для общего взвешенного графика мы можем рассчитать кратчайшие расстояния от одного источника за время O (VE), используя алгоритм Беллмана – Форда . Для графика без отрицательных весов мы можем добиться большего успеха и рассчитать кратчайшие расстояния одного источника за время O (E + VLogV), используя алгоритм Дейкстры . Можем ли мы сделать еще лучше для направленного ациклического графа (DAG)? Мы можем рассчитать кратчайшие расстояния от одного источника за время O (V + E) для DAG. Идея состоит в том, чтобы использовать топологическую сортировку .

Мы инициализируем расстояния до всех вершин как бесконечные и расстояние до источника равными 0, затем находим топологическую сортировку графа. Топологическая сортировка графа представляет линейное упорядочение графа (см. Ниже, рисунок (b) является линейным представлением фигуры (a)). Получив топологический порядок (или линейное представление), мы по очереди обрабатываем все вершины в топологическом порядке. Для каждой обрабатываемой вершины мы обновляем расстояния ее смежных, используя расстояние текущей вершины.

Следующая цифра взята из этого источника. Он показывает пошаговый процесс поиска кратчайших путей.

Ниже приведен полный алгоритм поиска кратчайших расстояний.
1) Инициализируйте dist [] = {INF, INF,….} И dist [s] = 0, где s — исходная вершина.
2) Создайте топологический порядок всех вершин.
3) Выполните следующие действия для каждой вершины u в топологическом порядке.
………. Делайте следующее для каждой смежной вершины v из вас
……………… if (dist [v]> dist [u] + вес (u, v))
……………………… dist [v] = dist [u] + вес (u, v)

C ++

// C ++ программа для поиска кратчайших путей из одного источника для направленных ациклических графов
#include<iostream>
#include <list>
#include <stack>
#include <limits.h>
#define INF INT_MAX

using namespace std;

  
// График представлен с использованием списка смежности. Каждый узел списка смежности
// содержит номер вершины вершины, с которой соединяется ребро. Это также
// содержит вес ребра

class AdjListNode

{

    int v;

    int weight;

public:

    AdjListNode(int _v, int _w)  { v = _v;  weight = _w;}

    int getV()       {  return v;  }

    int getWeight()  {  return weight; }

};

  
// Класс для представления графа с использованием представления списка смежности

class Graph

{

    int V;    // Количество вершин

  

    // Указатель на массив, содержащий списки смежности

    list<AdjListNode> *adj;

  

    // Функция, используемая ShorttestPath

    void topologicalSortUtil(int v, bool visited[], stack<int> &Stack);

public:

    Graph(int V);   // Конструктор

  

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

    void addEdge(int u, int v, int weight);

  

    // Находит кратчайшие пути из заданной исходной вершины

    void shortestPath(int s);

};

  

Graph::Graph(int V)

{

    this->V = V;

    adj = new list<AdjListNode>[V];

}

  

void Graph::addEdge(int u, int v, int weight)

{

    AdjListNode node(v, weight);

    adj[u].push_back(node); // Добавить v в список u

}

  
// Рекурсивная функция, используемая ShorttestPath. Смотрите ссылку ниже для деталей
// https://www.geeksforgeeks.org/topological-sorting/amp/

void Graph::topologicalSortUtil(int v, bool visited[], stack<int> &Stack)

{

    // Пометить текущий узел как посещенный

    visited[v] = true;

  

    // Повторение для всех вершин, смежных с этой вершиной

    list<AdjListNode>::iterator i;

    for (i = adj[v].begin(); i != adj[v].end(); ++i)

    {

        AdjListNode node = *i;

        if (!visited[node.getV()])

            topologicalSortUtil(node.getV(), visited, Stack);

    }

  

    // Вставляем текущую вершину в стек, в котором хранится топологическая сортировка

    Stack.push(v);

}

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

void Graph::shortestPath(int s)

{

    stack<int> Stack;

    int dist[V];

  

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

    bool *visited = new bool[V];

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

        visited[i] = false;

  

    // Вызов рекурсивной вспомогательной функции для сохранения топологической сортировки

    // начиная со всех вершин по одной

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

        if (visited[i] == false)

            topologicalSortUtil(i, visited, Stack);

  

    // Инициализировать расстояния до всех вершин как бесконечные и расстояние

    // источник 0

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

        dist[i] = INF;

    dist[s] = 0;

  

    // Обработка вершин в топологическом порядке

    while (Stack.empty() == false)

    {

        // Получить следующую вершину из топологического порядка

        int u = Stack.top();

        Stack.pop();

  

        // Обновляем расстояния всех смежных вершин

        list<AdjListNode>::iterator i;

        if (dist[u] != INF)

        {

          for (i = adj[u].begin(); i != adj[u].end(); ++i)

             if (dist[i->getV()] > dist[u] + i->getWeight())

                dist[i->getV()] = dist[u] + i->getWeight();

        }

    }

  

    // Распечатать рассчитанные кратчайшие расстояния

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

        (dist[i] == INF)? cout << "INF ": cout << dist[i] << " ";

}

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

int main()

{

    // Создать график, приведенный на диаграмме выше. Здесь номера вершин

    // 0, 1, 2, 3, 4, 5 со следующими отображениями:

    // 0 = r, 1 = s, 2 = t, 3 = x, 4 = y, 5 = z

    Graph g(6);

    g.addEdge(0, 1, 5);

    g.addEdge(0, 2, 3);

    g.addEdge(1, 3, 6);

    g.addEdge(1, 2, 2);

    g.addEdge(2, 4, 4);

    g.addEdge(2, 5, 2);

    g.addEdge(2, 3, 7);

    g.addEdge(3, 4, -1);

    g.addEdge(4, 5, -2);

  

    int s = 1;

    cout << "Following are shortest distances from source " << s <<" n";

    g.shortestPath(s);

  

    return 0;

}

Джава

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

import java.io.*;

import java.util.*;

  

class ShortestPath

{

    static final int INF=Integer.MAX_VALUE;

    class AdjListNode

    {

        private int v;

        private int weight;

        AdjListNode(int _v, int _w) { v = _v;  weight = _w; }

        int getV() { return v; }

        int getWeight()  { return weight; }

    }

  

    // Класс для представления графа в виде списка смежности

    // узлы типа AdjListNode

    class Graph

    {

        private int V;

        private LinkedList<AdjListNode>adj[];

        Graph(int v)

        {

            V=v;

            adj = new LinkedList[V];

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

                adj[i] = new LinkedList<AdjListNode>();

        }

        void addEdge(int u, int v, int weight)

        {

            AdjListNode node = new AdjListNode(v,weight);

            adj[u].add(node);// Добавить v в список u

        }

  

        // Рекурсивная функция, используемая ShorttestPath.

        // Подробности смотрите ниже по ссылке

        void topologicalSortUtil(int v, Boolean visited[], Stack stack)

        {

            // Пометить текущий узел как посещенный.

            visited[v] = true;

            Integer i;

  

            // Повторение для всех вершин, смежных с этой вершиной

            Iterator<AdjListNode> it = adj[v].iterator();

            while (it.hasNext())

            {

                AdjListNode node =it.next();

                if (!visited[node.getV()])

                    topologicalSortUtil(node.getV(), visited, stack);

            }

            // Вставляем текущую вершину в стек, в котором хранится результат

            stack.push(new Integer(v));

        }

  

        // Функция для поиска кратчайших путей из заданной вершины. Это

        // использует рекурсивный topologicalSortUtil () для получения топологического

        // сортировка данного графа.

        void shortestPath(int s)

        {

            Stack stack = new Stack();

            int dist[] = new int[V];

  

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

            Boolean visited[] = new Boolean[V];

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

                visited[i] = false;

  

            // Вызываем рекурсивную вспомогательную функцию для хранения топологии

            // Сортировка, начиная со всех вершин по одной

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

                if (visited[i] == false)

                    topologicalSortUtil(i, visited, stack);

  

            // Инициализировать расстояния до всех вершин как бесконечные и

            // расстояние до источника как 0

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

                dist[i] = INF;

            dist[s] = 0;

  

            // Обработка вершин в топологическом порядке

            while (stack.empty() == false)

            {

                // Получить следующую вершину из топологического порядка

                int u = (int)stack.pop();

  

                // Обновляем расстояния всех смежных вершин

                Iterator<AdjListNode> it;

                if (dist[u] != INF)

                {

                    it = adj[u].iterator();

                    while (it.hasNext())

                    {

                        AdjListNode i= it.next();

                        if (dist[i.getV()] > dist[u] + i.getWeight())

                            dist[i.getV()] = dist[u] + i.getWeight();

                    }

                }

            }

  

            // Распечатать рассчитанные кратчайшие расстояния

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

            {

                if (dist[i] == INF)

                    System.out.print( "INF ");

                else

                    System.out.print( dist[i] + " ");

            }

        }

    }

  

    // Метод создания нового экземпляра графа через объект

    // класса ShortestPath.

    Graph newGraph(int number)

    {

        return new Graph(number);

    }

  

    public static void main(String args[])

    {

        // Создать график, приведенный на диаграмме выше. Здесь вершина

        // числа 0, 1, 2, 3, 4, 5 со следующими отображениями:

        // 0 = r, 1 = s, 2 = t, 3 = x, 4 = y, 5 = z

        ShortestPath t = new ShortestPath();

        Graph g = t.newGraph(6);

        g.addEdge(0, 1, 5);

        g.addEdge(0, 2, 3);

        g.addEdge(1, 3, 6);

        g.addEdge(1, 2, 2);

        g.addEdge(2, 4, 4);

        g.addEdge(2, 5, 2);

        g.addEdge(2, 3, 7);

        g.addEdge(3, 4, -1);

        g.addEdge(4, 5, -2);

  

        int s = 1;

        System.out.println("Following are shortest distances "+

                            "from source " + s );

        g.shortestPath(s);

    }

}
// Этот код предоставлен Aakash Hasija

питон

# Программа Python для поиска кратчайших путей из одного источника
№ для сложности направленных ациклических графов: OV (V + E)

from collections import defaultdict

  
# График представлен с использованием списка смежности. каждый
# узел списка смежности содержит номер вершины
# вершина, с которой соединяется ребро. Он также содержит
# вес ребра

class Graph:

    def __init__(self,vertices):

  

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

  

        # словарь, содержащий список смежности

        self.graph = defaultdict(list)

  

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

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

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

  

  

    # Рекурсивная функция, используемая ShorttestPath

    def topologicalSortUtil(self,v,visited,stack):

  

        # Пометить текущий узел как посещенный.

        visited[v] = True

  

        # Повторить для всех вершин, смежных с этой вершиной

        if v in self.graph.keys():

            for node,weight in self.graph[v]:

                if visited[node] == False:

                    self.topologicalSortUtil(node,visited,stack)

  

        # Вставить текущую вершину в стек, в котором хранится топологическая сортировка

        stack.append(v)

  

  

    '' 'Функция для поиска кратчайших путей из заданной вершины.

        Он использует рекурсивный topologicalSortUtil () для получения топологического

        сортировка заданного графа.

    def shortestPath(self, s):

  

        # Отметить все вершины как не посещенные

        visited = [False]*self.V

        stack =[]

  

        # Вызовите рекурсивную вспомогательную функцию для хранения топологии

        # Сортировка, начиная с исходной вершины

        for i in range(self.V):

            if visited[i] == False:

                self.topologicalSortUtil(s,visited,stack)

  

        # Инициализировать расстояния до всех вершин как бесконечные и

        # расстояние до источника как 0

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

        dist[s] = 0

  

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

        while stack:

  

            # Получить следующую вершину из топологического порядка

            i = stack.pop()

  

            # Обновление расстояний всех смежных вершин

            for node,weight in self.graph[i]:

                if dist[node] > dist[i] + weight:

                    dist[node] = dist[i] + weight

  

        # Распечатать рассчитанные кратчайшие расстояния

        for i in range(self.V):

            print ("%d" %dist[i]) if dist[i] != float("Inf") else  "Inf" ,

  

  

g = Graph(6)

g.addEdge(0, 1, 5)

g.addEdge(0, 2, 3)

g.addEdge(1, 3, 6)

g.addEdge(1, 2, 2)

g.addEdge(2, 4, 4)

g.addEdge(2, 5, 2)

g.addEdge(2, 3, 7)

g.addEdge(3, 4, -1)

g.addEdge(4, 5, -2)

  
# source = 1

s = 1

  

print ("Following are shortest distances from source %d " % s)

g.shortestPath(s)

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


Выход:

Following are shortest distances from source 1
INF 0 2 6 5 3 

Сложность времени: временная сложность топологической сортировки O (V + E). После нахождения топологического порядка алгоритм обрабатывает все вершины и для каждой вершины запускает цикл для всех смежных вершин. Общее число смежных вершин в графе равно O (E). Таким образом, внутренний цикл выполняется O (V + E) раз. Следовательно, общая временная сложность этого алгоритма составляет O (V + E).

Ссылки:
http://www.utdallas.edu/~sizheng/CS4349.d/l-notes.d/L17.pdf

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

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

Кратчайший путь в направленном ациклическом графе

0.00 (0%) 0 votes