Cover Image for C++ Dijkstra Algorithm using the priority queue
106 views

C++ Dijkstra Algorithm using the priority queue

Dijkstra’s algorithm is used to find the shortest path from a source vertex to all other vertices in a weighted graph. When implementing Dijkstra’s algorithm in C++, using a priority queue (e.g., std::priority_queue) can help improve efficiency in selecting the next vertex with the smallest tentative distance.

Here’s a C++ program that demonstrates Dijkstra’s algorithm using a priority queue:

C++
#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

// Define an edge structure to represent edges in the graph
struct Edge {
    int to;
    int weight;
    Edge(int _to, int _weight) : to(_to), weight(_weight) {}
};

// Define a custom comparison function for the priority queue
struct Compare {
    bool operator()(const pair<int, int>& a, const pair<int, int>& b) const {
        return a.second > b.second;
    }
};

// Function to perform Dijkstra's algorithm
void dijkstra(const vector<vector<Edge>>& graph, int source) {
    int n = graph.size();
    vector<int> distance(n, INT_MAX);
    vector<bool> visited(n, false);

    priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;

    distance[source] = 0;
    pq.push({source, 0});

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

        if (visited[u]) continue;
        visited[u] = true;

        for (const Edge& edge : graph[u]) {
            int v = edge.to;
            int w = edge.weight;

            if (!visited[v] && distance[u] + w < distance[v]) {
                distance[v] = distance[u] + w;
                pq.push({v, distance[v]});
            }
        }
    }

    // Print the shortest distances from the source vertex
    cout << "Shortest distances from vertex " << source << ":\n";
    for (int i = 0; i < n; ++i) {
        cout << "Vertex " << i << ": " << distance[i] << endl;
    }
}

int main() {
    int n = 6; // Number of vertices
    vector<vector<Edge>> graph(n);

    // Adding edges to the graph
    graph[0].push_back(Edge(1, 2));
    graph[0].push_back(Edge(2, 4));
    graph[1].push_back(Edge(2, 1));
    graph[1].push_back(Edge(3, 7));
    graph[2].push_back(Edge(4, 3));
    graph[3].push_back(Edge(4, 1));
    graph[3].push_back(Edge(5, 5));
    graph[4].push_back(Edge(5, 2));

    int source = 0; // Source vertex

    dijkstra(graph, source);

    return 0;
}

In this code:

  • We define an Edge structure to represent edges in the graph.
  • We define a custom comparison function (Compare) for the priority queue to ensure that the vertex with the smallest tentative distance is selected.
  • The dijkstra function performs Dijkstra’s algorithm to calculate the shortest distances from the source vertex to all other vertices in the graph.
  • In the main function, we create a sample graph, specify the source vertex, and call the dijkstra function to find and print the shortest distances from the source vertex to all other vertices.

Make sure to adjust the graph and source vertex according to your specific problem.

YOU MAY ALSO LIKE...

The Tech Thunder

The Tech Thunder

The Tech Thunder


COMMENTS