Bellman–Ford Algorithm

Given vertexCount vertices numbered 0 through vertexCount - 1, directed weighted edges [left, right, weight], and source, return shortest distances from…

Given vertexCount vertices numbered 0 through vertexCount - 1, directed weighted edges [left, right, weight], and source, return shortest distances from source in vertex order. Return 1000000000 for an unreachable vertex. Return [-1] if and only if a source-reachable negative cycle exists. Negative edges, self-loops, repeated directed edge occurrences, and disconnected graphs are permitted.

- 2 <= vertexCount <= 500 - 1 <= edges.length <= vertexCount * (vertexCount - 1) - Endpoint IDs and source are integers from 0 through vertexCount - 1 - Edge weights are integers from -1000 through 1000 - The edge cap counts occurrences; input row order is retained - Visual inputs have at most 12 vertices and 24 edges and must fit the full-pass trace budget; dense combinations can be rejected - C++ and Java need wide intermediate distances while detecting negative cycles; finite no-cycle output stays within -499000..499000 - Run Code and Submit use the full coding bounds.

Example 1: input vertexCount = 3, edges = [[1,2,-2],[0,1,3]], source = 0; output [0,3,1]. The first scan reaches vertex 1 after its outgoing edge was scanned; the next scan propagates the path to vertex 2.

Example 2: input vertexCount = 3, edges = [[1,2,-1],[2,1,0]], source = 0; output [0,1000000000,1000000000]. The negative cycle is unreachable from source 0 and does not invalidate its distance array.

Category: Graphs. Topic: graph. Difficulty: Hard. Patterns: graph-traversal.