Unified facade for pathfinding algorithms.
This module provides a single entry point for all pathfinding and distance computation algorithms. Each function delegates to a specialized submodule.
Submodules
Yog.Pathfinding.Dijkstra— Single-source shortest paths (non-negative weights)Yog.Pathfinding.AStar— Heuristic-guided shortest pathsYog.Pathfinding.BellmanFord— Shortest paths with negative weights, cycle detectionYog.Pathfinding.Bidirectional— Bidirectional BFS/Dijkstra for faster convergenceYog.Pathfinding.FloydWarshall— All-pairs shortest paths (dense graphs)Yog.Pathfinding.Johnson— All-pairs shortest paths (sparse graphs, negative weights)Yog.Pathfinding.Matrix— Distance matrix computationYog.Pathfinding.Path— Path struct for representing results
Algorithm Selection Guide
| Algorithm | Use When | Time Complexity |
|---|---|---|
| Dijkstra | Non-negative weights, single pair | O((V+E) log V) |
| A* | Non-negative weights + good heuristic | O((V+E) log V) |
| Bellman-Ford | Negative weights OR cycle detection | O(VE) |
| Bidirectional | Large graphs, unweighted or uniform weights | O((V+E) log V) |
| Floyd-Warshall | All-pairs, dense graphs | O(V³) |
| Johnson's | All-pairs, sparse graphs, negative weights | O(V² log V + VE) |
Summary
Functions
Finds the shortest path using A* search with a heuristic.
Alias for a_star/1.
Finds the shortest path using Bellman-Ford (supports negative weights).
Finds the shortest path using bidirectional Dijkstra.
Finds the shortest path using bidirectional BFS (unweighted graphs).
Detects negative cycles in the graph via Floyd-Warshall.
Computes a distance matrix between specified points of interest.
Computes all-pairs shortest paths using Floyd-Warshall.
Computes all-pairs shortest paths using Johnson's algorithm.
Finds the shortest path between two nodes using Dijkstra's algorithm.
Single-source distances from a node to all reachable nodes (Dijkstra).
Functions
Finds the shortest path using A* search with a heuristic.
Options
:in- The graph to search:from- Starting node ID:to- Target node ID:zero- Zero value for weights (default: 0):add- Addition function for weights (default: &Kernel.+/2):compare- Comparison function for weights (default: &Yog.Utils.compare/2):heuristic- Heuristic function(node, goal) -> weight(Mandatory)
Alias for a_star/1.
Finds the shortest path using Bellman-Ford (supports negative weights).
Returns {:error, :negative_cycle} if a negative cycle is reachable.
Options
:in- The graph to search:from- Starting node ID:to- Target node ID:zero- Identity value for weights (default: 0):add- Addition function (default: &Kernel.+/2):compare- Comparison function (default: &Yog.Utils.compare/2)
Finds the shortest path using bidirectional Dijkstra.
Options
:in- The graph to search:from- Starting node ID:to- Target node ID:zero- Zero value for weights (default: 0):add- Addition function (default: &Kernel.+/2):compare- Comparison function (default: &Yog.Utils.compare/2)
Example
iex> {:ok, graph} = Yog.directed()
...> |> Yog.add_node(1, "A")
...> |> Yog.add_node(2, "B")
...> |> Yog.add_node(3, "C")
...> |> Yog.add_edges([{1, 2, 5}, {2, 3, 3}, {1, 3, 10}])
iex> {:ok, path} = Yog.Pathfinding.bidirectional(
...> in: graph, from: 1, to: 3
...> )
iex> path.weight
8Finds the shortest path using bidirectional BFS (unweighted graphs).
Options
:in- The graph to search:from- Starting node ID:to- Target node ID
Detects negative cycles in the graph via Floyd-Warshall.
Computes a distance matrix between specified points of interest.
Uses Dijkstra from each point to compute pairwise distances.
Computes all-pairs shortest paths using Floyd-Warshall.
Options
:in- The graph:zero- Identity element (default: 0):add- Addition function (default: &Kernel.+/2):compare- Comparison function (default: &Yog.Utils.compare/2)
Computes all-pairs shortest paths using Johnson's algorithm.
More efficient than Floyd-Warshall for sparse graphs. Supports negative edge weights (but not negative cycles).
Finds the shortest path between two nodes using Dijkstra's algorithm.
Options
:in- The graph to search:from- Starting node ID:to- Target node ID:zero- Zero value for weights (default: 0):add- Addition function for weights (default: &Kernel.+/2):compare- Comparison function for weights (:lt, :eq, :gt) (default: &Yog.Utils.compare/2)
Example
iex> {:ok, graph} = Yog.directed()
...> |> Yog.add_node(1, "A")
...> |> Yog.add_node(2, "B")
...> |> Yog.add_node(3, "C")
...> |> Yog.add_edges([{1, 2, 5}, {2, 3, 3}, {1, 3, 10}])
iex> {:ok, path} = Yog.Pathfinding.shortest_path(
...> in: graph, from: 1, to: 3
...> )
iex> path.weight
8Single-source distances from a node to all reachable nodes (Dijkstra).
Options
:in- The graph:from- Source node:zero- Zero value (default: 0):add- Addition function (default: &Kernel.+/2):compare- Comparison function (default: &Yog.Utils.compare/2)