Zero_One_BFS.H File Reference

0-1 BFS shortest path algorithm. More...

#include <limits>
#include <type_traits>
#include <tpl_dynDlist.H>
#include <tpl_graph_utils.H>
#include <ah-errors.H>

Include dependency graph for Zero_One_BFS.H:

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

Go to the source code of this file.

Classes
class	Aleph::Zero_One_BFS< GT, Distance, Itor, SA >
	0-1 BFS algorithm for shortest paths in graphs with 0/1 weights. More...
struct	Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::Node_Info
struct	Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::Painted_Info
	Stores parent and distance after painting for O(1) access. More...
class	Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::ZOB_Init_Guard
	RAII guard for Zero_One_BFS initialization and cleanup. More...

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

Macros
#define	ZOB_INFO(p)   (static_cast<Node_Info *>(NODE_COOKIE(p)))
#define	ZOB_PNTD(p)   (static_cast<Painted_Info *>(NODE_COOKIE(p)))
#define	ZOB_DIST(p)   (ZOB_INFO(p)->dist)
#define	ZOB_PARENT(p)   (ZOB_INFO(p)->parent)
#define	ZOB_PARENT_ARC(p)   (ZOB_INFO(p)->parent_arc)

Detailed Description

0-1 BFS shortest path algorithm.

Implements the 0-1 BFS algorithm for finding shortest paths in graphs where all edge weights are either 0 or 1. Uses a double-ended queue (deque) to achieve O(V + E) time complexity, which is optimal for this class of graphs.

How it works

Instead of a priority queue (as in Dijkstra), 0-1 BFS uses a deque:

• When traversing a 0-weight edge, the target node is pushed to the front of the deque (it has the same distance as the current node).
• When traversing a 1-weight edge, the target node is pushed to the back of the deque (it has distance + 1).

This maintains the invariant that the deque is sorted by distance, so the front always contains the node with minimum distance.

Complexity

Operation	Time	Space
Single-target	O(V + E)	O(V)
All-targets	O(V + E)	O(V)

Usage Example

// Graph with 0/1 edge weights
List_Graph<Graph_Node<int>, Graph_Arc<int>> g;
auto* n0 = g.insert_node(0);
auto* n1 = g.insert_node(1);
auto* n2 = g.insert_node(2);
g.insert_arc(n0, n1, 0);  // free edge
g.insert_arc(n1, n2, 1);  // cost-1 edge
 
Zero_One_BFS<decltype(g)> bfs01;
Path<decltype(g)> path(g);
int dist = bfs01(g, n0, n2, path);  // dist == 1

See also

Dijkstra.H For general non-negative weights

Dial.H For small integer weights

tpl_find_path.H For unweighted BFS

Author

Leandro Rabindranath Leon

Definition in file Zero_One_BFS.H.

Macro Definition Documentation

ZOB_DIST

#define ZOB_DIST

(

p

)

(ZOB_INFO(p)->dist)

Definition at line 167 of file Zero_One_BFS.H.

ZOB_INFO

#define ZOB_INFO

(

p

)

(static_cast<Node_Info *>(NODE_COOKIE(p)))

Definition at line 165 of file Zero_One_BFS.H.

ZOB_PARENT

#define ZOB_PARENT

(

p

)

(ZOB_INFO(p)->parent)

Definition at line 168 of file Zero_One_BFS.H.

ZOB_PARENT_ARC

#define ZOB_PARENT_ARC

(

p

)

(ZOB_INFO(p)->parent_arc)

Definition at line 169 of file Zero_One_BFS.H.

ZOB_PNTD

#define ZOB_PNTD

(

p

)

(static_cast<Painted_Info *>(NODE_COOKIE(p)))

Definition at line 166 of file Zero_One_BFS.H.