Implementation of Dijkstra's Algorithm

To understand the implementation of Dijkstra's Algorithm using C++

Objective

To understand the implementation of Dijkstra's Algorithm using C++

#include <bits/stdc++.h>
using namespace std;

#define INF 0x3f3f3f3f

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));
}

void dijkstra(vector> adj[], int V, int src) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    vector<int> dist(V, INF);

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

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

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

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

    cout << "Vertex | Distance from Source" << endl;
    for(int i = 0; i < V; ++i) {
        cout << i << "\t | \t\t" << dist[i] << endl;
    }
}

int main() {
    int V = 5;
    vector<pair<int, int>> adj[V];

    addEdge(adj, 0, 1, 10);
    addEdge(adj, 0, 4, 5);
    addEdge(adj, 1, 2, 1);
    addEdge(adj, 1, 4, 2);
    addEdge(adj, 2, 3, 4);
    addEdge(adj, 3, 0, 7);
    addEdge(adj, 3, 2, 6);
    addEdge(adj, 4, 1, 3);
    addEdge(adj, 4, 2, 9);
    addEdge(adj, 4, 3, 2);

    dijkstra(adj, V, 0);

    return 0;
}

Discussion of Algorithm

1. Start
2. Set the source vertex distance as 0, and all other vertices as infinity
3. Add the source vertex to a priority queue
4. While the priority queue is not empty:
   • Extract the vertex with the smallest distance
   • For each vertex v connected to u:
   • If dist[u] + weight(u, v) < dist[v], update dist[v] to dist[u] + weight(u, v)
5. Output the shortest distance from the source to all vertices
6. End

Representations

Flow Diagram

   +----------------------------------+
   |                                  |
   |            Start                 |
   |              |                   |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |    // Initialize variables       |
   |       and data structures        |
   |           int V = 5;             |
 | vector<pair<int,int>> adj[V]; |
   |              |                   |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |  // Add edges to the graph       |
   |    addEdge(adj, 0, 1, 10);       |
   |             ...                  |
   |    addEdge(adj, 4, 3, 2);        |
   |              |                   |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |      Dijkstra's Algorithm        |
   |       (Shortest Path)            |
   |                                  |
   |       priority_queue pq          |
   |   vector<int> dist(V, INF);   |
   |        dist[src] = 0;            |
   |    pq.push(make_pair(0, src));   |
   |                                  |
   +----------------------------------+
   
                  |
                  V
   +----------------------------------+
   |                                  |
   |      Process nodes in the        |
   |      priority queue              |
   |                                  |
   |            pq.pop();           |
   |if(dist[v] > dist[u] + weight) {  |
   |   dist[v] = dist[u] + weight;    |
   |   pq.push(make_pair(dist[v], v));|
   | }                                |
   +----------------------------------+
   
                  |
                  V
   +----------------------------------+
   |                                  |
   |       Print the distances        |
   |       from the source node       |
   |                                  |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |             Exit                 |
   |              |                   |
   +----------------------------------+

Tabular Dry Run

Output

Vertex | Distance from Source
0      |         0
1      |         8
2      |         9
3      |         7
4      |         5