Shortest Distance from Source (Bellman-Ford Algorithm)

Given a weighted directed graph represented as an edge list edges, the number of vertices V, and a source node src, return an array dist where dist[i] represents the shortest distance (sum of edge weights) from src to node i. If node i is unreachable from src, dist[i] should be Infinity. If a negative weight cycle is detected, return null.

Note:

The edge list uses [u, v, weight] format, where u is the source node, v is the destination node, and weight can be positive, zero, or negative.

Examples

Input: edges = [[0, 1, 4], [0, 2, 5], [1, 2, -3], [2, 3, 4]], V = 4, src = 0
Output: [0, 4, 1, 5]
Explanation:
- Distance from 0 to 0: 0 (same node)
- Distance from 0 to 1: 4 (direct edge 0 -> 1)
- Distance from 0 to 2: 1 (0 -> 1 -> 2, weight: 4 + (-3) = 1, shorter than 0 -> 2 with weight 5)
- Distance from 0 to 3: 5 (0 -> 1 -> 2 -> 3, weight: 4 + (-3) + 4 = 5)

Input: edges = [[0, 1, 1], [1, 2, -1], [2, 0, -1]], V = 3, src = 0
Output: null
Explanation: Negative cycle detected (0 -> 1 -> 2 -> 0 with total weight -1)

Input: edges = [[0, 1, 5], [1, 2, 3], [2, 3, 1]], V = 4, src = 0
Output: [0, 5, 8, 9]
Explanation: Simple path 0 -> 1 -> 2 -> 3

Constraints

• Graph is represented as an edge list where each edge is [u, v, weight]
• Edge weights can be positive, zero, or negative
• V is the number of vertices (nodes numbered from 0 to V-1)
• Graph may contain cycles
• Graph may be disconnected
• Distance from src to itself is always 0
• Unreachable nodes have distance Infinity
• If a negative weight cycle is reachable from source, return null

Function Signature

function bellmanFord(edges, V, src) {
  // Your code here
}

Test Cases

• Base cases: single node edges = [], V = 1, src = 0 -> [0]
• Simple path: [[0, 1, 2], [1, 2, 3]], V = 3, src = 0 -> [0, 2, 5]
• Negative edges: [[0, 1, 4], [0, 2, 5], [1, 2, -3], [2, 3, 4]], V = 4, src = 0 -> [0, 4, 1, 5]
• Negative cycle: [[0, 1, 1], [1, 2, -1], [2, 0, -1]], V = 3, src = 0 -> null
• Disconnected nodes: [[0, 1, 2]], V = 3, src = 0 -> [0, 2, Infinity]
• Early termination: graph where no updates occur before V-1 iterations
• Large graphs with various edge weights