Bellman_Ford.H File Reference

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

#include <ah-graph-concepts.H>
#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.

Complexity

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

Example

List_Digraph<Node, Arc> g;
// ... build graph ...
List_Digraph<Node, Arc>::Node * start = g.get_first_node();
 
Bellman_Ford bf(g);
 
// Check for negative cycles and compute shortest paths from 'start'
if (bf.has_negative_cycle(start)) {
  Path<Graph> cycle = bf.build_negative_cycle();
  // handle negative cycle
} else {
  // bf.is_painted() is true, Spanning_Tree bits are set
}

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.