yog/pathfinding/unweighted
Unweighted pathfinding algorithms for graphs where all edges have equal weight.
These algorithms use Breadth-First Search (BFS) to find paths and distances based on the number of hops between nodes.
| Algorithm | Function | Complexity | Best For |
|---|---|---|---|
| BFS Path | shortest_path/3 | O(V + E) | Single-pair unweighted paths |
| SSAD | single_source_distances/2 | O(V + E) | Distances from one node to all others |
| Unweighted APSP | all_pairs_shortest_paths/1 | O(V(V + E)) | All-pairs distances in sparse graphs |
Why Use Unweighted Algorithms?
If your graph doesn’t have custom edge weights (or if all weights are identical), Dijkstra and Floyd-Warshall are unnecessarily slow due to their use of priority queues or O(V³) matrices. BFS-based algorithms are the most efficient way to calculate hop-counts.
Comparison with Weighted Algorithms
| Feature | Unweighted (BFS) | Weighted (Dijkstra) |
|---|---|---|
| point-to-point | O(V + E) | O((V+E) log V) |
| SS/APSP | O(V(V + E)) | O(V² log V + VE) |
| Overhead | Low (simple queue) | Higher (priority queue) |
Values
pub fn all_pairs_shortest_paths(
in graph: model.Graph(n, e),
) -> dict.Dict(#(Int, Int), Int)Computes hop-count distances between all pairs of nodes in an unweighted graph.
This implementation runs a BFS from every node, which is much more efficient than Floyd-Warshall for sparse unweighted graphs.
Time Complexity: O(V(V + E))
pub fn shortest_path(
in graph: model.Graph(n, e),
from start: Int,
to goal: Int,
) -> option.Option(path.Path(Int))Finds the shortest path (minimum hops) between two nodes in an unweighted graph.
Time Complexity: O(V + E)
Example
unweighted.shortest_path(graph, from: 1, to: 5)
// => Some(Path([1, 2, 5], 2))
pub fn single_source_distances(
in graph: model.Graph(n, e),
source start: Int,
) -> dict.Dict(Int, Int)Computes the shortest distance (in hops) from a source node to all reachable nodes.
Time Complexity: O(V + E)
Example
unweighted.single_source_distances(graph, source: 1)
// => Dict([#(1, 0), #(2, 1), #(5, 2)])