Bellman-Ford shortest paths in Aleph-w (negative weights, negative-cycle detection, SPFA). More...

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <chrono>
#include <cstring>
#include <tpl_graph.H>
#include <Bellman_Ford.H>

Include dependency graph for bellman_ford_example.cc:

Classes
struct	Distance
	Distance accessor. More...

Typedefs
using	WeightedDigraph = List_Digraph< Graph_Node< string >, Graph_Arc< double > >

using	Node = WeightedDigraph::Node

using	Arc = WeightedDigraph::Arc

Functions
Node *	find_node (WeightedDigraph &g, const string &name)

void	print_graph (WeightedDigraph &g)

void	print_path (Path< WeightedDigraph > &path, WeightedDigraph &g)

template<typename Func >
double	measure_ms (Func &&f)

void	example_basic_negative_weights ()

void	example_negative_cycle ()

void	example_spfa_comparison ()

void	example_comparison_dijkstra ()

static void	usage (const char *prog)

static bool	has_flag (int argc, char argv[], const char flag)

int	main (int argc, char *argv[])

Detailed Description

Bellman-Ford shortest paths in Aleph-w (negative weights, negative-cycle detection, SPFA).

Overview

This example demonstrates Aleph-w's Bellman-Ford implementation for single-source shortest paths on directed graphs that may contain negative arc weights. It also demonstrates:

Negative-cycle detection (reachable from the source).
A queue-based relaxation strategy often referred to as SPFA (Shortest Path Faster Algorithm).

Bellman-Ford is the “safe default” when you cannot guarantee non-negative weights, and it is a key building block for Johnson's all-pairs algorithm.

Data model used by this example

Graph type: WeightedDigraph = List_Digraph<Graph_Node<string>, Graph_Arc<double>>
Node info: label/name (string)
Arc info: weight/cost (double)

Usage

# Run the full demo suite (default)
./bellman_ford_example
 
# Run the negative-cycle demo
./bellman_ford_example --negative-cycles
 
# Run the SPFA comparison demo
./bellman_ford_example --spfa
 
# Show help
./bellman_ford_example --help

If no flags are given, or if you pass no “specific” flags, the program runs all demos.

Algorithms

Standard Bellman-Ford

Bellman-Ford repeatedly relaxes all edges. In a graph with no negative cycles reachable from the source, shortest paths have at most |V|-1 edges, so |V|-1 relaxation rounds suffice.

Negative-cycle detection

After the |V|-1 rounds, if any edge can still be relaxed, there exists a negative cycle reachable from the source, and shortest paths are not well-defined (cost can be decreased indefinitely by looping).

SPFA (queue-based relaxation)

The example also shows a queue-driven approach that only relaxes outgoing edges of nodes whose distance changed. This is often faster in practice, but retains Bellman-Ford's worst-case behavior.

Complexity

Let V be the number of nodes and E the number of arcs.

Standard Bellman-Ford: O(V * E) time, O(V) extra space.
SPFA (typical): often close to O(E) on many inputs (no guarantee).
SPFA (worst case): O(V * E).

Pitfalls and edge cases

Dijkstra incompatibility: Dijkstra is invalid if any arc has negative weight.
Cycle reachability: a negative cycle that is not reachable from the chosen source does not affect shortest paths from that source.
Floating point: with double weights, comparisons can be sensitive to rounding; be careful if you adapt this to real-world numeric data.
Unreachable nodes: distances remain infinite; paths to those nodes are empty.

References / see also

Bellman_Ford.H (implementation)
dijkstra_example.cc / Dijkstra.H (faster when all weights are non-negative)
johnson_example.cc (all-pairs shortest paths using Bellman-Ford + Dijkstra)

Author: Leandro Rabindranath León

Definition in file bellman_ford_example.cc.

Typedef Documentation

◆ Arc

using Arc = WeightedDigraph::Arc

Definition at line 141 of file bellman_ford_example.cc.

◆ Node

using Node = WeightedDigraph::Node

Definition at line 140 of file bellman_ford_example.cc.

◆ WeightedDigraph

using WeightedDigraph = List_Digraph<Graph_Node<string>, Graph_Arc<double> >

Definition at line 139 of file bellman_ford_example.cc.

Function Documentation

◆ example_basic_negative_weights()

void example_basic_negative_weights ( )

Definition at line 226 of file bellman_ford_example.cc.

References Aleph::maps(), print_graph(), and print_path().

◆ example_comparison_dijkstra()

void example_comparison_dijkstra ( )

Definition at line 437 of file bellman_ford_example.cc.

References Aleph::maps().

◆ example_negative_cycle()

void example_negative_cycle ( )

Definition at line 303 of file bellman_ford_example.cc.

References Aleph::maps(), and print_graph().

◆ example_spfa_comparison()

void example_spfa_comparison ( )

Definition at line 372 of file bellman_ford_example.cc.

References Aleph::maps(), measure_ms(), N, nodes, and Aleph::to_string().

◆ find_node()

Node * find_node	(	WeightedDigraph &	g,
		const string &	name
	)

Definition at line 157 of file bellman_ford_example.cc.

◆ has_flag()

static bool has_flag	(	int	argc,
		char *	argv[],
		const char *	flag
	)

static

Definition at line 456 of file bellman_ford_example.cc.

◆ main()

int main	(	int	argc,
		char *	argv[]
	)

Definition at line 464 of file bellman_ford_example.cc.

◆ measure_ms()

template<typename Func >

double measure_ms ( Func && f )

Definition at line 214 of file bellman_ford_example.cc.

Referenced by example_spfa_comparison().

◆ print_graph()

void print_graph ( WeightedDigraph & g )

Definition at line 165 of file bellman_ford_example.cc.