Graph AlgorithmsAdvanced

Bellman-Ford Algorithm

Single-source shortest path algorithm that handles negative weights and detects negative cycles. Relaxes all edges V-1 times to guarantee correct distances even with negative weights. Essential for currency arbitrage detection, network routing with varied costs, and situations where Dijkstra's algorithm fails. Trades speed for flexibility.

#graph#shortest-path#negative-weights#dynamic-programming

Complexity Analysis

Time (Average)

O(V × E)

Expected case performance

Space

O(V)

Memory requirements

Time (Best)

O(V × E)

Best case performance

Time (Worst)

O(V × E)

Worst case performance

📚 CLRS Reference

Introduction to Algorithms•Chapter 24•Section 24.1

Implementation

Related Algorithms

View all in Graph Algorithms

Breadth-First Search (BFS)

Intermediate

Explores a graph level by level, visiting all vertices at the current depth before moving deeper. Uses a queue and is ideal for finding shortest paths in unweighted graphs. Applications include maze solving, social network analysis, and finding connections between nodes.

Depth-First Search (DFS)

Intermediate

Explores a graph by going as deep as possible along each path before backtracking. Implemented using a stack or recursion, making it natural for recursive problems. Used for pathfinding, cycle detection, topological sorting, and maze generation.

Dijkstra's Algorithm

Advanced

Finds the shortest paths from a single source vertex to all other vertices in a weighted graph. Powers GPS navigation systems and network routing protocols. Works efficiently with non-negative edge weights using a greedy approach with a priority queue.

Back to Graph Algorithms