Алгоритм кратчайшего пути Дейкстры с использованием priority_queue STL

Опубликовано: 27 Января, 2022

Для данного графа и исходной вершины в графе найти кратчайшие пути от источника ко всем вершинам данного графа.


Вход: Источник = 0
Выход : 
     Расстояние от вершины до источника
        0 0
        1 4
        2 12
        3 19
        4 21
        5 11
        6 9
        7 8
        8 14

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

Алгоритм Дейкстры для представления матрицы смежности (в C / C ++ с временной сложностью O (v2)
Алгоритм Дейкстры для представления списка смежности (в C со сложностью времени O (ELogV))
Алгоритм кратчайшего пути Дейкстры с использованием набора в STL (в C ++ со сложностью времени O (ELogV))

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

Третья реализация проще, поскольку использует 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.

Below is C++ implementation of above idea.

// Program to find Dijkstra"s shortest path using
// priority_queue in STL
#include<bits/stdc++.h>
using namespace std;
# define INF 0x3f3f3f3f
  
// iPair ==>  Integer Pair
typedef pair<int, int> iPair;
  
// This class represents a directed graph using
// adjacency list representation
class Graph
{
    int V;    // No. of vertices
  
    // In a weighted graph, we need to store vertex
    // and weight pair for every edge
    list< pair<int, int> > *adj;
  
public:
    Graph(int V);  // Constructor
  
    // function to add an edge to graph
    void addEdge(int u, int v, int w);
  
    // prints shortest path from s
    void shortestPath(int s);
};
  
// Allocates memory for adjacency list
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));
}
  
// Prints shortest paths from src to all other vertices
void Graph::shortestPath(int src)
{
    // Create a priority queue to store vertices that
    // are being preprocessed. This is weird syntax in C++.
    // Refer below link for details of this syntax
    // https://www.geeksforgeeks.org/implement-min-heap-using-stl/
    priority_queue< iPair, vector <iPair> , greater<iPair> > pq;
  
    // Create a vector for distances and initialize all
    // distances as infinite (INF)
    vector<int> dist(V, INF);
  
    // Insert source itself in priority queue and initialize
    // its distance as 0.
    pq.push(make_pair(0, src));
    dist[src] = 0;
  
    /* Looping till priority queue becomes empty (or all
      distances are not finalized) */
    while (!pq.empty())
    {
        // The first vertex in pair is the minimum distance
        // vertex, extract it from priority queue.
        // vertex label is stored in second of pair (it
        // has to be done this way to keep the vertices
        // sorted distance (distance must be first item
        // in pair)
        int u = pq.top().second;
        pq.pop();
  
        // "i" is used to get all adjacent vertices of a vertex
        list< pair<int, int> >::iterator i;
        for (i = adj[u].begin(); i != adj[u].end(); ++i)
        {
            // Get vertex label and weight of current adjacent
            // of u.
            int v = (*i).first;
            int weight = (*i).second;
  
            //  If there is shorted path to v through u.
            if (dist[v] > dist[u] + weight)
            {
                // Updating distance of v
                dist[v] = dist[u] + weight;
                pq.push(make_pair(dist[v], v));
            }
        }
    }
  
    // Print shortest distances stored in dist[]
    printf("Vertex   Distance from Source
");
    for (int i = 0; i < V; ++i)
        printf("%d 		 %d
", i, dist[i]);
}
  
// Driver program to test methods of graph class
int main()
{
    // create the graph given in above fugure
    int V = 9;
    Graph g(V);
  
    //  making above shown graph
    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;
}

Output:

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

A Quicker Implementation using vector of pairs representation of weighted graph:

// Program to find Dijkstra"s shortest path using
// priority_queue in STL
#include<bits/stdc++.h>
using namespace std;
# define INF 0x3f3f3f3f
  
// iPair ==> Integer Pair
typedef pair<int, int> iPair;
  
// To add an edge
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));
}
   
  
// Prints shortest paths from src to all other vertices
void shortestPath(vector<pair<int,int> > adj[], int V, int src)
{
    // Create a priority queue to store vertices that
    // are being preprocessed. This is weird syntax in C++.
    // Refer below link for details of this syntax
    // http://geeksquiz.com/implement-min-heap-using-stl/
    priority_queue< iPair, vector <iPair> , greater<iPair> > pq;
  
    // Create a vector for distances and initialize all
    // distances as infinite (INF)
    vector<int> dist(V, INF);
  
    // Insert source itself in priority queue and initialize
    // its distance as 0.
    pq.push(make_pair(0, src));
    dist[src] = 0;
  
    /* Looping till priority queue becomes empty (or all
    distances are not finalized) */
    while (!pq.empty())
    {
        // The first vertex in pair is the minimum distance
        // vertex, extract it from priority queue.
        // vertex label is stored in second of pair (it
        // has to be done this way to keep the vertices
        // sorted distance (distance must be first item
        // in pair)
        int u = pq.top().second;
        pq.pop();
  
        // Get all adjacent of u. 
        for (auto x : adj[u])
        {
            // Get vertex label and weight of current adjacent
            // of u.
            int v = x.first;
            int weight = x.second;
  
            // If there is shorted path to v through u.
            if (dist[v] > dist[u] + weight)
            {
                // Updating distance of v
                dist[v] = dist[u] + weight;
                pq.push(make_pair(dist[v], v));
            }
        }
    }
  
    // Print shortest distances stored in dist[]
    printf("Vertex Distance from Source
");
    for (int i = 0; i < V; ++i)
        printf("%d 		 %d
", i, dist[i]);
}
  
// Driver program to test methods of graph class
int main()
{
    int V = 9;
    vector<iPair > adj[V];
  
    // making above shown graph
    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;
}

Output:

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

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

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

Вниманию читателя! Не переставай учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Алгоритм кратчайшего пути Дейкстры с использованием priority_queue STL

РЕКОМЕНДУЕМЫЕ СТАТЬИ