Bellman–Ford Shortest Paths
Updated
Problem statement
Implement Bellman–Ford for a directed weighted graph with vertices 0 through n-1. Each row [u,v,w] in edges permits travel from u to v at cost w. Return the shortest distance from source to every vertex in vertex-label order.
For this exercise, return 1000000000 for an unreachable vertex. If any negative-weight cycle is reachable from source, return only [-1] instead of a distance array. An unreachable negative cycle does not trigger that result. The empty path to source has cost zero unless a reachable negative cycle exists.
Implement Bellman–Ford with the direction, input encoding, bounds and unreachable/cycle output rules above.
Function
bellmanFord(n: int, edges: int[][], source: int) → int[]Examples
Example 1
n = 3edges = [[0,1,4],[0,2,5],[1,2,-2]]source = 0return = [0,4,2]The route 0→1→2 costs 4-2=2, improving on the direct edge of cost 5.
Example 2
n = 2edges = [[0,1,-1],[1,0,0]]source = 0return = [-1]The reachable cycle 0→1→0 costs -1. Repeating it lowers the walk cost without bound, so return the cycle marker.
Constraints
- For this exercise, assume
1 <= n <= 100and0 <= edges.length <= 500. - Each edge has exactly three integers
[u,v,w], with0 <= u,v < nand-10000 <= w <= 10000. 0 <= source < n. Parallel edges and self-loops are allowed.
More JP Morgan Chase Onsite Interview questions
- LFU CacheONSITE INTERVIEW · Seen Nov 2026
- LRU CacheONSITE INTERVIEW · Seen Nov 2026
- Employees Above Average SalaryONSITE INTERVIEW · Seen Sep 2026
- Highest-Earning Employees By DepartmentONSITE INTERVIEW · Seen Sep 2026
- K Largest Integers in Descending OrderONSITE INTERVIEW · Seen Aug 2026
- Tile a Three-Row Board with DominoesONSITE INTERVIEW · Seen Jan 2026
- Two SumONSITE INTERVIEW · Seen Nov 2025
- Intersection of Two ListsONSITE INTERVIEW · Seen Jan 2025
- Maximum Subarray SumONSITE INTERVIEW · Seen Jan 2025
- Fibonacci NumberONSITE INTERVIEW · Seen Nov 2024
Similar questions at other companies
- Cheapest Flights Within K StopsAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Fire Station Response BillLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
- Minimum Product Path in a Directed GraphGoogle · ONSITE INTERVIEWGoogle interview questions
- Minimum Friend API CallsMercor · ONSITE INTERVIEWMercor interview questions
- Shortest Increasing Path to a TargetUber · ONSITE INTERVIEWUber interview questions
- Path With Maximum ProbabilitySalesforce · ONSITE INTERVIEWSalesforce interview questions
- Find and Reconstruct a Binary-Matrix PathMeta · PHONE SCREEN · ONSITE INTERVIEWMeta interview questions
- Cheapest Flights Within K StopsGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
- Open the Lock and Return a Shortest PathZip · PHONE SCREEN · ONSITE INTERVIEWZip interview questions
- Dijkstra's Shortest PathsMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
Interview reports that mention this question
JP Morgan Chase interview experiences
- JPMorgan Quant Stats Superdays: 3 Experiences (Part 3 of 3)
- JPMorgan Quant Modeling Superdays: 7 Experiences (Part 2 of 3)
- JPMorgan Quant Intern Superday: 19 Experiences (Part 1 of 3)
- JP Morgan Chase Data and AI Intern Superday: 11 Experiences
- JPMorgan Code for Good India 2024: 6 Experiences (Part 5 of 5)