dijkstra algorithm in c++ geeksforgeeks

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

using namespace std;

vector<int> dijkstra(vector<vector<pair<int, int>>> graph, int source) {
    int n = graph.size();
    vector<int> dist(n, INT_MAX);
    vector<bool> visited(n, false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    dist[source] = 0;
    pq.push(make_pair(0, source));

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

        if (visited[u]) {
            continue;
        }

        visited[u] = true;

        for (auto neighbor : graph[u]) {
            int v = neighbor.first;
            int weight = neighbor.second;

            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push(make_pair(dist[v], v));
            }
        }
    }

    return dist;
}

int main() {
    int n, m;
    cout << "Enter the number of vertices: ";
    cin >> n;
    cout << "Enter the number of edges: ";
    cin >> m;

    vector<vector<pair<int, int>>> graph(n);

    cout << "Enter the edges and their weights:\n";
    for (int i = 0; i < m; i++) {
        int u, v, weight;
        cin >> u >> v >> weight;
        graph[u].push_back(make_pair(v, weight));
        graph[v].push_back(make_pair(u, weight));
    }

    int source;
    cout << "Enter the source vertex: ";
    cin >> source;

    vector<int> dist = dijkstra(graph, source);

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

    return 0;
}

The code provided is an implementation of Dijkstra's algorithm in C++ to find the shortest paths from a given source vertex to all other vertices in a weighted graph. Let's go through the code step by step to understand how it works.

Importing Required Libraries

The code starts by including the necessary C++ libraries: - iostream for input/output operations - vector for storing the graph structure and distances - queue for the priority queue used in the algorithm - climits for initializing the distances with a large value

Dijkstra's Algorithm Function

Next, a function named dijkstra is defined. It takes two parameters: - graph: a vector of vectors of pairs representing the weighted graph - source: the source vertex from which we want to find the shortest paths

Inside the function, the number of vertices is obtained from the size of the graph vector. Two vectors, dist and visited, are initialized to track the distances and visited vertices, respectively. A priority queue named pq is declared as a min heap of pairs, where the first element represents the distance and the second element represents the vertex.

The distance to the source vertex is set to 0, and the pair (0, source) is pushed into the priority queue. This pair represents the distance to the source vertex itself.

The main part of the algorithm is implemented in a while loop that continues until the priority queue is empty. In each iteration, the vertex with the minimum distance is extracted from the priority queue.

If the vertex has already been visited, the loop skips to the next iteration. Otherwise, the vertex is marked as visited.

The loop then iterates over all the neighbors of the current vertex. For each neighbor, the vertex index v and the edge weight weight are extracted. If the distance to the current vertex plus the weight of the edge to the neighbor is less than the current distance to the neighbor, the distance is updated, and the pair (new distance, neighbor) is pushed into the priority queue.

After the while loop finishes, the function returns the vector dist containing the shortest distances from the source vertex to all other vertices.

Main Function

The main function is where the user interacts with the program. It prompts the user to enter the number of vertices and edges in the graph. Then, it creates a vector of vectors named graph to represent the graph.

Next, the user is prompted to enter the edges and their weights. For each edge, the code reads the vertices u and v, and the weight of the edge. The edge is added to both graph[u] and graph[v] as a pair of the neighbor vertex and the weight.

The user is then asked to enter the source vertex. The dijkstra function is called with the graph and source as arguments, and the returned vector dist is stored.

Finally, the shortest distances from the source vertex to all other vertices are printed.

That's the explanation of the provided code implementing Dijkstra's algorithm in C++.