Bellman–Ford Algorithm
Practice this coding question on Coding Gurukul.
Problem statement
Given a directed weighted graph and source s, use Bellman–Ford to find the shortest distance to every vertex. Edge weights may be negative. If a negative-weight cycle is reachable from s, print NEGATIVE CYCLE only. Ignore negative cycles that cannot be reached from s. Otherwise, print distances in vertex order and INF for unreachable vertices. Self-loops and repeated edges are allowed. Use signed 64-bit distances and O(n*m) time. Worked example The path 0→1→2 costs 4-6=-2, less than the direct cost 5. Vertex 3 is unreachable. Print 0 4 -2 INF.
Input format
First line: n m s. Next m lines: directed edge u v w.
Output format
Print NEGATIVE CYCLE, or n space-separated distances/INF tokens in vertex order.
Constraints
1 <= n <= 500; 0 <= m <= 3000; 0 <= s,u,v < n; -10^9 <= w <= 10^9.
Sample input
4 3 0 0 1 4 1 2 -6 0 2 5
Sample output
0 4 -2 INF
Sign in to run or submit a solution in C++, Java or Python.