Dijkstra Algorithm
Practice this coding question on Coding Gurukul.
Problem statement
Given a directed weighted graph and source s, use Dijkstra’s algorithm to find the shortest distance from s to every vertex. All edge weights are nonnegative. Print distances in vertex order. The distance to s is 0. Print -1 for an unreachable vertex. An edge u v w goes from u to v only. Zero-weight edges, self-loops and repeated edges are allowed. Use a min-priority queue, signed 64-bit distances, and O((n+m) log n) time. Worked example The path 0→2→1 costs 2+3=5, less than the direct edge of weight 9. Distances from 0 are 0, 5, 2 and -1; vertex 3 is unreachable.
Input format
First line: n m s. Next m lines: u v w.
Output format
Print n distances in vertex order 0 to n-1, using -1 for unreachable vertices.
Constraints
1 <= n <= 100000; 0 <= m <= 200000; 0 <= s,u,v < n; 0 <= w <= 10^9.
Sample input
4 3 0 0 1 9 0 2 2 2 1 3
Sample output
0 5 2 -1
Sign in to run or submit a solution in C++, Java or Python.