Dijikstra's Algorithm

📌 Table of Contents

1. Introduction

Convex vs Concave

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.

2. How it Works

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.

3. Template


#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;
}