Dijkstra's Algorithm

Dijkstra's Algorithm is a shortest path algorithm. The idea is just like BFS but instead of a queue we have a min priority_queue and now the graph is weighted. The only problem of Dijkstra's algorithm is that if it has a negative cycle then Dijkstra's algorithm will loop forever. This is why next time we will talk about Bellman-Ford algorithm, the Bellman-Ford algorithm can detect negative cycles and can just like Dijkstra's algorithm calculate the shortest path.

C++ Code

The following line does min priority_queue :
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
using namespace std;
 
int main(){
   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   int n,a,idx;
   cin >> n >> a >> idx;
   vector<int> ret(n,INT_MAX);
   vector<vector<pair<int,int>>> adj(n);
   for (int i=0; i<a; ++i){
      int id1,id2,dist;
      cin >> id1 >> id2 >> dist;
      adj[id1-1].push_back({id2-1,dist});
      adj[id2-1].push_back({id1-1,dist});
   }
   priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
   q.emplace(idx-1,0);
   ret[idx-1] = 0;
   while (!q.empty()){
      auto f=q.top();
      q.pop();
      for (auto& i:adj[f.first]){
         if (ret[i.first] > i.second+f.second){
            q.emplace(i.first,f.second+i.second);
            ret[i.first] = f.second+i.second;
         }
      }
   }
}