C++ Dijkstra Algorithm using the Priority Queue

Dijkstra's algorithm is a popular shortest-path algorithm used to find the shortest path between two nodes in a graph. The algorithm uses a priority queue to store the distances to each node and selects the shortest distance at each step.

Syntax

void dijkstra(int start, int end) {
    // code
}

The dijkstra function takes two parameters - the starting node and the ending node.

Example

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <functional>
#define INF 0x3f3f3f3f

using namespace std;

typedef pair<int, int> pii;
typedef vector<vector<pii>> Graph;

void dijkstra(Graph& G, int start, int end) {
    vector<int> dist(G.size(), INF);
    priority_queue<pii, vector<pii>, greater<pii>> pq;

    dist[start] = 0;
    pq.emplace(0, start);

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        if (u == end) {
            break;
        }

        for (auto&& [v, wt] : G[u]) {
            if (dist[v] > dist[u] + wt) {
                dist[v] = dist[u] + wt;
                pq.emplace(dist[v], v);
            }
        }
    }

    cout << "Shortest path from " << start << " to " << end << " is " << dist[end] << endl;
}

int main() {
    Graph G(5);
    G[0].push_back(make_pair(1, 2));
    G[0].push_back(make_pair(2, 4));
    G[1].push_back(make_pair(2, 1));
    G[1].push_back(make_pair(3, 7));
    G[2].push_back(make_pair(3, 3));
    G[2].push_back(make_pair(4, 5));
    G[3].push_back(make_pair(4, 2));

    dijkstra(G, 0, 4);

    return 0;
}

Output

Shortest path from 0 to 4 is 11

Explanation

In the above example, we have defined a graph using an adjacency list. We then use the Dijkstra algorithm to find the shortest path from node 0 to node 4. The algorithm uses a priority queue to store the distances from the starting node to each visited node.

At each iteration, the algorithm selects the node with the shortest distance from the starting node and updates the distances of its neighboring nodes. The algorithm continues until it reaches the ending node or until all nodes have been visited.

Use

Dijkstra's algorithm is commonly used in route planning, network routing, and other applications involving finding shortest paths in graphs.

Important Points

• Dijkstra's algorithm is a popular shortest-path algorithm used to find the shortest path between two nodes in a graph.
• The algorithm uses a priority queue to store the distances to each node and selects the shortest distance at each step.
• The algorithm terminates when it reaches the ending node or when all nodes have been visited.
• Dijkstra's algorithm assumes that all edge weights are nonnegative.

Summary

In summary, Dijkstra's algorithm is a useful tool in graph theory for finding the shortest path between two nodes. It makes use of a priority queue to store distances to each node and selects the shortest distance at each step. The algorithm is widely used in route planning, network routing, and other applications involving finding shortest paths in graphs.