Dijkstra's algorithm is a greedy algorithm designed to solve the single-source shortest path problem for a graph with non-negative edge weights. Its goal is to find the shortest path from a starting node to all other nodes in the graph.
The algorithm operates by maintaining a set of visited nodes and a set of unvisited nodes. It also keeps track of the shortest known distance from the starting node to every other node.
Time complexity: O((E+V)logV), where V is the number of vertices (nodes) and E is the number of edges.
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pp push_back
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair <int,int>;
using pll = pair <ll,ll>;
using pld = pair <ld,ld>;
const char el ='\n';
const char sp = ' ';
const int maxn = 1e5+5, mod = 1e9+7;
const ll inf = 1e18;
int n,m,s,t;
ll d[maxn];
vector <pii> adj[maxn];
priority_queue <pll,vector<pll>,greater<pll>> f;
void input()
{
// Read number of nodes (n) and edges (m)
cin>>n>>m;
// Set source (s) and target (t) nodes
s=1;
t=n;
// Initialize distances to all nodes as infinity
fill(d,d+n+1,inf);
// Read graph edges and weights
for(int i=1,u,v,w;i<=m;++i)
{
cin>>u>>v>>w;
// Add edge from u to v with weight w
adj[u].pp({v,w});
}
// Set distance to the source node to 0
d[s]=0;
// Push the source node with its distance into the priority queue
f.push({0,s});
// Main loop of Dijkstra's algorithm
while(f.size()>0)
{
// Get the node with the smallest distance from the priority queue
pll tmp=f.top();
int v=tmp.ss;
// Remove it from the queue
f.pop();
// Optimization: if we've already found a shorter path, skip this node
if(d[v]!=tmp.ff) continue;
// Iterate through all neighbors of the current node
for(pii i : adj[v])
{
// Relaxation step: check if a shorter path to the neighbor exists
if(d[v]+i.ss<d[i.ff])
{
// Update the distance to the neighbor
d[i.ff]=d[v]+i.ss;
// Push the neighbor with its new, shorter distance into the queue
f.push({d[i.ff],i.ff});
}
}
}
// Check if the target node is reachable
if(d[t]<inf) cout<<d[t];
else cout<<-1; // If not, print -1
}
int32_t main()
{
freopen("DIJKSTRA.INP","r",stdin);
freopen("DIJKSTRA.OUT","w",stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// Call the function to run the algorithm
input();
return 0;
}