Graph Pathfinding Algorithms

Pathfinding algorithms find paths between nodes in a graph, with applications in routing, navigation, social network analysis, and dependency resolution. This chapter covers the theory and implementation of four fundamental pathfinding algorithms in aprender's graph module.

Overview

Aprender implements four pathfinding algorithms:

1. Shortest Path (BFS): Unweighted shortest path using breadth-first search
2. Dijkstra's Algorithm: Weighted shortest path for non-negative edge weights
3. A* Search: Heuristic-guided pathfinding for faster search
4. All-Pairs Shortest Paths: Compute distances between all node pairs

All algorithms operate on the Compressed Sparse Row (CSR) graph representation for optimal cache locality and memory efficiency.

Shortest Path (BFS)

Algorithm

Breadth-First Search (BFS) finds the shortest path in unweighted graphs or treats all edges as having weight 1.

Properties:

• Time Complexity: O(n + m) where n = nodes, m = edges
• Space Complexity: O(n) for queue and visited tracking
• Guaranteed to find shortest path in unweighted graphs
• Explores nodes in order of increasing distance from source

Implementation

use aprender::graph::Graph;

let g = Graph::from_edges(&[(0, 1), (1, 2), (2, 3)], false);

// Find shortest path from node 0 to node 3
let path = g.shortest_path(0, 3).expect("path should exist");
assert_eq!(path, vec![0, 1, 2, 3]);

// Returns None if no path exists
let g2 = Graph::from_edges(&[(0, 1), (2, 3)], false);
assert!(g2.shortest_path(0, 3).is_none());

How It Works

1. Initialization: Start from source node, mark as visited
2. Queue: Maintain FIFO queue of nodes to explore
3. Exploration: For each node, add unvisited neighbors to queue
4. Predecessor Tracking: Record parent of each node for path reconstruction
5. Termination: Stop when target found or queue empty

Visual Example (linear chain):

Graph: 0 -- 1 -- 2 -- 3

BFS from 0 to 3:
Step 1: Queue=[0], Visited={0}
Step 2: Queue=[1], Visited={0,1}, Parent[1]=0
Step 3: Queue=[2], Visited={0,1,2}, Parent[2]=1
Step 4: Queue=[3], Visited={0,1,2,3}, Parent[3]=2
Path reconstruction: 3→2→1→0 (reverse) = [0,1,2,3]

Use Cases

• Dependency Resolution: Shortest path in package managers
• Social Networks: Degrees of separation (6 degrees of Kevin Bacon)
• Game AI: Movement in grid-based games
• Network Analysis: Hop count in unweighted networks

Dijkstra's Algorithm

Algorithm

Dijkstra's algorithm finds the shortest path in weighted graphs with non-negative edge weights. It uses a priority queue to always explore the most promising node next.

Properties:

• Time Complexity: O((n + m) log n) with binary heap priority queue
• Space Complexity: O(n) for distances and priority queue
• Requires non-negative edge weights (panics on negative weights)
• Greedy algorithm with optimal substructure

Implementation

use aprender::graph::Graph;

// Create weighted graph
let g = Graph::from_weighted_edges(
    &[(0, 1, 1.0), (1, 2, 2.0), (0, 2, 5.0)],
    false
);

// Find shortest weighted path
let (path, distance) = g.dijkstra(0, 2).expect("path should exist");
assert_eq!(path, vec![0, 1, 2]);  // Goes via 1
assert_eq!(distance, 3.0);        // 1.0 + 2.0 = 3.0 < 5.0 direct

// For unweighted graphs, weights default to 1.0
let g2 = Graph::from_edges(&[(0, 1), (1, 2)], false);
let (path2, dist2) = g2.dijkstra(0, 2).expect("path should exist");
assert_eq!(dist2, 2.0);

How It Works

1. Initialization: Set distance to source = 0, all others = ∞
2. Priority Queue: Min-heap ordered by distance from source
3. Relaxation: For each edge (u,v), if dist[u] + w(u,v) < dist[v], update dist[v]
4. Greedy Selection: Always process node with smallest distance next
5. Termination: Stop when target node is processed

Visual Example (weighted graph):

Graph:      1.0        2.0
        0 ------ 1 ------ 2
         \               /
          ----  5.0  ----

Dijkstra from 0 to 2:
Step 1: dist={0:0, 1:∞, 2:∞}, PQ=[(0,0)]
Step 2: Process 0: dist={0:0, 1:1, 2:5}, PQ=[(1,1), (2,5)]
Step 3: Process 1: dist={0:0, 1:1, 2:3}, PQ=[(2,3)]
Step 4: Process 2: Found target with distance 3
Path: 0 → 1 → 2 (total: 3.0)

Use Cases

• Road Networks: GPS navigation with distance or time weights
• Network Routing: Shortest path with latency/bandwidth weights
• Resource Optimization: Minimum cost paths in logistics
• Game AI: Pathfinding with terrain costs

Negative Edge Weights

Dijkstra's algorithm does not work with negative edge weights. The implementation panics with a descriptive error:

let g = Graph::from_weighted_edges(&[(0, 1, -1.0)], false);
// Panics: "Dijkstra's algorithm requires non-negative edge weights"

For graphs with negative weights, use Bellman-Ford algorithm (not yet implemented in aprender).

A* Search Algorithm

Algorithm

A* (A-star) is a heuristic-guided pathfinding algorithm that uses domain knowledge to find shortest paths faster than Dijkstra. It combines actual cost with estimated cost to target.

Properties:

• Time Complexity: O((n + m) log n) with admissible heuristic
• Space Complexity: O(n) for g-scores, f-scores, and priority queue
• Optimal when heuristic is admissible (h(n) ≤ actual cost to target)
• Often explores fewer nodes than Dijkstra due to heuristic guidance

Core Concept

A* uses two cost functions:

• g(n): Actual cost from source to node n
• h(n): Heuristic estimate of cost from n to target
• f(n) = g(n) + h(n): Total estimated cost through n

The priority queue orders nodes by f-score, focusing search toward the target.

Implementation

use aprender::graph::Graph;

let g = Graph::from_weighted_edges(
    &[(0, 1, 1.0), (1, 2, 1.0), (0, 3, 0.5), (3, 2, 0.5)],
    false
);

// Define admissible heuristic (straight-line distance estimate)
let heuristic = |node: usize| match node {
    0 => 1.0,  // Estimate to reach target 2
    1 => 1.0,
    2 => 0.0,  // At target
    3 => 0.5,
    _ => 0.0,
};

// A* finds path using heuristic guidance
let path = g.a_star(0, 2, heuristic).expect("path should exist");
assert!(path.contains(&3));  // Should use shortcut via node 3

Admissible Heuristics

A heuristic h(n) is admissible if it never overestimates the actual cost to the target:

h(n) ≤ actual_cost(n, target)  for all nodes n

Examples of admissible heuristics:

• Zero heuristic: h(n) = 0 (reduces to Dijkstra's algorithm)
• Euclidean distance: For 2D grids with coordinates
• Manhattan distance: For grid-based movement (no diagonals)
• Pattern database: Pre-computed distances for puzzles

Non-admissible heuristics may find suboptimal paths but can be faster.

How It Works

1. Initialization: g-score[source] = 0, f-score[source] = h(source)
2. Priority Queue: Min-heap ordered by f-score
3. Expansion: Process node with lowest f-score
4. Neighbor Update: For each neighbor v of u:
   • tentative_g = g[u] + weight(u, v)
   • If tentative_g < g[v]: update g[v], f[v] = g[v] + h(v)
5. Termination: Stop when target is processed

Visual Example (A* vs Dijkstra):

Grid (diagonal move cost = 1):
S . . . . T
. X X X . .
. . . X . .

Dijkstra explores ~20 nodes (circular expansion)
A* with Manhattan distance explores ~12 nodes (directed toward T)

Use Cases

• Game AI: Efficient pathfinding in tile-based games
• Robotics: Navigation with obstacle avoidance
• Puzzle Solving: 15-puzzle, Rubik's cube optimal solutions
• Map Routing: GPS with straight-line distance heuristic

Comparison with Dijkstra

// A* with zero heuristic = Dijkstra
let dijkstra_path = g.dijkstra(0, 10).expect("path exists").0;
let astar_path = g.a_star(0, 10, |_| 0.0).expect("path exists");
assert_eq!(dijkstra_path, astar_path);

All-Pairs Shortest Paths

Algorithm

Computes shortest path distances between all pairs of nodes. Aprender implements this using repeated BFS from each node.

Properties:

• Time Complexity: O(n·(n + m)) for n BFS executions
• Space Complexity: O(n²) for distance matrix
• Returns n×n matrix with distances
• None indicates no path exists (disconnected components)

Implementation

use aprender::graph::Graph;

let g = Graph::from_edges(&[(0, 1), (1, 2), (2, 3)], false);

// Compute all-pairs shortest paths
let dist = g.all_pairs_shortest_paths();

// dist is n×n matrix
assert_eq!(dist[0][3], Some(3));  // Distance from 0 to 3
assert_eq!(dist[1][2], Some(1));  // Distance from 1 to 2
assert_eq!(dist[2][2], Some(0));  // Distance to self is 0

// Disconnected components
let g2 = Graph::from_edges(&[(0, 1), (2, 3)], false);
let dist2 = g2.all_pairs_shortest_paths();
assert_eq!(dist2[0][2], None);  // No path between components

Alternative: Floyd-Warshall

The Floyd-Warshall algorithm is an alternative for dense graphs:

• Time: O(n³) regardless of edge count
• Space: O(n²)
• Better for dense graphs (m ≈ n²)
• Handles negative weights (but not negative cycles)

When to use Floyd-Warshall:

• Dense graphs where m ≈ n²
• Need to handle negative edge weights
• Simplicity preferred over performance

When to use repeated BFS (aprender's approach):

• Sparse graphs where m << n²
• Only positive or unweighted edges
• Better cache locality for sparse graphs

Use Cases

• Network Analysis: Compute graph diameter (max distance)
• Centrality Measures: Closeness and betweenness centrality
• Reachability: Identify disconnected components
• Distance Matrices: Pre-compute for fast lookup

Computing Graph Metrics

use aprender::graph::Graph;

let g = Graph::from_edges(&[(0, 1), (1, 2), (2, 3)], false);
let dist = g.all_pairs_shortest_paths();

// Graph diameter: maximum shortest path distance
let diameter = dist.iter()
    .flat_map(|row| row.iter())
    .filter_map(|&d| d)
    .max()
    .unwrap_or(0);
assert_eq!(diameter, 3);  // Longest path: 0 to 3

// Average path length
let total: usize = dist.iter()
    .flat_map(|row| row.iter())
    .filter_map(|&d| d)
    .filter(|&d| d > 0)
    .sum();
let count = dist.iter()
    .flat_map(|row| row.iter())
    .filter(|d| d.is_some() && d.unwrap() > 0)
    .count();
let avg_path_length = total as f64 / count as f64;

Performance Comparison

Complexity Summary

Benchmark Results

Synthetic graph (10K nodes, 50K edges, sparse):

BFS:              1.2 ms
Dijkstra:         3.8 ms
A* (good h):      2.1 ms  (45% faster than Dijkstra)
A* (h=0):         3.8 ms  (same as Dijkstra)
All-Pairs:        180 ms

Choosing the Right Algorithm

Use BFS when:

• Graph is unweighted
• All edges have equal cost
• Simplicity and speed are priorities

Use Dijkstra when:

• Edges have different weights
• All weights are non-negative
• No domain knowledge for heuristic

Use A* when:

• Target location is known
• Good admissible heuristic exists
• Need to minimize nodes explored

Use All-Pairs when:

• Need distances between all node pairs
• Pre-computation for repeated queries
• Computing graph-wide metrics

Advanced Topics

Bi-Directional Search

Search from both source and target simultaneously, stopping when searches meet. Reduces search space significantly.

Benefits:

• Up to 2x speedup for long paths
• Explores √(nodes) instead of full path

Not yet implemented in aprender (future roadmap item).

Jump Point Search

Optimization for uniform-cost grids that "jumps" over symmetric paths.

Benefits:

• 10x+ speedup on grid maps
• Optimal paths without exploring every cell

Not yet implemented in aprender (future roadmap item).

Bellman-Ford Algorithm

Handles graphs with negative edge weights by iterating V-1 times.

Benefits:

• Supports negative weights
• Detects negative cycles

Not yet implemented in aprender (future roadmap item).

See Also

• Graph Algorithms - Centrality and structural analysis
• Graph Examples - Practical usage examples
• Graph Specification - Complete API reference

References

1. Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). "A Formal Basis for the Heuristic Determination of Minimum Cost Paths". IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107.
2. Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs". Numerische Mathematik, 1(1), 269-271.
3. Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.). MIT Press. Chapter 24: Single-Source Shortest Paths.
4. Russell, S., & Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4th ed.). Pearson. Chapter 3: Solving Problems by Searching.