We can’t use Dijkstra algorithm to find the shortest path in a graph if there are any negative weights in the graph. The Bellman Ford algorithm is capable of:
– find the shortest path in graphs with negative edge weights
– answer the question: is there a negative cycle (edges are connected in such a way that the sum of their weights has a negative value) in the graph.
To find the shortest path, the Bellman-Ford algorithm uses a mathematical approach called the Principle of Relaxation:
– to find the shortest path it’s necessary to apply relaxation V-1 times, where V – count of vertices (nodes)
– if we apply the V‘th time of “relaxation” and any short path is shortened, then there is a negative cycle in graph.
The following should be implemented in code:
- introduce a new distance array to store the current shortest distance from the starting point to the node with a number equal to the index of the distance array
- fill this array with maximum integer values
- execute the following steps V-1 times the relaxation procedure:
– take each edge with a start node and an end node
– if the distance to the start node plus the weight of the edge (new distance) does no exceed the distance to the end node, then put the new distance to the end node in the distance array - check for negative weighted cycles:
– repeat relaxation 1 time more
– if any distance has reduced, there is a negative cycle in the graph.
Time complexity: O(V * E)
Space complexity: O(V)
import java.util.Arrays;
public class ImplementBellmanFordAlgorithm {
static void BellmanFord(int[][] graph, int nodes, int edges, int src) {
var distance = new int[nodes];
Arrays.fill(distance, Integer.MAX_VALUE);
distance[src] = 0;
for (var i = 0; i < nodes - 1; i++) {
for (var j = 0; j < edges; j++) {
var node1 = graph[j][0];
var node2 = graph[j][1];
var weight12 = graph[j][2];
if (distance[node1] != Integer.MAX_VALUE
&& (distance[node1] + weight12 < distance[node2])) {
distance[node2] = distance[node1] + weight12;
}
}
}
for (var i = 0; i < edges; i++) {
var node1 = graph[i][0];
var node2 = graph[i][1];
var weight12 = graph[i][2];
if (distance[node1] != Integer.MAX_VALUE && distance[node1] + weight12 < distance[node2]) {
System.out.println("Graph contains negative weight cycle");
break;
}
}
System.out.println("Vertex Distance from Source");
for (var i = 0; i < nodes; i++) {
System.out.println(i + "\t\t" + distance[i]);
}
}
public static void main(String[] args) {
var vertices = 5;
var edges = 8;
var graph = new int[][]{
{0, 1, -1},
{0, 2, 4},
{1, 2, 3},
{1, 3, 2},
{1, 4, 2},
{3, 2, 5},
{3, 1, 1},
{4, 3, -3}
};
BellmanFord(graph, vertices, edges, 0);
}
}