Bellman-Ford Algorithm

Bellman-Ford algorithm is single source shortest path algorithm, it finds shortest paths from a given source vertex to all other vertices. The algorithm also works with negative weight edges if the graph doesn’t have a negative weight cycle. If a graph has only edges of positive weight then Dijkstra’s algorithm offers more efficient solution.

Bellman-Ford algorithm is a dynamic programming algorithm where the each step evaluate the shortest paths by the shortest paths evaluated in previous step. Each step evaluates shortest paths of length one edge greater than the paths evaluated in previous step.

The algorithm works with simple graph, multi-graph, connected graph and disconnected graph or any combination of these. It has $O(V \times E)$ worst time complexity and $O(V)$ worst space complexity, here $V$ is number of vertices $|V|$ and $E$ is number of edge $|E|$.

Tutorial Document

Tutorial document BellmanFordAlgorithm.pdf explains Bellman-Ford algorithm in details using a directed graph as a complete example.

Tutorial first explains what is the negative weight cycle and why there is no shortest path solution if a graph has a negative weight cycle. It then explains why algorithm requires $V-1$ iteration by explaining the max-degree of a graph, a graph theory concept. Finally tutorial explains how algorithm detects a negative weight cycle if present in a graph.

Tutorial then explain a cycle find technique called Floyd's Cycle-Finding/ Hare & Tortoise algorithm because Bellman-Ford algorithm can detect a negative weight cycle but it can’t locate it. Tutorial first explains how cycle may be detected at a vertex that belongs to the cycle or it may be outside or far way from the cycle using three example graphs. Tutorial then explains Floyd's Cycle-Finding algorithm by considering one of the graph as a complete example.

Usage

Repository provides implementation in C++ as a default language but if you understand the algorithm explained by tutorial BellmanFordAlgorithm.pdf, algorithm can be easily implemented in your preferred programming language.

Implementation can be used to find shortest path from a given source vertex to all other vertices of a graph by passing the source vertex and a graph to bellmanFordAlgorithm::shortestPath function.

Graph Initialization

It is a simple directed weighted graph with three vertices and it can be considered as a triangle where three corners of the triangle represent three vertices. The left side of the triangle has one vertex and it is labeled as vertex 0 and the opposite side of it there are two vertices labeled 1 and 2 in clockwise direction respectively.

std::vector< std::vector< std::pair<std::size_t, std::ptrdiff_t> > >  graph { { {1, -1}, {2, 3} }, { {2, 1} }, {  } };

Here an edge is represented by a std::pair<std::size_t, std::ptrdiff_t> where first element std::size_t represents vertex and second element std::ptrdiff_t represents weight of the edge.

Last entry in the graph is an empty std::vector< pair<std::size_t, std::ptrdiff_t> > because vertex 2 doesn’t have any outgoing edge but it is required to be represented by empty entry and can’t be ignored.

Function Invocation

std::tuple< std::vector<std::size_t>, std::vector<std::ptrdiff_t> ,std::ptrdiff_t > shortestPathInfo = bellmanFordAlgorithm::shortestPath(sourceVertex, graph);

It returns a std::tuple< std::vector<std::size_t>, std::vector<std::ptrdiff_t>, std::ptrdiff_t >, where first element std::vector<std::size_t> represents parent information of all vertices and the second element std::vector<std::ptrdiff_t> represents shortest distance information of all vertices and last element std::ptrdiff_t represents the vertex where negative weight cycle is detect, if the graph has negative weight cycle otherwise it has $-1$ value.

If Bellman-Ford algorithm detects a negative weight cycle then Floyd's Cycle-Finding algorithm can be used to find the cycle as follows,

std::ptrdiff_t shortestPathInfo = floydCycleFindingAlgorithm::findCycleInAGraph(cycleDetectedAtVertex, parent);

It returns first vertex of negative weight cycle.

Example

A simple directed weighted graph as shown in Fig-1 below on the left with vertex $a$ as source vertex and the shortest path to each vertex from source vertex $a$ is shown in Fig-2 below on the right.

License

The code is licensed under the MIT License.
The tutorial document BellmanFordAlgorithm.pdf and graphAndShortestPath.svg are licensed under the CC-BY 4.0.