All-Pairs Shortest Paths
Updated
Problem statement
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