Dijkastra’s Algorithm

Dijkastra’s algorithm allows us to find the shortest path between any two vertices of a graph.

How Dijkastra’s Algorithm works-

    Dijkastra’s Algorithm works on the basis that any subpath B=>D of the shortest path A=>D between vertices A and D is also the shortest path between vertices B and D.
Dijkastra’s used this property in the opposite direction i.e we overestimate the distance of each vertex from the starting vertex. Then we visit each node and its neighbors to find the shortest subpath to those neighbors.
The algorithm uses a greedy approach in the sense that we find the next best solution hoping that the end result is the best solution for the whole problem.

Idea-
    1. Assign a distance value to all vertices in the input graph. Initialize all distance values as INFINITE, Assign distance value as 0 for the source vertex.







CP Problem:
Given a weight graph. Find the single source shortest path from a vertex U to all the vertices in the graph. If the node is unreachable, then print -1.

Note: The weights of the edges must be positive, Sample test case:

Input:
4    4    [4 vertices and 4 Edges]
1    2    24    [1,2 are edges and 24 is weights/cost]
1    4    20
3    1    3
4    3    12
1    [source edges]

Output:
0    24    3    15

Source Code

#include"bits/stdc++.h"
using namespace std;
const int inf = 1e7;
int main(){
    int n, m;
    cin>>n>>m;
    vector dist(n+1, inf);
    vector>>graph(n+1);
    for(int i=0;i         int u, v, w;
        cin>>u>>v>>w;
        graph[u].push_back({v,w});
        graph[v].push_back({u,w});
    }
    int source;
    cin>>source;
    dist[source]=0;
    set> s;
    s.insert({0,source}); //{wt, vertex}.....Order
    while(!s.empty()){
        auto x = *(s.begin());
        s.erase(x);
        for(auto it:graph[x.second]){
            if(dist[it.first]>dist[x.second]+it.second){
            s.erase({dist[it.first], it.first});
            dist[it.first]=dist[x.second]+it.second;
            s.insert({dist[it.first], it.first});
        }
        }
    }
    for(int i=1; i<=n; i++){
        if(dist[i]         cout<         }
        else{
         cout<<-1<<" ";
        }
    }
}

Watch the video for understande more-