Dijkstra's Shortest Paths
Updated
Problem statement
Implement Dijkstra's algorithm. A directed graph has n nodes numbered 0 to n - 1. Each edges[i] = [u_i, v_i, w_i] is a one-way edge from u_i to v_i with non-negative weight w_i. The same pair of nodes may be joined by several edges, and an edge may start and end at the same node.
The length of a path is the sum of its edge weights. Return an array dist of length n where dist[v] is the length of the shortest path from source to v, or -1 if v cannot be reached from source. dist[source] is 0.
Function
shortestDistances(n: int, edges: int[][], source: int) → int[]Examples
Example 1
n = 4edges = [[0,1,4],[0,2,1],[2,1,2],[1,3,1],[2,3,5]]source = 0return = [0,3,1,4]Node 1 is cheaper through node 2 (1 + 2 = 3) than directly (4). Node 3 is reached through 2 and 1 for 3 + 1 = 4, cheaper than 1 + 5 = 6 through the edge 2 to 3. So the distances are [0, 3, 1, 4].
Example 2
n = 3edges = [[1,0,2],[0,1,7]]source = 1return = [2,0,-1]Edges are one-way. From node 1, node 0 costs 2. Node 2 has no incoming edge, so it cannot be reached and its distance is -1.
Constraints
1 <= n <= 1000and0 <= source < n0 <= edges.length <= 10^4andedges[i].length == 30 <= u_i, v_i < nand0 <= w_i <= 10^5
More Microsoft Onsite Interview questions
- Longest Substring Without Repeating CharactersONSITE INTERVIEW · Seen Nov 2026
- Valid ParenthesesONSITE INTERVIEW · Seen Nov 2026
- Count a User's Actions in an Event LogONSITE INTERVIEW · Seen Nov 2026
- Smallest Batch Size Within a Step LimitONSITE INTERVIEW · Seen Nov 2026
- Count Subarrays with Equal Even and Odd CountsONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Rot All OrangesONSITE INTERVIEW · Seen Nov 2026
- Coin ChangeONSITE INTERVIEW · Seen Oct 2026
- Daily USD Totals with Effective-Dated Exchange RatesONSITE INTERVIEW · Seen Oct 2026
- Number Words to Digits in Any LanguageONSITE INTERVIEW · Seen Oct 2026
- Totals from a Tiered Rate TableONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- Cheapest Flights Within K StopsAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Minimum Product Path in a Directed GraphGoogle · ONSITE INTERVIEWGoogle interview questions
- Path With Maximum ProbabilitySalesforce · ONSITE INTERVIEWSalesforce interview questions
- Single-Source Shortest PathsRippling · ONSITE INTERVIEWRippling interview questions
- Minimum-Weight Path Through a MatrixMeta · ONSITE INTERVIEWMeta interview questions
- Hub Vertices Within a RadiusThe Walt Disney Company · ONSITE INTERVIEWThe Walt Disney Company interview questions
- Minimum Path Cost with Edge DiscountsSkyscanner · ONSITE INTERVIEWSkyscanner interview questions
- Shortest Paths in a Nonnegative Directed GraphNation with NaMo · PHONE SCREEN
- Dijkstra Shortest Paths in a Weighted Undirected GraphGoldman Sachs · PHONE SCREENGoldman Sachs interview questions
- Shortest Paths to Multiple TargetsWaymo · PHONE SCREENWaymo interview questions