# Dijkstra：使用STL的priority_queue的最短路径算法

2021年3月23日14:35:04 发表评论 477 次浏览

``````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``````

• Dijkstra的邻接矩阵表示算法(在C / C ++中, 时间复杂度为O(v2)
• Dijkstra的邻接表表示算法(时间复杂度为O(ELogV)的C语言)
• Dijkstra使用STL中设置的最短路径算法(在C ++中具有时间复杂度O(ELogV))

• 每当顶点距离减小时, 我们就会在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

5) Print distance array dist[] to print all shortest
paths.``````

``````// 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
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;
}

void Graph::addEdge( int u, int v, int 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.lsbin.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;
{
// 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\n" );
for ( int i = 0; i < V; ++i)
printf ( "%d \t\t %d\n" , 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.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``````

``````// 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;

void addEdge(vector <pair< int , int > > adj[], int u, int v, int 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\n" );
for ( int i = 0; i < V; ++i)
printf ( "%d \t\t %d\n" , i, dist[i]);
}

// Driver program to test methods of graph class
int main()
{
int V = 9;

// making above shown graph

return 0;
}``````

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