# 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
```rust
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):
```text
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
```rust
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):
```text
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:
```rust
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
```rust
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)
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:
```text
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):
```text
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
| Heuristic | None (h=0) | Domain-specific h(n) |
| Exploration | Uniform expansion | Directed toward target |
| Nodes Explored | More (exhaustive) | Fewer (guided) |
| Optimality | Always optimal | Optimal if h admissible |
| Use Case | Unknown target location | Known target coordinates |
```rust
// A* with zero heuristic = Dijkstra
let dijkstra_path = g.dijkstra(0, 10).expect("path exists").0;
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
```rust
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
| BFS | O(n+m) | O(n) | Unweighted graphs |
| Dijkstra | O((n+m) log n) | O(n) | Weighted, non-negative |
| A\* | O((n+m) log n) | O(n) | Weighted, with heuristic |
| All-Pairs | O(n·(n+m)) | O(n²) | All distances |
### Benchmark Results
Synthetic graph (10K nodes, 50K edges, sparse):
```text
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](./graph-algorithms.md) - Centrality and structural analysis
- [Graph Examples](../../../examples/graph_social_network.rs) - Practical usage examples
- [Graph Specification](../../../docs/specifications/complete-graph-methods-statistics-spec.md) - 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.