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)

@spec all_pairs_shortest_paths_unweighted(Yog.graph()) :: %{
  required(Yog.node_id()) => %{required(Yog.node_id()) => non_neg_integer()}
}

Computes all-pairs shortest paths in an unweighted graph using parallel BFS.

Returns a map of %{source => %{target => distance}} where distances are the number of edges in the shortest path.

Parameters

• graph - The unweighted graph to analyze

Returns

• A map from source nodes to distance maps: %{source => %{target => distance}}
• Each inner map contains distances from the source to all reachable nodes
• Distance from a node to itself is always 0
• Unreachable nodes have nil distance (note: this differs from floyd_warshall/1 which omits unreachable pairs entirely)

Complexity

• Time: O(V × (V + E)) = O(V² + VE) overall, but parallelized across CPU cores
• Space: O(V²) for the result matrix

When to Use

• Unweighted graphs only - For weighted graphs, use floyd_warshall/1 or johnson/1
• All-pairs needed - When you need distances between all node pairs
• Large graphs - Parallelization makes this efficient on multi-core systems

Algorithm

1. For each node, run BFS to compute distances to all other nodes
2. BFS from each source is parallelized using Task.async_stream
3. Results are aggregated into a nested map structure

Examples

# Simple path graph: 1-2-3-4
iex> graph = Yog.undirected()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_node(3, nil)
...> |> Yog.add_node(4, nil)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
...> |> Yog.add_edge_ensure(from: 3, to: 4, with: 1)
iex> distances = Yog.Pathfinding.all_pairs_shortest_paths_unweighted(graph)
iex> distances[1][4]
3
iex> distances[2][4]
2
iex> distances[1][1]
0

# Directed graph with unreachable nodes
iex> graph = Yog.directed()
...> |> Yog.add_node(1, nil)
...> |> Yog.add_node(2, nil)
...> |> Yog.add_node(3, nil)
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
iex> distances = Yog.Pathfinding.all_pairs_shortest_paths_unweighted(graph)
iex> distances[1][2]
1
iex> distances[3][1]
nil

See Also

• floyd_warshall/1 - For weighted graphs (all-pairs)
• johnson/5 - For sparse weighted graphs with negative weights
• distance_matrix/6 - For distances between specific points of interest only

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
8

Finds the shortest path using bidirectional BFS (unweighted graphs).

Options

• :in - The graph to search
• :from - Starting node ID
• :to - Target node ID

Solves the Chinese Postman Problem (Route Inspection) for undirected graphs.

Finds the shortest closed walk that traverses every edge at least once.

Example

iex> graph = Yog.from_edges(:undirected, [{1, 2, 1}, {2, 3, 1}, {3, 4, 1}, {4, 1, 1}])
iex> {:ok, _path, weight} = Yog.Pathfinding.chinese_postman(graph)
iex> weight
4

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).

@spec k_shortest_paths(
  Yog.Graph.t(),
  Yog.node_id(),
  Yog.node_id(),
  pos_integer(),
  keyword()
) ::
  {:ok, [Path.t()]} | :error

Finds the k shortest loopless paths from source to target using Yen's algorithm.

Options

• :with - Function to extract/transform edge weight
• :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)

Example

iex> graph = Yog.directed() |> Yog.add_node(1, nil) |> Yog.add_node(2, nil) |> Yog.add_node(3, nil) |> Yog.add_edges!([{1, 2, 1}, {2, 3, 1}, {1, 3, 2}])
iex> {:ok, paths} = Yog.Pathfinding.k_shortest_paths(graph, 1, 3, 2)
iex> length(paths)
2

@spec lca(Yog.Pathfinding.LCA.State.t(), Yog.node_id(), Yog.node_id()) ::
  {:ok, Yog.node_id()} | {:error, :node_not_found}

Returns the lowest common ancestor of two nodes.

Returns

• {:ok, node_id} - The LCA node
• {:error, :node_not_found} - One or both nodes not in the tree

@spec lca_preprocess(Yog.Graph.t(), Yog.node_id()) ::
  {:ok, Yog.Pathfinding.LCA.State.t()} | {:error, :root_not_found | :not_a_tree}

Preprocesses a tree for LCA queries using binary lifting.

Parameters

• graph - The tree graph
• root - The root node for the tree

Returns

• {:ok, LCA.State.t()} - Preprocessed state for LCA queries
• {:error, :root_not_found} - Root node not in graph
• {:error, :not_a_tree} - Graph contains a cycle or is disconnected

Example

iex> tree =
...>   Yog.undirected()
...>   |> Yog.add_node(1, nil)
...>   |> Yog.add_node(2, nil)
...>   |> Yog.add_node(3, nil)
...>   |> Yog.add_edges!([{1, 2, 1}, {1, 3, 1}])
iex> {:ok, state} = Yog.Pathfinding.lca_preprocess(tree, 1)
iex> Yog.Pathfinding.lca(state, 2, 3)
{:ok, 1}

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
8

@spec shortest_path_unweighted(Yog.graph(), Yog.node_id(), Yog.node_id()) ::
  {:ok, [Yog.node_id()]} | {:error, :no_path}

Finds the shortest path between two nodes in an unweighted graph using BFS.

This is significantly faster than Dijkstra for unweighted graphs because:

1. Uses BFS instead of Dijkstra's algorithm (no heap overhead)
2. Stops as soon as the target is found (early termination)
3. Works for both directed and undirected graphs
4. Handles nil weights or uniform weights (e.g., all weight=1)

Parameters

• graph - The unweighted graph (directed or undirected)
• source - Starting node ID
• target - Target node ID

Returns

• {:ok, [node_id]} - List of nodes representing the shortest path from source to target
• {:ok, [source]} - When source == target
• {:error, :no_path} - When target is unreachable from source

Complexity

• Time: O(V + E) worst case, but typically much less due to early termination
• Space: O(V) for the queue and visited set

Examples

# Simple path: 1-2-3
iex> graph = Yog.undirected()
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
iex> Yog.Pathfinding.shortest_path_unweighted(graph, 1, 3)
{:ok, [1, 2, 3]}

# Same source and target
iex> graph = Yog.undirected()
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
iex> Yog.Pathfinding.shortest_path_unweighted(graph, 1, 1)
{:ok, [1]}

# No path exists
iex> graph = Yog.directed()
...> |> Yog.add_node(:a, nil)
...> |> Yog.add_node(:b, nil)
iex> Yog.Pathfinding.shortest_path_unweighted(graph, :a, :b)
{:error, :no_path}

# Directed graph - respects edge direction
iex> graph = Yog.directed()
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
iex> Yog.Pathfinding.shortest_path_unweighted(graph, 1, 3)
{:ok, [1, 2, 3]}
iex> Yog.Pathfinding.shortest_path_unweighted(graph, 3, 1)
{:error, :no_path}

When to Use

• Unweighted graphs - All edges have the same cost (or nil weight)
• Single pair query - When you only need one source-target path
• Performance critical - Faster than Dijkstra for unweighted graphs

See Also

• shortest_path/1 - Dijkstra for weighted graphs
• bidirectional_unweighted/1 - Bidirectional BFS (potentially faster for large graphs)
• all_pairs_shortest_paths_unweighted/1 - When you need all-pairs distances

Single-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)

@spec tree_distance(Yog.Pathfinding.LCA.State.t(), Yog.node_id(), Yog.node_id()) ::
  {:ok, non_neg_integer()} | {:error, :node_not_found}

Calculates the tree distance (number of edges) between two nodes.

Returns

• {:ok, distance} - Number of edges between the nodes
• {:error, :node_not_found} - One or both nodes not in the tree

@spec widest_path(Yog.Graph.t(), source :: Yog.node_id(), target :: Yog.node_id()) ::
  {:ok, Path.t()} | :error

Finds the widest path (maximum capacity path) between two nodes.

The widest path maximizes the minimum edge weight along the path (the bottleneck). This is useful for network bandwidth routing, finding reliable paths, and max-min fair allocation problems.

Parameters

• graph - The graph to search
• source - Starting node ID
• target - Target node ID

Returns

• {:ok, path} - A Path.t() struct with maximum bottleneck capacity
• :error - If no path exists between the nodes

Example

# Network with bandwidths
graph = Yog.directed()
|> Yog.add_edges!([
  {:a, :b, 100},  # 100 Mbps link
  {:a, :c, 50},   # 50 Mbps link
  {:b, :d, 80},   # 80 Mbps link
  {:c, :d, 200}   # 200 Mbps link
])

{:ok, path} = Yog.Pathfinding.widest_path(graph, :a, :d)
# Path via b has bottleneck min(100, 80) = 80
# Path via c has bottleneck min(50, 200) = 50
# So widest path is a->b->d with capacity 80

Algorithm

This is a modification of Dijkstra's algorithm:

• Standard Dijkstra: distance[v] = min(distance[u] + weight(u,v))
• Widest Path: capacity[v] = max(capacity[v], min(capacity[u], weight(u,v)))

The path's "width" is the minimum edge weight along it. We want to maximize this minimum (the bottleneck capacity).

Complexity

• Time: O((V + E) log V)
• Space: O(V)

See Also

• shortest_path/1 - Standard Dijkstra for shortest paths
• Wikipedia: https://en.wikipedia.org/wiki/Widest_path_problem