dijkstra_example.cc File Reference

Dijkstra shortest paths in Aleph-w (single path, shortest-path tree, and heap trade-offs). More...

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <chrono>
#include <random>
#include <limits>
#include <tpl_graph.H>
#include <Dijkstra.H>

Include dependency graph for dijkstra_example.cc:

Go to the source code of this file.

Classes
struct	RoadDistance
	Distance accessor functor for Dijkstra algorithm. More...

Typedefs
using	CityNode = Graph_Node< string >
	Node type: city name.
using	RoadArc = Graph_Arc< double >
	Arc type: distance in km.
using	CityGraph = List_Digraph< CityNode, RoadArc >
	Graph type: directed graph of cities connected by roads.

Functions
CityGraph	build_city_graph (vector< CityGraph::Node * > &nodes)
	Build a sample graph representing a city road network.
CityGraph	build_random_graph (int num_nodes, double edge_probability, double max_weight, unsigned seed=42)
	Build a random graph for performance testing.
void	print_graph (CityGraph &g)
	Print the graph structure.
void	print_path_detailed (CityGraph &g, Path< CityGraph > &path)
	Print a path with detailed step-by-step information.
template<typename Func >
double	measure_time_ms (Func &&f)
int	main ()

Detailed Description

Dijkstra shortest paths in Aleph-w (single path, shortest-path tree, and heap trade-offs).

Overview

This example demonstrates how to compute shortest paths with Aleph-w's Dijkstra_Min_Paths on a weighted graph with non-negative arc weights. It focuses on two common usage modes:

• Single-destination query: compute one shortest path from a source to a destination.
• Many queries from one source: compute a shortest-paths tree once and then query multiple destinations efficiently.

It also compares two priority-queue backends used internally by Dijkstra: ArcHeap (binary heap) vs ArcFibonacciHeap.

Data model used by this example

• Graph type: CityGraph = List_Digraph<Graph_Node<string>, Graph_Arc<double>>
• Node info: city name (string)
• Arc info: distance in km (double)

Note: The demo builds bidirectional roads by inserting arcs in both directions, even though the container type is a directed graph.

Usage

./dijkstra_example

This example has no command-line options; all parameters (graph sizes, densities) are hard-coded.

Algorithms and Aleph-w API

• Single shortest path:
  • find_min_path(g, src, dst, path) computes a shortest path and writes it into path.
• Shortest-paths tree (many queries):
  • compute_min_paths_tree(g, src, tree) builds an explicit shortest-path tree graph.
  • paint_min_paths_tree(g, src) marks the original graph so you can query later.
  • get_min_path(tree, dst, path) extracts the path to dst from a previously built tree.
  • get_min_path(dst, path) extracts the path to dst after paint_min_paths_tree().

Complexity

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

• **Binary heap (ArcHeap)**: O((V + E) log V)
• **Fibonacci heap (ArcFibonacciHeap)**: O(E + V log V) (amortized)

Notes:

• Fibonacci heaps can win on dense graphs due to cheaper decrease-key operations, but have higher constant factors.
• In practice, binary heaps are often the default choice.

Pitfalls and edge cases

• Negative weights: Dijkstra is invalid if any arc weight is negative.
• Disconnected graphs: unreachable nodes will not appear in the computed tree.
• Source==destination: this example documents Aleph-w's observed behavior where find_min_path(g, s, s, path) may return Inf and an empty path; handle the trivial case explicitly if you need distance 0 and path [s].
• Directed vs undirected modeling: for undirected graphs you must insert both directions or use an undirected graph container.

References / see also

• Dijkstra.H (implementation)
• bellman_ford_example.cc / Bellman_Ford.H (negative weights)
• johnson_example.cc (all-pairs shortest paths with negative weights but no negative cycles)
• astar_example.cc / AStar.H (the heuristic-guided shortest path)

Author

Leandro Rabindranath León

Definition in file dijkstra_example.cc.

Typedef Documentation

CityGraph

using CityGraph = List_Digraph<CityNode, RoadArc>

Graph type: directed graph of cities connected by roads.

Definition at line 136 of file dijkstra_example.cc.

CityNode

using CityNode = Graph_Node<string>

Node type: city name.

Definition at line 130 of file dijkstra_example.cc.

RoadArc

using RoadArc = Graph_Arc<double>

Arc type: distance in km.

Definition at line 133 of file dijkstra_example.cc.

Function Documentation

build_city_graph()

CityGraph build_city_graph

(

vector< CityGraph::Node * > &

nodes

)

Build a sample graph representing a city road network.

Creates the following network:

Alpha ──100── Beta ──150── Gamma
  │           │            │
 200         50          100
  │           │            │
Delta ──80── Epsilon ─120─ Zeta
  │                        │
 300                      90
  │                        │
 Eta ────────250──────── Theta

Parameters

[out]

nodes

Vector to store node pointers for later reference

Returns

The constructed graph

Definition at line 184 of file dijkstra_example.cc.

References Aleph::maps(), and nodes.

Referenced by main().

build_random_graph()

CityGraph build_random_graph	(	int	num_nodes,
		double	edge_probability,
		double	max_weight,
		unsigned	seed = 42
	)

Build a random graph for performance testing.

Parameters

num_nodes	Number of nodes
edge_probability	Probability of edge between any two nodes (0.0 to 1.0)
max_weight	Maximum edge weight
seed	Random seed for reproducibility

Returns

The constructed graph

Definition at line 228 of file dijkstra_example.cc.

References Aleph::maps(), nodes, num_nodes, rng, Aleph::to_string(), and w.

Referenced by main().

main()

int main

(

)

Definition at line 349 of file dijkstra_example.cc.

References build_city_graph(), build_random_graph(), Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::compute_min_paths_tree(), Aleph::maps(), measure_time_ms(), nodes, print_graph(), print_path_detailed(), and Aleph::Path< GT >::size().

measure_time_ms()

template<typename Func >

double measure_time_ms

(

Func &&

f

)

Definition at line 337 of file dijkstra_example.cc.

Referenced by main().

print_graph()

void print_graph

(

CityGraph &

g

)

Print the graph structure.

Definition at line 262 of file dijkstra_example.cc.

References Aleph::maps().

Referenced by main().

print_path_detailed()

void print_path_detailed	(	CityGraph &	g,
		Path< CityGraph > &	path
	)

Print a path with detailed step-by-step information.

Definition at line 294 of file dijkstra_example.cc.

References Aleph::Path< GT >::for_each_arc(), Aleph::Path< GT >::for_each_node(), Aleph::maps(), and Aleph::Path< GT >::size().

Referenced by main().