FastPrepAll-Pairs Shortest Paths
Problems/All-Pairs Shortest Paths

All-Pairs Shortest Paths

Morgan Stanley logoMorgan Stanley● MediumINTERNOAONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in a Morgan Stanley online assessment for interns. The report names an all-pairs shortest-path task. The campus author names the graph goal without writing down the graph rules. Here the edges are directed with nonnegative integer weights. The answer covers all ordered vertex pairs, with -1 for pairs that cannot be reached. The input has limits. Another report only mentions a shortest-path topic. We did not guess any single-source or graph details from it.

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

Given n vertices numbered 0 through n-1 and a directed weighted edge list edges, return an n-by-n matrix of shortest-path costs. Each edge is [from,to,weight]. For this exercise, weights are nonnegative integers.

Entry answer[u][v] is the minimum total weight of a directed path from u to v. Write -1 when no path exists. Every diagonal entry is 0 because the empty path from a vertex to itself is allowed.

Parallel edges and self-loops are allowed. A path follows the supplied directions; a reverse edge exists only if it is listed. Zero-weight edges are valid. Do not modify the edge list.

Function

allPairsShortestPaths(n: int, edges: int[][]) → int[][]

Examples

Example 1

n = 3edges = [[0,1,1],[1,2,1],[0,2,5],[2,0,1]]return = [[0,1,2],[2,0,1],[1,2,0]]

From 0, using 0→1→2 costs 2 instead of direct cost 5. The cycle gives 1→2→0 cost 2 and 2→0→1 cost 2. The three diagonal entries are 0.

Example 2

n = 4edges = [[0,1,0],[1,2,5],[0,2,9]]return = [[0,0,5,-1],[-1,0,5,-1],[-1,-1,0,-1],[-1,-1,-1,0]]

Edge 0→1 has cost 0, so 0→1→2 costs 5 instead of direct cost 9. No edge reaches vertex 3 from another vertex, and no reverse directions are implied. Unreachable entries are -1, while all diagonals remain 0.

Constraints

  • For this exercise, assume 1 <= n <= 50.
  • For this exercise, assume 0 <= edges.length <= 2000.
  • Every edge row has exactly 3 integers.
  • Every edge integer is between 0 and 1000000, inclusive.
  • Every edge endpoint from and to is less than n; the third integer is the nonnegative edge weight.

More Morgan Stanley Online Assessment questions

  • Three-Resource 0/1 KnapsackOA · Seen Sep 2026
  • Maximum Concurrent ProcessesOA · ONSITE INTERVIEW · Seen Sep 2026
  • Maximum Total of Nonadjacent RatingsOA · Seen Jul 2026
  • Count Shipment SchedulesOA · Seen Apr 2026
  • Delete and EarnOA · Seen Apr 2026
  • Interleave Array HalvesOA · Seen Apr 2026
  • Get Patch SequenceOA · Seen Feb 2025
  • String Subsequences 🐳OA · Seen Mar 2024
  • Binary Tree Level OrderOA · Seen Feb 2024
  • Merge IntervalsOA · Seen Feb 2024

Similar questions at other companies

  • Cities on Shortest Delivery RoutesMathWorks · OAMathWorks interview questions
  • Cheapest Flights Within K StopsGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
  • Cheapest Flights Within K StopsInMobi · OAInMobi interview questions
  • Drone Delivery with Battery Swap StationsCisco · OACisco interview questions
  • Minimum Path Cost with Edge DiscountsSkyscanner · ONSITE INTERVIEWSkyscanner interview questions
  • Cheapest Flight with Its PathAirbnb · OA · ONSITE INTERVIEWAirbnb interview questions
  • Maximum Gain on a Budgeted Returning WalkNVIDIA · ONSITE INTERVIEWNVIDIA interview questions
  • Shortest Paths in a Nonnegative Directed GraphNation with NaMo · PHONE SCREEN
  • Cheapest Flights Within K StopsAmazon · PHONE SCREEN · ONSITE INTERVIEW
  • Reach a Destination Through Scheduled FlightsGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions

Interview reports that mention this question

  • Morgan Stanley Intern Oldest Loops: 5 Experiences (Part 5 of 5)
  • Morgan Stanley Intern Earlier Loops: 5 Experiences (Part 3 of 5)

Morgan Stanley interview experiences

  • Morgan Stanley Apprenticeship and Tech Interviews: 6 Experiences
  • Morgan Stanley New Grad Technology Analyst: 2 Experiences
  • Morgan Stanley Intern OOP Loops: 5 Experiences (Part 4 of 5)
  • Morgan Stanley Intern Tech Rounds: 5 Experiences (Part 2 of 5)
All Morgan Stanley interview questionsSee Morgan Stanley hiring insights
Saved
class Solution {
    public int[][] allPairsShortestPaths(int n, int[][] edges) {
        // Write your code here.
    }

}
Checking account…