Skip to interview prep
Apexed

98. Shortest Paths With Negative Edges (Bellman-Ford)

MediumGraphs

A directed graph has n vertices (0 to n − 1) and weighted edges [u, v, w]; weights may be negative. Return an array dist where dist[i] is the shortest distance from src to i, or null if i cannot be reached.

If a negative-weight cycle can be reached from src, shortest distances are undefined: return null instead of an array.

Example 1

Input: n = 3, edges = [[0,1,4],[0,2,5],[1,2,-2]], src = 0
Output: [0, 4, 2]

Example 2

Input: n = 3, edges = [[0,1,1],[1,2,-1],[2,1,-1]], src = 0
Output: null

Constraints

  • 1 ≤ n ≤ 500
  • 0 ≤ edges.length ≤ 5000

Tab indents · Ctrl/⌘ + Enter runs · Esc then Tab leaves the editor

Run checks these cases; the expected output comes from the reference solution. Submit judges all 5 hidden and sample tests.

Code runs only in your browser in an isolated sandbox. Progress and submissions are saved on this device.

Shortest Paths With Negative Edges (Bellman-Ford) — coding interview practice — Apexed