Bellman Ford’s Algorithm

The Bell man Ford’s algorithm is a single source graph search algorithm which help us to find the shortest path between a source vertex and any other vertex in a give graph. We can use it in both weighted and unweighted graphs. This algorithm is slower than Dijkstra’s algorithm and it can also use negative edge weight.

Algorithm

1: First we Initialize all vertices v in a distance array dist[] as INFINITY.

2: Then we pick a random vertex as vertex 0 and assign dist[0] =0.

3: Then iteratively update the minimum distance to each node (dist[v]) by comparing it with the sum of the distance from the source node (dist[u]) and the edge weight (weight) N-1 times.

4: To identify the presence of negative edge cycles, with the help of following cases do one more round of edge relaxation.

• We can say that a negative cycle exists if for any edge uv the sum of distance from the source node (dist[u]) and the edge weight (weight) is less than the current distance to the largest node(dist[v])
• It indicates the absence of negative edge cycle if none of the edges satisfies case1.

Example: Bellman ford detecting negative edge cycle in a graph.

Consider the Graph G:

Step 1:

Step 2:

Step 3:

Step 4:

Step 5:

Outcome: The graph contains a negative cycle in the path from node D to node F and then to node E.

In between sending and receiving data packets from the sender to the receiver, it will go through many routers and subnets. So as a part of increasing the efficiency in routing the data packets and decreasing the traffic, we must find the shortest path. In this article, we are discussing the shortest path algorithms.