Рубрики

Алгоритм кратчайшего пути Дейкстры, использующий приоритетную очередь STL

По заданному графу и исходной вершине в графе найдите кратчайшие пути от источника ко всем вершинам данного графа.



Input : Source = 0
Output : 
     Vertex   Distance from Source
        0                0
        1                4
        2                12
        3                19
        4                21
        5                11
        6                9
        7                8
        8                14

Мы обсудили кратчайшие пути реализации Дейкстры.

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

Третья реализация проще, так как использует STL. Проблема с третьей реализацией заключается в том, что она использует набор, который, в свою очередь, использует самобалансирующиеся деревья двоичного поиска. Для алгоритма Дейкстры всегда рекомендуется использовать кучу (или очередь приоритетов), так как требуемые операции (извлечение ключа минимума и уменьшения) соответствуют специализации кучи (или очереди приоритетов). Однако проблема в том, что priority_queue не поддерживает клавишу уменьшения. Чтобы решить эту проблему, не обновляйте ключ, а вставьте еще одну его копию. Поэтому мы разрешаем несколько экземпляров одной и той же вершины в очереди с приоритетами. Этот подход не требует операции нажатия клавиши и имеет ниже важные свойства.

  • Всякий раз, когда расстояние до вершины уменьшается, мы добавляем еще один экземпляр вершины в priority_queue. Даже если есть несколько экземпляров, мы рассматриваем экземпляр только с минимальным расстоянием и игнорируем другие экземпляры.
  • Временная сложность остается O (ELogV)), поскольку в очереди приоритетов будет не более O (E) вершин, а O (Log E) такое же, как O (Log V)

Ниже приведен алгоритм, основанный на представленной выше идее.

1) Initialize distances of all vertices as infinite.

2) Create an empty priority_queue pq.  Every item
   of pq is a pair (weight, vertex). Weight (or 
   distance) is used used as first item  of pair
   as first item is by default used to compare
   two pairs

3) Insert source vertex into pq and make its
   distance as 0.

4) While either pq doesn't become empty
    a) Extract minimum distance vertex from pq. 
       Let the extracted vertex be u.
    b) Loop through all adjacent of u and do 
       following for every vertex v.

           // If there is a shorter path to v
           // through u. 
           If dist[v] > dist[u] + weight(u, v)

               (i) Update distance of v, i.e., do
                     dist[v] = dist[u] + weight(u, v)
               (ii) Insert v into the pq (Even if v is
                    already there)
               
5) Print distance array dist[] to print all shortest
   paths. 

Ниже приведена реализация вышеуказанной идеи на C ++.

// Программа для поиска кратчайшего пути Дейкстры, используя
// приоритетная очередь в STL
#include<bits/stdc++.h>

using namespace std;

# define INF 0x3f3f3f3f

  
// iPair ==> Целочисленная пара

typedef pair<int, int> iPair;

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

class Graph

{

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

  

    // В взвешенном графе нам нужно хранить вершину

    // и весовая пара для каждого ребра

    list< pair<int, int> > *adj;

  

public:

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

  

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

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

  

    // печатает кратчайший путь из s

    void shortestPath(int s);

};

  
// Распределяет память для списка смежности

Graph::Graph(int V)

{

    this->V = V;

    adj = new list<iPair> [V];

}

  

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

{

    adj[u].push_back(make_pair(v, w));

    adj[v].push_back(make_pair(u, w));

}

  
// Печатает кратчайшие пути из src во все остальные вершины

void Graph::shortestPath(int src)

{

    // Создать приоритетную очередь для хранения вершин, которые

    // обрабатываются Это странный синтаксис в C ++.

    // Обратитесь к ссылке ниже для деталей этого синтаксиса

    // https://www.geeksforgeeks.org/implement-min-heap-using-stl/amp/

    priority_queue< iPair, vector <iPair> , greater<iPair> > pq;

  

    // Создать вектор для расстояний и инициализировать все

    // расстояния как бесконечные (INF)

    vector<int> dist(V, INF);

  

    // Вставить сам источник в приоритетную очередь и инициализировать

    // его расстояние равно 0.

    pq.push(make_pair(0, src));

    dist[src] = 0;

  

    / * Цикл пока приоритетная очередь не станет пустой (или все

      расстояния не уточняются) * /

    while (!pq.empty())

    {

        // Первая вершина в паре - это минимальное расстояние

        // вершина, извлечь ее из приоритетной очереди.

        // метка вершины хранится во второй из пары

        // нужно сделать так, чтобы сохранить вершины

        // отсортированное расстояние (расстояние должно быть первым элементом

        // в паре)

        int u = pq.top().second;

        pq.pop();

  

        // 'i' используется для получения всех смежных вершин вершины

        list< pair<int, int> >::iterator i;

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

        {

            // Получить метку вершины и вес текущего смежного

            // из вас.

            int v = (*i).first;

            int weight = (*i).second;

  

            // Если есть короткий путь к v через u.

            if (dist[v] > dist[u] + weight)

            {

                // Обновление расстояния v

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

                pq.push(make_pair(dist[v], v));

            }

        }

    }

  

    // Печатать кратчайшие расстояния, хранящиеся в dist []

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

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

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

}

  
// Программа драйвера для тестирования методов класса графа

int main()

{

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

    int V = 9;

    Graph g(V);

  

    // делаем выше показанный график

    g.addEdge(0, 1, 4);

    g.addEdge(0, 7, 8);

    g.addEdge(1, 2, 8);

    g.addEdge(1, 7, 11);

    g.addEdge(2, 3, 7);

    g.addEdge(2, 8, 2);

    g.addEdge(2, 5, 4);

    g.addEdge(3, 4, 9);

    g.addEdge(3, 5, 14);

    g.addEdge(4, 5, 10);

    g.addEdge(5, 6, 2);

    g.addEdge(6, 7, 1);

    g.addEdge(6, 8, 6);

    g.addEdge(7, 8, 7);

  

    g.shortestPath(0);

  

    return 0;

}

Выход:

Vertex   Distance from Source
0          0
1          4
2          12
3          19
4          21
5          11
6          9
7          8
8          14

Более быстрая реализация с использованием вектора представления пар взвешенного графа :

// Программа для поиска кратчайшего пути Дейкстры, используя
// приоритетная очередь в STL
#include<bits/stdc++.h>

using namespace std;

# define INF 0x3f3f3f3f

  
// iPair ==> Целочисленная пара

typedef pair<int, int> iPair;

  
// Добавить ребро

void addEdge(vector <pair<int, int> > adj[], int u,

                                     int v, int wt)

{

    adj[u].push_back(make_pair(v, wt));

    adj[v].push_back(make_pair(u, wt));

}

   

  
// Печатает кратчайшие пути из src во все остальные вершины

void shortestPath(vector<pair<int,int> > adj[], int V, int src)

{

    // Создать приоритетную очередь для хранения вершин, которые

    // обрабатываются Это странный синтаксис в C ++.

    // Обратитесь к ссылке ниже для деталей этого синтаксиса

    // http://geeksquiz.com/implement-min-heap-using-stl/

    priority_queue< iPair, vector <iPair> , greater<iPair> > pq;

  

    // Создать вектор для расстояний и инициализировать все

    // расстояния как бесконечные (INF)

    vector<int> dist(V, INF);

  

    // Вставить сам источник в приоритетную очередь и инициализировать

    // его расстояние равно 0.

    pq.push(make_pair(0, src));

    dist[src] = 0;

  

    / * Цикл пока приоритетная очередь не станет пустой (или все

    расстояния не уточняются) * /

    while (!pq.empty())

    {

        // Первая вершина в паре - это минимальное расстояние

        // вершина, извлечь ее из приоритетной очереди.

        // метка вершины хранится во второй из пары

        // нужно сделать так, чтобы сохранить вершины

        // отсортированное расстояние (расстояние должно быть первым элементом

        // в паре)

        int u = pq.top().second;

        pq.pop();

  

        // Получить все смежные с вами.

        for (auto x : adj[u])

        {

            // Получить метку вершины и вес текущего смежного

            // из вас.

            int v = x.first;

            int weight = x.second;

  

            // Если есть короткий путь к v через u.

            if (dist[v] > dist[u] + weight)

            {

                // Обновление расстояния v

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

                pq.push(make_pair(dist[v], v));

            }

        }

    }

  

    // Печатать кратчайшие расстояния, хранящиеся в dist []

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

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

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

}

  
// Программа драйвера для тестирования методов класса графа

int main()

{

    int V = 9;

    vector<iPair > adj[V];

  

    // делаем выше показанный график

    addEdge(adj, 0, 1, 4);

    addEdge(adj, 0, 7, 8);

    addEdge(adj, 1, 2, 8);

    addEdge(adj, 1, 7, 11);

    addEdge(adj, 2, 3, 7);

    addEdge(adj, 2, 8, 2);

    addEdge(adj, 2, 5, 4);

    addEdge(adj, 3, 4, 9);

    addEdge(adj, 3, 5, 14);

    addEdge(adj, 4, 5, 10);

    addEdge(adj, 5, 6, 2);

    addEdge(adj, 6, 7, 1);

    addEdge(adj, 6, 8, 6);

    addEdge(adj, 7, 8, 7);

  

    shortestPath(adj, V, 0);

  

    return 0;

}

Выход:

Vertex Distance from Source
0          0
1          4
2          12
3          19
4          21
5          11
6          9
7          8
8          14

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

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

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

Алгоритм кратчайшего пути Дейкстры, использующий приоритетную очередь STL

0.00 (0%) 0 votes