Practice › Graphs
Dijkstra's Shortest Paths
Medium · Graphs · Asked at Amazon, Google, Microsoft, Uber, Flipkart
For a weighted undirected graph, print the shortest distance from node 1 to every node (-1 if unreachable).
Input
First line: n m. Next m lines: u v w — an undirected edge with weight w.
Output
n distances (for nodes 1..n), space-separated.
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ m ≤ 2·10^5
- 1 ≤ w ≤ 10^4
Dijkstra's algorithm with a min-priority queue — O((n + m) log n).
Example 1
Input
4 4 1 2 4 1 3 1 3 2 2 2 4 5
Output
0 3 1 8
Example 2
Input
3 1 1 2 7
Output
0 7 -1
Hints
- BFS is not enough once edges have different weights.
- Always expand the unfinished node with the smallest known distance (min-heap). Skip heap entries that are older than the node's current distance.
Approach
Set dist[1] = 0, all others ∞, and push (0, 1) into a min-heap. Pop (d, u). If d is larger than dist[u], the entry is stale, so skip it. Otherwise relax each edge: if d + w < dist[v], update dist[v] and push (dist[v], v). With positive weights, the first time a node is popped its distance is final. Print -1 for nodes still at ∞. Distances can reach about 10^9, so use 64 bits.
Complexity: O((n + m) log n) time · O(n + m) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<pair<int, long long>>> adj(n + 1);
for (int i = 0; i < m; i++) {
int u, v;
long long w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
const long long INF = LLONG_MAX;
vector<long long> dist(n + 1, INF);
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
dist[1] = 0;
pq.push({0, 1});
while (!pq.empty()) {
long long d = pq.top().first;
int u = pq.top().second;
pq.pop();
if (d > dist[u]) continue; // stale entry
for (auto &e : adj[u])
if (d + e.second < dist[e.first]) {
dist[e.first] = d + e.second;
pq.push({dist[e.first], e.first});
}
}
for (int i = 1; i <= n; i++) cout << (dist[i] == INF ? -1 : dist[i]) << (i < n ? " " : "\n");
return 0;
}Python solution
import sys
import heapq
data = list(map(int, sys.stdin.read().split()))
n, m = data[0], data[1]
adj = [[] for _ in range(n + 1)]
for i in range(m):
u, v, w = data[2 + 3 * i : 5 + 3 * i]
adj[u].append((v, w))
adj[v].append((u, w))
INF = float("inf")
dist = [INF] * (n + 1)
dist[1] = 0
pq = [(0, 1)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue # stale entry
for v, w in adj[u]:
if d + w < dist[v]:
dist[v] = d + w
heapq.heappush(pq, (dist[v], v))
print(*(-1 if x == INF else x for x in dist[1:]))Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
List<List<long[]>> adj = new ArrayList<>();
for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
for (int i = 0; i < m; i++) {
int u = sc.nextInt(), v = sc.nextInt();
long w = sc.nextLong();
adj.get(u).add(new long[] {v, w});
adj.get(v).add(new long[] {u, w});
}
long[] dist = new long[n + 1];
Arrays.fill(dist, Long.MAX_VALUE);
dist[1] = 0;
PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
pq.add(new long[] {0, 1});
while (!pq.isEmpty()) {
long[] top = pq.poll();
long d = top[0];
int u = (int) top[1];
if (d > dist[u]) continue; // stale entry
for (long[] e : adj.get(u)) {
int v = (int) e[0];
if (d + e[1] < dist[v]) {
dist[v] = d + e[1];
pq.add(new long[] {dist[v], v});
}
}
}
StringBuilder sb = new StringBuilder();
for (int i = 1; i <= n; i++) sb.append(i > 1 ? " " : "").append(dist[i] == Long.MAX_VALUE ? -1 : dist[i]);
System.out.println(sb);
}
}Solve Dijkstra's Shortest Paths online · All practice problems