Bellman_Ford.H File Reference

Bellman-Ford algorithm for single-source shortest paths. More...

#include <type_traits>
#include <limits>
#include <vector>
#include <tpl_dynListQueue.H>
#include <tpl_dynSetTree.H>
#include <tpl_graph_utils.H>
#include <Tarjan.H>
#include <ah-errors.H>
#include <ah_init_guard.H>
#include <cookie_guard.H>

Include dependency graph for Bellman_Ford.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >
	Bellman-Ford algorithm for shortest paths with negative weights. More...
struct	Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::Sni
struct	Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::Ni
struct	Aleph::Bellman_Ford_Negative_Cycle< GT, Distance, Ait, NAit, SA >
	Detects if a negative cycle exists and eventually computes it. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Detailed Description

Bellman-Ford algorithm for single-source shortest paths.

This file implements the Bellman-Ford algorithm, which computes the shortest paths from a single source vertex to all other vertices in a weighted directed graph. Unlike Dijkstra's algorithm, Bellman-Ford can handle graphs with negative edge weights and can detect negative-weight cycles.

Algorithms Provided

• Standard Bellman-Ford: O(V*E) time complexity
• SPFA (Shortest Path Faster Algorithm): Queue-based optimization that is often faster in practice on sparse graphs

Key Features

• Handles negative edge weights
• Detects negative-weight cycles
• Can return the negative cycle as a path
• Supports both painted (in-place) and separate tree construction

Complexity

Operation	Time	Space
Standard	O(V*E)	O(V)
SPFA (avg)	O(E)	O(V)
SPFA (worst)	O(V*E)	O(V)

Usage Example

List_Digraph<Node, Arc> g;
// ... build graph ...
 
Bellman_Ford<List_Digraph<Node, Arc>> bf(g);
 
// Check for negative cycles and compute shortest paths
if (bf.has_negative_cycle(start_node)) {
  Path<Graph> cycle = bf.build_negative_cycle();
  // handle negative cycle
} else {
  // Use the shortest path tree
}

See also

Dijkstra.H For graphs without negative weights (more efficient)

Floyd_Warshall.H For all-pairs shortest paths

Johnson.H For all-pairs with negative weights (uses Bellman-Ford)

Author

Leandro Rabindranath León

Definition in file Bellman_Ford.H.