5.Dijkstra’s Algorithm(Single Source Shortest Path)

Dijkstra's algorithm is to find the shortest paths from the source vertex to all other vertices in the graph.

Algorithm Steps:

• Set all vertices distances = infinity except for the source vertex, set the source distance = 0.

• Push the source vertex in a min-priority queue in the form (distance , vertex), as the comparison in the min-priority queue will be according to vertices distances.

• Pop the vertex with the minimum distance from the priority queue (at first the popped vertex = source).

• Update the distances of the connected vertices to the popped vertex in case of "current vertex distance + edge weight < next vertex distance", then push the vertex with the new distance to the priority queue.

• If the popped vertex is visited before, just continue without using it.

• Apply the same algorithm again until the priority queue is empty.

Heap Implementation

And in Dijkstra’s algorithm, we need a priority queue and below operations on priority queue :

• ExtractMin : from all those vertices whose shortest distance is not yet found, we need to get vertex with minimum distance.

• DecreaseKey : After extracting vertex we need to update distance of its adjacent vertices, and if new distance is smaller, then update that in data structure.

Priority queue doesn’t support decrease key and delete operations. So set can also be used

void findSortestPath(vector<pair<int, int>> v[], vector<int> &dist, vector<bool> &vs ,int src)
{

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, src});
    dist[src] = 0;

    while (!pq.empty())
    {

        pair<int, int> p = pq.top();
        pq.pop();

        int node = p.second;
        
        if(vs[node]){
            continue;
        }

        vs[node] = true;

        for (auto itr = v[node].begin(); itr != v[node].end(); itr++)
        {

            int x = (*itr).first;
            int w = (*itr).second;

            if (dist[node] + w < dist[x])
            {
                dist[x] = w + dist[node];
                pq.push({dist[x], x});
            }
        }
    }
    return;
}

Time Complexity: O(V + E log V)

Using Set

void findSortestPath(vector<pair<int, int>> v[], vector<int> &dist, int src)
{

    set<pair<int, int>> st;
    st.insert({0, src});
    dist[src] = 0;

    while (!st.empty())
    {
        int node = (*st.begin()).second;
        st.erase(st.begin());

        for (auto itr = v[node].begin(); itr != v[node].end(); itr++)
        {
            int x = (*itr).first;
            int w = (*itr).second;

            if (w + dist[node] < dist[x])
            {
                if (dist[x] != INT_MAX)
                {
                    st.erase(st.find({dist[x], x}));
                }

                dist[x] = dist[node] + w;
                st.insert({dist[x], x});
            }
        }
    }

    return;
}

Set in C++ are typically implemented using Self-balancing binary search trees. Therefore, time complexity of set operations like insert, delete is logarithmic and time complexity of above solution is O(E LogV)).