Dijkstra's Shortest path Algorithm

Introduction:

This is a single source shortest path Algorithm where there is a single source from which we want to find shortest path to a node or to all other nodes.

Problem Statement:

find the shortest paths to all nodes from a start node.

Algorithm

1. A graph \(G(V, E)\) and start vertex \(s\) are given.

2. We create vertex set containing all vertices.

3. we have two arrays \(dist[\ ]\) initialized to \(\infty\) and \(prev[\ ]\) initilaized to -1 for all vertices

4. we make \(dist[s] = 0\).

5. while queue is not empty we pop vertex \(u\) from queue which has shortest value for \(dist[u]\).

6. for each vertex v in adjacency_list of u and in queue check if dist[v] can be relaxed i.e., check if \(dist[u]+ weightofedge(u, v) < dist[v]\) and accordingly update dist[v]

Pseudo code :

(source wikipedia)

function Dijkstra(Graph, source):
    dist[source] ← 0                           // Initialization

    create vertex priority queue Q

    for each vertex v in Graph:          
        if v ≠ source
            dist[v] ← INFINITY                 // Unknown distance from source to v
            prev[v] ← UNDEFINED                // Predecessor of v

        Q.add_with_priority(v, dist[v])


    while Q is not empty:                      // The main loop
        u ← Q.extract_min()                    // Remove and return best vertex
        for each neighbor v of u:              // only v that are still in Q
            alt ← dist[u] + length(u, v)
            if alt < dist[v]
                dist[v] ← alt
                prev[v] ← u
                Q.decrease_priority(v, alt)

     return dist, prev

Code :

    // single source shortest path
    // no negative edges
    #include <bits/stdc++.h>
    using namespace std;
    
    #define adjacency_list map<int, vector<pair<int, int>>>
    #define mp make_pair
    #define INF INT_MAX
    
    typedef struct graph
    {
        adjacency_list adj;
        int num_edges;
        int num_vertices;
    } graph;
    
    void dijkstra(graph G, int source)
    {
        set<int> vertex_set;
        for (int i = 0; i < G.num_vertices; i++)
        {
            vertex_set.insert(i);
        }
        vector<int> dist(G.num_vertices, INF);
        vector<int> prev(G.num_vertices, -1);
    
        dist[source] = 0;
        while (!vertex_set.empty())
        {
            int u = *(vertex_set.begin());
            int min_dist = INF;
            for (auto i : vertex_set)
            {
                if (dist[i] < min_dist)
                {
                    u = i;
                    min_dist = dist[i];
                }
            }
            vertex_set.erase(u);
            // u has vertex with min distance from source
            // terminate dijkstra if you want minimum distance to this vertex.
            for (auto i : G.adj[u])
            {
                int v = i.first;
                if (dist[u] != INF && dist[u] + i.second < dist[v])
                {
                    dist[v] = dist[u] + i.second;
                    prev[v] = u;
                }
            }
        }
        cout << "vertex prev dist\n";
    
        for (int i = 0; i < G.num_vertices; i++)
        {
            cout << i << " " << prev[i] << " " << dist[i] << "\n";
        }
        // cout << "\n";
    }
    
    int main()
    {
        // undirected graph
    
        graph G; // u - {{v1,w1}, {v2, w2}, .... {vk,wk}}
        cin >> G.num_vertices;
        cin >> G.num_edges;
    
        int u, v, w;
        for (int i = 0; i < G.num_edges; i++)
        {
            cin >> u >> v >> w;
            G.adj[u].push_back(mp(v, w));
            G.adj[v].push_back(mp(u, w)); // comment this if directed.
        }
        int s;
        // cout << "Enter start vertext for dijkstra : ";
        cin >> s;
    
        dijkstra(G, s);
        // cout << "\n";
    }

Complexity Analysis :

Time complexity : \(O(|V|^2)\) . This is the original dijkstra's algorithm which does not use min-heap to get min distance.

Try using min heap in the above implementation.

Complexity dependends on the implementation of this algorithm. \(O(|E|T_{decrease\_key}+|V|T_{extract\_min})\)