Bellman-Ford algorithm is a graph search algorithm that can handle edges with negative weight of traversal (this means, better to pass through such an edge than not to pass). Edges with negative weights may arise after transforming many real world problems into graph search algorithm.Dijkstra algorithm and only should be used when graph edges may have negative weights (Dijkstra algorithm cannot handle such graphs).
Unlike Dijkstra or A*, Bellman-Ford algorithm does not try to pick the optimal set of nodes to scan: it simply iterates over all edges that may come in any order. For each node, the algorithm may assign a "predecessor". At the end of the algorithm, the path from the target to the starting point can be traced by tracking which node is a predecessor in the path. Bellman-Ford algorithm iterates through edges, not through nodes (vertices) of the graph, and treats all edges as directional (hence path from A to B may have different cost than path from B to A). A pair of opposite edges must be added for every connection if the node relations in the task are not directional.
The algorithm itself is described as following:
Assign the zero tentative distance to the start node. Assign the infinite tentative distance to all other nodes.
Repeat as many times as there are nodes in the graph For each edge |uv| in the graph, where u is the source and v is the destination if u.distance + |uv|.weight < v.distance then v.distance := u.distance + |uv|.weight v.predecessor := u end if
A negative cycle is a cycle whose edges sum to a negative value. If graph contains such a cycle, then walks of arbitrarily low weight can be constructed (there is no shortest path). The extension, defined below, detects negative cycles and report their existence:
This extension is usually understood as part of the Bellman-Ford algorithm itself. After running the algorithms as described above, with all node distances still assigned, the following steps must be performed:
For each edge |uv| in the graph if u.distance + |uv|.weight < v.distance then report negative cycle - no solution
This means, if after one iteration of the loop some node still can be "relaxed" (finding a "better solution" for it), this can only mean that the task itself is not consistent (negative weight cycle present) and no proper solution exists.