FREE E LEARNING PLATFORM
☰ HOMEEXCEPTIONSOOPSJVMINTRO
SYLLABUS TUTORIALS FORUM
 

Bellman-Ford Algorithm



Introduction

Bellman-Ford Algorithm is a shortest path algorithm used to find the minimum distance from a single source vertex to all other vertices in a weighted graph. Unlike Dijkstra's Algorithm, Bellman-Ford can handle negative edge weights and can also detect the presence of negative weight cycles in a graph.

The algorithm repeatedly relaxes all edges of the graph until the shortest distances are obtained. If a shorter path is still found after performing (V − 1) iterations, the graph contains a negative weight cycle.

Why Do We Need Bellman-Ford Algorithm?

Many real-world problems involve graphs containing negative edge weights. Dijkstra's Algorithm cannot solve such problems correctly, whereas Bellman-Ford Algorithm provides the correct shortest path and also detects negative weight cycles.

Application Purpose
Computer Networks Finding shortest paths with varying link costs.
Currency Exchange Detecting profitable exchange cycles.
Transportation Networks Finding minimum travel cost when discounts are available.
Routing Protocols Distance Vector Routing (RIP).
Financial Systems Detecting arbitrage opportunities.

Prerequisites

Concept Description
Graph A collection of vertices connected by weighted edges.
Weighted Graph Each edge has an associated cost.
Edge Relaxation Updating the shortest distance if a better path is found.
Negative Edge Weight An edge having a value less than zero.

Working Principle

Bellman-Ford Algorithm starts by assigning a distance of 0 to the source vertex and ∞ (Infinity) to all other vertices. It then relaxes every edge in the graph repeatedly for (V − 1) iterations. During each iteration, if a shorter path is found, the corresponding distance is updated.

After completing all iterations, one additional pass is performed. If any distance can still be reduced, the graph contains a negative weight cycle.

Illustration


Source Vertex : A

Iteration 1

A → B = 4

A → C = 5

Iteration 2

B → D = 2

C → D = 1

Shortest Distance Updated

Repeat until (V−1) iterations

Finally Check

Negative Cycle ?

Yes / No

Figure 1 : Working of Bellman-Ford Algorithm

Step-by-Step Example

Iteration Updated Vertex Distance
1 A 0
2 B 4
3 C 5
4 D 6

Bellman-Ford Algorithm

BellmanFord(Graph, Source) Step 1 : Assign distance 0 to the source vertex. Step 2 : Assign infinite distance to all other vertices. Step 3 : Relax every edge of the graph. Step 4 : Repeat Step 3 exactly (V − 1) times. Step 5 : Perform one more relaxation. Step 6 : If any distance is updated, a Negative Weight Cycle exists. Step 7 : Otherwise, display the shortest distance from the source to every vertex.

Complexity Analysis

Operation Time Complexity Remarks
Edge Relaxation O(V × E) Each edge is relaxed (V − 1) times.
Negative Cycle Detection O(E) One additional traversal of all edges.
Total Time Complexity O(V × E) Suitable for graphs containing negative edge weights.
Space Complexity O(V) Stores distance and predecessor arrays.

Advantages of Bellman-Ford Algorithm

  • Works correctly even when the graph contains negative edge weights.
  • Can detect negative weight cycles.
  • Simple to understand and implement.
  • Computes the shortest path from a single source vertex.
  • Suitable for routing and network optimization problems.

Limitations of Bellman-Ford Algorithm

  • Slower than Dijkstra's Algorithm.
  • Not suitable for very large graphs where faster algorithms are available.
  • Requires repeated relaxation of all edges.
  • Cannot produce a valid shortest path if a negative weight cycle exists.

Applications of Bellman-Ford Algorithm

Application Description
Routing Protocols Used in Distance Vector Routing (RIP).
Computer Networks Finding shortest communication paths.
Currency Exchange Detecting arbitrage opportunities using negative cycles.
Transportation Systems Finding minimum travel cost with discounts.
Financial Networks Optimizing investment and exchange paths.

Bellman-Ford Algorithm vs Dijkstra's Algorithm

Bellman-Ford Algorithm Dijkstra's Algorithm
Supports negative edge weights. Supports only non-negative edge weights.
Can detect negative weight cycles. Cannot detect negative weight cycles.
Time Complexity: O(V × E) Time Complexity: O((V + E) log V)
Uses repeated edge relaxation. Uses Greedy selection with Priority Queue.
Suitable when negative weights are present. Suitable for graphs with non-negative weights.

Important Points

  • Bellman-Ford Algorithm computes the shortest path from a single source vertex.
  • It supports graphs containing negative edge weights.
  • It detects the presence of negative weight cycles.
  • The algorithm relaxes every edge exactly (V − 1) times.
  • Its time complexity is O(V × E).
  • It is widely used in routing protocols and network optimization.

Exam Tip

In AKTU examinations, students are frequently asked to compare Bellman-Ford Algorithm with Dijkstra's Algorithm. Remember that Bellman-Ford supports negative edge weights and can detect negative weight cycles, whereas Dijkstra's Algorithm cannot.

Summary

Bellman-Ford Algorithm is an important shortest path algorithm that computes the minimum distance from a single source vertex to all other vertices. Its major advantage is that it works correctly even when negative edge weights are present and it can detect negative weight cycles. Although it is slower than Dijkstra's Algorithm, it is preferred whenever graphs contain negative edge weights.







Copyright 2020 by Noidatut. All Rights Reserved.

Noidatut.com