Dijkstra's Algorithm

Shortest path in non-negative weighted graphs using priority queue relaxation in O((V+E) log V).

[Graph]|

Jul 9, 2026

|explanatory_notes.md|

#dijkstra#shortest-path#priority-queue#graph

$cat source_code/

cpp

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define sz(x) int(x.size())

template <typename T = int>
struct Dijkstra {
  struct Edge {
    T v, w;
    Edge(T V = 0, T W = 0) : v(V), w(W) {}
    bool operator<(const Edge& e) const { return w > e.w; }
  };

  vector<vector<Edge>> adj;

  Dijkstra(int n, int edges, bool indirected = true) {
    adj = vector<vector<Edge>>(n + 1);
    for (int i = 0, u, v, w; i < edges; i++) {
      cin >> u >> v >> w;
      adj[u].push_back(Edge(v, w));
      if (indirected) adj[v].push_back(Edge(u, w));
    }
  }

  T Min_Cost(int src, int dest) {
    int n = sz(adj);
    vector<T> dist(n, numeric_limits<T>::max());
    dist[src] = 0;
    priority_queue<Edge> Dij;
    Dij.push(Edge(src, 0));
    while (!Dij.empty()) {
      auto [u, cost] = Dij.top();
      Dij.pop();
      for (auto& [v, w] : adj[u]) {
        if (dist[v] > dist[u] + w) {
          dist[v] = dist[u] + w;
          Dij.push(Edge(v, dist[v]));
        }
      }
    }
    return (dist[dest] == numeric_limits<T>::max() ? -1 : dist[dest]);
  }

  vector<T> get_dist(int src) {
    int n = sz(adj);
    vector<T> dist(n, numeric_limits<T>::max());
    dist[src] = 0;
    priority_queue<Edge> Dij;
    Dij.push(Edge(src, 0));
    while (!Dij.empty()) {
      auto [u, cost] = Dij.top();
      Dij.pop();
      for (auto& [v, w] : adj[u]) {
        if (dist[v] > dist[u] + w) {
          dist[v] = dist[u] + w;
          Dij.push(Edge(v, dist[v]));
        }
      }
    }
    return dist;
  }
};

void Solve() {
  // write your code here
}

int main() {
  ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int t = 1;
  // cin >> t;
  while (t--) Solve();
  return 0;
}

75 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

Dijkstra — Shortest Path (Non-Negative Weights)

Template Params

T = weight type (default int, use ll for large weights)

Constructor

Dijkstra dij(n, edges, indirected = true);
// n = node count (1-indexed), reads edges lines of "u v w" from cin

Methods

Min_Cost(src, dest) — returns T, min cost src→dest, -1 if unreachable

get_dist(src) — returns vector, distances from src to all nodes

Example

void Solve()
{
    int n, e; cin >> n >> e;
    Dijkstra dij(n, e, true);   // undirected
    cout << dij.Min_Cost(1, n) << "\n";
    auto dist = dij.get_dist(1);
}

Notes

Nodes are 1-indexed. Node count n is separate from edge count e.

Directed: Dijkstra dij(n, e, false);

Large weights: Dijkstra dij(n, e, true);

Min_Cost returns -1 if unreachable — only works with signed T.

Each constructor reads edges lines from cin. Don't create multiple objects from the same input.