FastPrepDijkstra's Shortest Paths
Problems/Dijkstra's Shortest Paths

Dijkstra's Shortest Paths

Microsoft logoMicrosoft● MediumINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in a review of a Microsoft software engineering internship. The review names Dijkstra's shortest-path algorithm, to be coded by the candidate, with no graph format or limits. The round was the first of the two final-round interviews.

Here the graph is directed, with n nodes numbered 0 to n - 1 (n up to 1000) and up to 10^4 weighted edges [u, v, w] with weights 0 to 10^5. Parallel edges and self-loops may appear. You return the shortest distance from the source to every node, with -1 for a node that cannot be reached. Writing the algorithm by hand is the point of the editorial. The tests cannot tell whether a library priority queue was used.

Our version is about 80% the same as the reported question.

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 <= 1000 and 0 <= source < n
  • 0 <= edges.length <= 10^4 and edges[i].length == 3
  • 0 <= u_i, v_i < n and 0 <= 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

Interview reports that mention this question

  • Microsoft SWE Intern, Late 2025: 47 Experiences (Part 3 of 6)
  • Microsoft SWE Intern Interviews: 244 Experiences (Part 1 of 6)

Microsoft interview experiences

  • Microsoft Explore and Student SWE: 12 Experiences (Part 6 of 6)
  • Microsoft SWE Intern, Early 2025: 41 Experiences (Part 5 of 6)
  • Microsoft SWE Intern, Mid 2025: 42 Experiences (Part 4 of 6)
  • Microsoft SWE Intern, Early 2026: 54 Experiences (Part 2 of 6)
All Microsoft interview questionsSee Microsoft hiring insights
Saved
class Solution {
    public int[] shortestDistances(int n, int[][] edges, int source) {
        // Write your code here.
    }
}
Checking account…