Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. BFS is not enough once edges have different weights.
  2. 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