Dijkstra
O(m log n)Single-source shortest paths on graphs with non-negative edge weights, using a priority queue with lazy deletion (the `d > dist[u]` skip). For negative weights use Bellman-Ford instead; for unweighted graphs plain BFS is enough.
// use it on
CSES: Shortest Routes I ↗
The canonical statement: shortest distance from city 1 to every other city, with weights up to 1e9. Note the long long / Python int distances.
// the code
// adj[u] = {{v, w}, ...}; returns dist from src (LLONG_MAX = unreachable)
vector<long long> dijkstra(int src, vector<vector<pair<int, int>>>& adj) {
int n = adj.size();
vector<long long> dist(n, LLONG_MAX);
priority_queue<pair<long long, int>, vector<pair<long long, int>>,
greater<>> pq;
dist[src] = 0;
pq.push({0, src});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue; // stale entry
for (auto [v, w] : adj[u])
if (d + w < dist[v]) pq.push({dist[v] = d + w, v});
}
return dist;
}// more shortest paths