Bellman-Ford algorithm

The Bellman-Ford algorithm finds shortest paths from a single source vertex to all of the other vertices. It is slower than Dijkstra’s algorithm, but handles graphs where negative cycles occur, therefore negative weights are acceptable.

Read more on wikipedia.


v e s
a b c (e times)

v – number of vertices
e – number of edges
s – start vertex
a b c – edge between a and b with weight c

Sample input

3 2 1
0 1 10
1 2 20


This algorithm returns shortest distances from city s to all other cities or message Negative cycle.


In the following solution there are two nested loops, so the algorithm runs in O(|V| · |E|) time.

Source code