Dial.H File Reference

Dial's algorithm for shortest paths with small integer weights. More...

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

Include dependency graph for Dial.H:

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

Go to the source code of this file.

Classes
class	Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >
	Dial's algorithm for shortest paths with integer weights. More...
struct	Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::Node_Info
class	Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::Dial_Init_Guard
	RAII guard for Dial initialization and cleanup. More...

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

Macros
#define	DIAL_INFO(p)   (static_cast<Node_Info *>(NODE_COOKIE(p)))
#define	DIAL_DIST(p)   (DIAL_INFO(p)->dist)
#define	DIAL_PARENT(p)   (DIAL_INFO(p)->parent)
#define	DIAL_PARC(p)   (DIAL_INFO(p)->parent_arc)

Detailed Description

Dial's algorithm for shortest paths with small integer weights.

Implements Dial's algorithm, a bucket-based variant of Dijkstra's algorithm optimized for graphs with non-negative integer edge weights. It achieves O(V + E + C) time complexity, where C is the maximum edge weight times the number of vertices.

How it works

Instead of a priority queue, Dial's algorithm uses an array of buckets indexed by distance. Each bucket holds the nodes at that distance from the source. The algorithm scans buckets in order, processing all nodes in the current bucket before moving to the next.

This is especially efficient when the maximum edge weight C is small, as the number of buckets is proportional to V * C.

Complexity

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

where C is the maximum edge weight.

Usage Example

// Graph with small integer 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, 3);
g.insert_arc(n1, n2, 2);
 
Dial_Min_Paths<decltype(g)> dial;
Path<decltype(g)> path(g);
int dist = dial(g, n0, n2, path);  // dist == 5

See also

Dijkstra.H For general non-negative weights (heap-based)

Zero_One_BFS.H For 0/1 weights only

Author

Leandro Rabindranath Leon

Definition in file Dial.H.

Macro Definition Documentation

DIAL_DIST

#define DIAL_DIST

(

p

)

(DIAL_INFO(p)->dist)

Definition at line 156 of file Dial.H.

DIAL_INFO

#define DIAL_INFO

(

p

)

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

Definition at line 155 of file Dial.H.

DIAL_PARC

#define DIAL_PARC

(

p

)

(DIAL_INFO(p)->parent_arc)

Definition at line 158 of file Dial.H.

DIAL_PARENT

#define DIAL_PARENT

(

p

)

(DIAL_INFO(p)->parent)

Definition at line 157 of file Dial.H.