Dijkstra's algorithm for single-source shortest paths.
Dijkstra's algorithm finds the shortest path from a source node to all other reachable nodes in a graph with non-negative edge weights.
Algorithm Characteristics
- Time Complexity: O((V + E) log V) with a binary heap
- Space Complexity: O(V)
- Requirements: Non-negative edge weights
- Optimality: Guaranteed optimal for graphs with non-negative weights
When to Use
- When all edge weights are non-negative
- For single-source shortest path problems
- When you need paths to all nodes from a source
- As a baseline comparison for other algorithms
Examples
# Find shortest path between two nodes
graph = Yog.directed()
|> Yog.add_node(:a, nil)
|> Yog.add_node(:b, nil)
|> Yog.add_node(:c, nil)
|> Yog.add_edge!(:a, :b, 4)
|> Yog.add_edge!(:b, :c, 1)
compare = &Yog.Utils.compare/2
Dijkstra.shortest_path(graph, :a, :c, 0, &(&1 + &2), compare)
#=> {:some, {:path, [:a, :b, :c], 5}}
# Find all distances from a source
Dijkstra.single_source_distances(graph, :a, 0, &(&1 + &2), compare)
#=> %{:a => 0, :b => 4, :c => 5}Summary
Types
Result type for shortest path queries
Functions
Implicit Dijkstra using keyword options.
Run Dijkstra on an implicit (generated) graph.
Implicit Dijkstra with key function using keyword options.
Implicit Dijkstra with a key function for visited state tracking.
Find shortest path using keyword options.
Find the shortest path between two nodes using custom numeric operations.
Single-source distances using keyword options.
single_source_distances(graph, from, zero \\ 0, add \\ &Kernel.+/2, compare \\ &Yog.Utils.compare/2)
Calculate single-source shortest distances to all reachable nodes.
Types
@type path_result() :: {:ok, Yog.Pathfinding.Path.t()} | :error
Result type for shortest path queries
Functions
Implicit Dijkstra using keyword options.
Options
:from- Starting state:successors_with_cost- Function returning neighbors with costs:is_goal- Function to check if a state is the goal:zero- Identity value for the weight type:add- Function to add two weights:compare- Function to compare weights
Examples
Pathfinding.implicit_dijkstra(
from: 1,
successors_with_cost: fn n -> [{n+1, 1}] end,
is_goal: fn n -> n == 10 end,
zero: 0,
add: &(&1 + &2),
compare: &Yog.Utils.compare/2
)@spec implicit_dijkstra( state, (state -> [{state, cost}]), (state -> boolean()), cost, (cost, cost -> cost), (cost, cost -> :lt | :eq | :gt) ) :: {:ok, cost} | :error when state: var, cost: var
Run Dijkstra on an implicit (generated) graph.
Instead of storing all edges explicitly, provide a successor function that generates neighbors on demand. This is useful for:
- Infinite or very large graphs
- Grid-based pathfinding with dynamic obstacles
- Game state spaces
Parameters
from- Starting statesuccessors- Functionstate -> [{neighbor, cost}]is_goal- Functionstate -> booleanto check if goal reachedzero- Identity value for the weight typeadd- Function to add two weightscompare- Function to compare weights
Returns
{:ok, cost}- Minimum cost to reach goal:error- Goal is unreachable
Examples
# Search on a linear chain: 1->2->3->4 with costs 1,2,3
iex> successors = fn
...> 1 -> [{2, 1}]
...> 2 -> [{3, 2}]
...> 3 -> [{4, 3}]
...> 4 -> []
...> end
iex> compare = &Yog.Utils.compare/2
iex> {:ok, cost} = Dijkstra.implicit_dijkstra(
...> 1, successors, fn x -> x == 4 end,
...> 0, &(&1 + &2), compare
...> )
iex> cost
6Implicit Dijkstra with key function using keyword options.
Options
:from- Starting state:successors_with_cost- Function returning neighbors with costs:visited_by- Function to extract a key for visited tracking:is_goal- Function to check if a state is the goal:zero- Identity value for the weight type:add- Function to add two weights:compare- Function to compare weights
@spec implicit_dijkstra_by( state, (state -> [{state, cost}]), (state -> term()), (state -> boolean()), cost, (cost, cost -> cost), (cost, cost -> :lt | :eq | :gt) ) :: {:ok, cost} | :error when state: var, cost: var
Implicit Dijkstra with a key function for visited state tracking.
Similar to implicit_dijkstra/6, but uses a key function to determine
when states should be considered "visited". This allows:
- Efficient pruning of equivalent states
- Custom equivalence relations beyond simple equality
Parameters
from- Starting statesuccessors- Functionstate -> [{neighbor, cost}]key_fn- Functionstate -> keyfor visited trackingis_goal- Functionstate -> booleanto check if goal reachedzero- Identity value for the weight typeadd- Function to add two weightscompare- Function to compare weights
Examples
iex> successors = fn
...> {pos, _dir} when pos < 3 -> [{{pos + 1, :fwd}, 1}]
...> _ -> []
...> end
iex> key_fn = fn {pos, _dir} -> pos end
iex> goal_fn = fn {pos, _dir} -> pos == 3 end
iex> compare = &Yog.Utils.compare/2
iex> {:ok, cost} = Dijkstra.implicit_dijkstra_by(
...> {0, :start}, successors, key_fn,
...> goal_fn, 0, &(&1 + &2), compare
...> )
iex> cost
3@spec shortest_path(keyword()) :: path_result()
Find shortest path using keyword options.
Options
:in- The graph to search:from- Starting node:to- Target node:zero- Identity value for the weight type:add- Function to add two weights:compare- Function to compare weights (:lt,:eq,:gt)
Examples
Pathfinding.shortest_path(
in: graph,
from: :a,
to: :c,
zero: 0,
add: &(&1 + &2),
compare: &Yog.Utils.compare/2
)@spec shortest_path( Yog.t(), Yog.node_id(), Yog.node_id(), weight, (weight, weight -> weight), (weight, weight -> :lt | :eq | :gt) ) :: path_result() when weight: var
Find the shortest path between two nodes using custom numeric operations.
Parameters
graph- The graph to searchfrom- Starting nodeto- Target nodezero- Identity value for the weight typeadd- Function to add two weights:(weight, weight) -> weightcompare- Function to compare weights, returns:lt,:eq, or:gt
Returns
{:ok, path}- APathstruct containing the nodes and total weight:error- No path exists between the nodes
Examples
iex> graph = Yog.directed()
...> |> Yog.add_node(:a, nil)
...> |> Yog.add_node(:b, nil)
...> |> Yog.add_node(:c, nil)
...> |> Yog.add_edge!(:a, :b, 4)
...> |> Yog.add_edge!(:b, :c, 1)
iex> compare = &Yog.Utils.compare/2
iex> {:ok, path} = Dijkstra.shortest_path(graph, :a, :c, 0, &(&1 + &2), compare)
iex> path.nodes
[:a, :b, :c]
iex> path.weight
5
iex> graph = Yog.directed()
...> |> Yog.add_node(:a, nil)
...> |> Yog.add_node(:b, nil)
...> |> Yog.add_node(:c, nil)
...> |> Yog.add_edge!(:a, :b, 4)
...> |> Yog.add_edge!(:b, :c, 1)
iex> compare = &Yog.Utils.compare/2
iex> Dijkstra.shortest_path(graph, :a, :nonexistent, 0, &(&1 + &2), compare)
:error@spec single_source_distances(keyword()) :: %{required(Yog.node_id()) => any()}
Single-source distances using keyword options.
Options
:in- The graph to search:from- Starting node:zero- Identity value for the weight type:add- Function to add two weights:compare- Function to compare weights
Examples
Pathfinding.single_source_distances(
in: graph,
from: :a,
zero: 0,
add: &(&1 + &2),
compare: &Yog.Utils.compare/2
)@spec single_source_distances( Yog.t(), Yog.node_id(), weight, (weight, weight -> weight), (weight, weight -> :lt | :eq | :gt) ) :: %{required(Yog.node_id()) => weight} when weight: var
Calculate single-source shortest distances to all reachable nodes.
Returns a map of node IDs to their shortest distance from the source.
Parameters
graph- The graph to searchfrom- Source nodezero- Identity value for the weight typeadd- Function to add two weightscompare- Function to compare weights
Examples
iex> graph = Yog.directed()
...> |> Yog.add_node(:a, nil)
...> |> Yog.add_node(:b, nil)
...> |> Yog.add_node(:c, nil)
...> |> Yog.add_edge!(:a, :b, 4)
...> |> Yog.add_edge!(:a, :c, 2)
...> |> Yog.add_edge!(:b, :c, 1)
iex> compare = &Yog.Utils.compare/2
iex> Dijkstra.single_source_distances(graph, :a, 0, &(&1 + &2), compare)
%{a: 0, b: 4, c: 2}