Current section
Files
Jump to
Current section
Files
src/yog@pathfinding@dijkstra.erl
-module(yog@pathfinding@dijkstra).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/pathfinding/dijkstra.gleam").
-export([do_dijkstra/6, shortest_path/6, single_source_distances/5, implicit_dijkstra/6, implicit_dijkstra_by/7, shortest_path_int/3, shortest_path_float/3, single_source_distances_int/2, single_source_distances_float/2]).
-if(?OTP_RELEASE >= 27).
-define(MODULEDOC(Str), -moduledoc(Str)).
-define(DOC(Str), -doc(Str)).
-else.
-define(MODULEDOC(Str), -compile([])).
-define(DOC(Str), -compile([])).
-endif.
?MODULEDOC(
" [Dijkstra's algorithm](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) for \n"
" single-source shortest paths in graphs with non-negative edge weights.\n"
"\n"
" Dijkstra's algorithm finds the shortest path from a source node to all other reachable\n"
" nodes in a graph. It works by maintaining a priority queue of nodes to visit,\n"
" always expanding the node with the smallest known distance.\n"
"\n"
" ## Algorithm\n"
"\n"
" | Algorithm | Function | Complexity | Best For |\n"
" |-----------|----------|------------|----------|\n"
" | [Dijkstra](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) (single-target) | `shortest_path/6` | O((V + E) log V) | One-to-one shortest path |\n"
" | [Dijkstra](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) (single-source) | `single_source_distances/5` | O((V + E) log V) | One-to-all shortest paths |\n"
" | Implicit Dijkstra | `implicit_dijkstra/6` | O((V + E) log V) | Large/infinite graphs |\n"
"\n"
" ## Key Concepts\n"
"\n"
" - **Greedy Strategy**: Always expands the node with minimum tentative distance\n"
" - **Priority Queue**: Min-heap ordered by current best distance\n"
" - **Relaxation**: Update distances when a shorter path is found\n"
" - **Non-Negative Weights**: Required for correctness (use Bellman-Ford for negative weights)\n"
"\n"
" ## Comparison with Other Algorithms\n"
"\n"
" | Algorithm | Handles Negative Weights | Complexity | Use Case |\n"
" |-----------|-------------------------|------------|----------|\n"
" | Dijkstra | ❌ No | O((V+E) log V) | General shortest paths |\n"
" | A* | ❌ No | O((V+E) log V) | When good heuristic available |\n"
" | Bellman-Ford | ✅ Yes | O(VE) | Negative weights, cycle detection |\n"
" | Floyd-Warshall | ✅ Yes | O(V³) | All-pairs shortest paths |\n"
"\n"
" ## History\n"
"\n"
" Edsger W. Dijkstra published this algorithm in 1959. The original paper described\n"
" it for finding the shortest path between two nodes, but it's commonly used for\n"
" single-source shortest paths to all nodes.\n"
"\n"
" ## Use Cases\n"
"\n"
" - **Network routing**: OSPF, IS-IS protocols use Dijkstra\n"
" - **Map services**: Shortest driving directions\n"
" - **Social networks**: Degrees of separation\n"
" - **Game development**: Shortest path on weighted grids\n"
"\n"
" ## References\n"
"\n"
" - [Wikipedia: Dijkstra's Algorithm](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm)\n"
" - [Dijkstra's Original Paper (1959)](https://link.springer.com/article/10.1007/BF01386390)\n"
" - [Red Blob Games: Dijkstra Introduction](https://www.redblobgames.com/pathfinding/a-star/introduction.html)\n"
" - [CP-Algorithms: Dijkstra](https://cp-algorithms.com/graph/dijkstra.html)\n"
).
-file("src/yog/pathfinding/dijkstra.gleam", 109).
-spec do_dijkstra(
yog@model:graph(any(), KCD),
integer(),
gleamy@pairing_heap:heap({KCD, list(integer())}),
gleam@dict:dict(integer(), KCD),
fun((KCD, KCD) -> KCD),
fun((KCD, KCD) -> gleam@order:order())
) -> gleam@option:option({KCD, list(integer())}).
do_dijkstra(Graph, Goal, Frontier, Visited, Add, Compare) ->
case gleamy@priority_queue:pop(Frontier) of
{error, nil} ->
none;
{ok, {{Dist, [Current | _] = Path}, Rest_frontier}} ->
case Current =:= Goal of
true ->
{some, {Dist, Path}};
false ->
Should_explore = yog@pathfinding@utils:should_explore_node(
Visited,
Current,
Dist,
Compare
),
case Should_explore of
false ->
do_dijkstra(
Graph,
Goal,
Rest_frontier,
Visited,
Add,
Compare
);
true ->
New_visited = gleam@dict:insert(
Visited,
Current,
Dist
),
Next_frontier = begin
_pipe = yog@model:successors(Graph, Current),
gleam@list:fold(
_pipe,
Rest_frontier,
fun(H, Neighbor) ->
{Next_id, Weight} = Neighbor,
gleamy@priority_queue:push(
H,
{Add(Dist, Weight),
[Next_id | Path]}
)
end
)
end,
do_dijkstra(
Graph,
Goal,
Next_frontier,
New_visited,
Add,
Compare
)
end
end;
{ok, _} ->
none
end.
-file("src/yog/pathfinding/dijkstra.gleam", 90).
?DOC(
" Finds the shortest path between two nodes using Dijkstra's algorithm.\n"
"\n"
" Works with non-negative edge weights only.\n"
"\n"
" **Time Complexity:** O((V + E) log V) with heap\n"
"\n"
" ## Parameters\n"
"\n"
" - `zero`: The identity element for addition (e.g., 0 for integers)\n"
" - `add`: Function to add two weights\n"
" - `compare`: Function to compare two weights\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" dijkstra.shortest_path(\n"
" in: graph,\n"
" from: 1,\n"
" to: 5,\n"
" with_zero: 0,\n"
" with_add: int.add,\n"
" with_compare: int.compare\n"
" )\n"
" // => Some(Path([1, 2, 5], 15))\n"
" ```\n"
).
-spec shortest_path(
yog@model:graph(any(), KBX),
integer(),
integer(),
KBX,
fun((KBX, KBX) -> KBX),
fun((KBX, KBX) -> gleam@order:order())
) -> gleam@option:option(yog@pathfinding@utils:path(KBX)).
shortest_path(Graph, Start, Goal, Zero, Add, Compare) ->
Frontier = begin
_pipe = gleamy@priority_queue:new(
fun(A, B) ->
yog@pathfinding@utils:compare_frontier(A, B, Compare)
end
),
gleamy@priority_queue:push(_pipe, {Zero, [Start]})
end,
_pipe@1 = do_dijkstra(Graph, Goal, Frontier, maps:new(), Add, Compare),
gleam@option:map(
_pipe@1,
fun(Res) ->
{Dist, Path} = Res,
{path, lists:reverse(Path), Dist}
end
).
-file("src/yog/pathfinding/dijkstra.gleam", 178).
-spec do_single_source_dijkstra(
yog@model:graph(any(), KCT),
gleamy@pairing_heap:heap({KCT, integer()}),
gleam@dict:dict(integer(), KCT),
fun((KCT, KCT) -> KCT),
fun((KCT, KCT) -> gleam@order:order())
) -> gleam@dict:dict(integer(), KCT).
do_single_source_dijkstra(Graph, Frontier, Distances, Add, Compare) ->
case gleamy@priority_queue:pop(Frontier) of
{error, nil} ->
Distances;
{ok, {{Dist, Current}, Rest_frontier}} ->
Should_explore = yog@pathfinding@utils:should_explore_node(
Distances,
Current,
Dist,
Compare
),
case Should_explore of
false ->
do_single_source_dijkstra(
Graph,
Rest_frontier,
Distances,
Add,
Compare
);
true ->
New_distances = gleam@dict:insert(Distances, Current, Dist),
Next_frontier = begin
_pipe = yog@model:successors(Graph, Current),
gleam@list:fold(
_pipe,
Rest_frontier,
fun(H, Neighbor) ->
{Next_id, Weight} = Neighbor,
gleamy@priority_queue:push(
H,
{Add(Dist, Weight), Next_id}
)
end
)
end,
do_single_source_dijkstra(
Graph,
Next_frontier,
New_distances,
Add,
Compare
)
end
end.
-file("src/yog/pathfinding/dijkstra.gleam", 164).
?DOC(
" Computes shortest distances from a source node to all reachable nodes.\n"
"\n"
" Returns a dictionary mapping each reachable node to its shortest distance\n"
" from the source. Unreachable nodes are not included in the result.\n"
"\n"
" **Time Complexity:** O((V + E) log V) with heap\n"
"\n"
" ## Parameters\n"
"\n"
" - `zero`: The identity element for addition (e.g., 0 for integers)\n"
" - `add`: Function to add two weights\n"
" - `compare`: Function to compare two weights\n"
).
-spec single_source_distances(
yog@model:graph(any(), KCN),
integer(),
KCN,
fun((KCN, KCN) -> KCN),
fun((KCN, KCN) -> gleam@order:order())
) -> gleam@dict:dict(integer(), KCN).
single_source_distances(Graph, Source, Zero, Add, Compare) ->
Frontier = begin
_pipe = gleamy@priority_queue:new(
fun(A, B) ->
yog@pathfinding@utils:compare_distance_frontier(A, B, Compare)
end
),
gleamy@priority_queue:push(_pipe, {Zero, Source})
end,
do_single_source_dijkstra(Graph, Frontier, maps:new(), Add, Compare).
-file("src/yog/pathfinding/dijkstra.gleam", 257).
-spec do_implicit_dijkstra(
gleamy@pairing_heap:heap({KDF, KDG}),
gleam@dict:dict(KDG, KDF),
fun((KDG) -> list({KDG, KDF})),
fun((KDG) -> boolean()),
fun((KDF, KDF) -> KDF),
fun((KDF, KDF) -> gleam@order:order())
) -> gleam@option:option(KDF).
do_implicit_dijkstra(Frontier, Distances, Successors, Is_goal, Add, Compare) ->
case gleamy@priority_queue:pop(Frontier) of
{error, nil} ->
none;
{ok, {{Dist, Current}, Rest_frontier}} ->
case Is_goal(Current) of
true ->
{some, Dist};
false ->
Should_explore = yog@pathfinding@utils:should_explore_node(
Distances,
Current,
Dist,
Compare
),
case Should_explore of
false ->
do_implicit_dijkstra(
Rest_frontier,
Distances,
Successors,
Is_goal,
Add,
Compare
);
true ->
New_distances = gleam@dict:insert(
Distances,
Current,
Dist
),
Next_frontier = begin
_pipe = Successors(Current),
gleam@list:fold(
_pipe,
Rest_frontier,
fun(H, Neighbor) ->
{Next_state, Cost} = Neighbor,
gleamy@priority_queue:push(
H,
{Add(Dist, Cost), Next_state}
)
end
)
end,
do_implicit_dijkstra(
Next_frontier,
New_distances,
Successors,
Is_goal,
Add,
Compare
)
end
end
end.
-file("src/yog/pathfinding/dijkstra.gleam", 240).
?DOC(
" Finds the shortest path in an implicit graph using Dijkstra's algorithm.\n"
"\n"
" Instead of a materialized `Graph`, this uses a `successors_with_cost` function\n"
" to compute weighted neighbors on demand.\n"
"\n"
" Returns the shortest distance to any state satisfying `is_goal`, or `None`\n"
" if no goal state is reachable.\n"
"\n"
" **Time Complexity:** O((V + E) log V) where V is visited states and E is explored transitions\n"
"\n"
" ## Parameters\n"
"\n"
" - `successors_with_cost`: Function that generates weighted successors for a state\n"
" - `is_goal`: Predicate that identifies goal states\n"
" - `zero`: The identity element for addition (e.g., 0 for integers)\n"
" - `add`: Function to add two costs\n"
" - `compare`: Function to compare two costs\n"
).
-spec implicit_dijkstra(
KDB,
fun((KDB) -> list({KDB, KDC})),
fun((KDB) -> boolean()),
KDC,
fun((KDC, KDC) -> KDC),
fun((KDC, KDC) -> gleam@order:order())
) -> gleam@option:option(KDC).
implicit_dijkstra(Start, Successors, Is_goal, Zero, Add, Compare) ->
Frontier = begin
_pipe = gleamy@priority_queue:new(
fun(A, B) -> Compare(erlang:element(1, A), erlang:element(1, B)) end
),
gleamy@priority_queue:push(_pipe, {Zero, Start})
end,
do_implicit_dijkstra(
Frontier,
maps:new(),
Successors,
Is_goal,
Add,
Compare
).
-file("src/yog/pathfinding/dijkstra.gleam", 342).
-spec do_implicit_dijkstra_by(
gleamy@pairing_heap:heap({KDR, KDS}),
gleam@dict:dict(KDU, KDR),
fun((KDS) -> list({KDS, KDR})),
fun((KDS) -> KDU),
fun((KDS) -> boolean()),
fun((KDR, KDR) -> KDR),
fun((KDR, KDR) -> gleam@order:order())
) -> gleam@option:option(KDR).
do_implicit_dijkstra_by(
Frontier,
Distances,
Successors,
Key_fn,
Is_goal,
Add,
Compare
) ->
case gleamy@priority_queue:pop(Frontier) of
{error, nil} ->
none;
{ok, {{Dist, Current}, Rest_frontier}} ->
case Is_goal(Current) of
true ->
{some, Dist};
false ->
Current_key = Key_fn(Current),
Should_explore = yog@pathfinding@utils:should_explore_node(
Distances,
Current_key,
Dist,
Compare
),
case Should_explore of
false ->
do_implicit_dijkstra_by(
Rest_frontier,
Distances,
Successors,
Key_fn,
Is_goal,
Add,
Compare
);
true ->
New_distances = gleam@dict:insert(
Distances,
Current_key,
Dist
),
Next_frontier = begin
_pipe = Successors(Current),
gleam@list:fold(
_pipe,
Rest_frontier,
fun(H, Neighbor) ->
{Next_state, Cost} = Neighbor,
gleamy@priority_queue:push(
H,
{Add(Dist, Cost), Next_state}
)
end
)
end,
do_implicit_dijkstra_by(
Next_frontier,
New_distances,
Successors,
Key_fn,
Is_goal,
Add,
Compare
)
end
end
end.
-file("src/yog/pathfinding/dijkstra.gleam", 316).
?DOC(
" Like `implicit_dijkstra`, but deduplicates visited states by a custom key.\n"
"\n"
" Essential when your state carries extra data beyond what defines identity.\n"
" The `visited_by` function extracts the deduplication key from each state.\n"
"\n"
" **Time Complexity:** O((V + E) log V) where V and E are measured in unique *keys*\n"
).
-spec implicit_dijkstra_by(
KDM,
fun((KDM) -> list({KDM, KDN})),
fun((KDM) -> any()),
fun((KDM) -> boolean()),
KDN,
fun((KDN, KDN) -> KDN),
fun((KDN, KDN) -> gleam@order:order())
) -> gleam@option:option(KDN).
implicit_dijkstra_by(Start, Successors, Key_fn, Is_goal, Zero, Add, Compare) ->
Frontier = begin
_pipe = gleamy@priority_queue:new(
fun(A, B) -> Compare(erlang:element(1, A), erlang:element(1, B)) end
),
gleamy@priority_queue:push(_pipe, {Zero, Start})
end,
do_implicit_dijkstra_by(
Frontier,
maps:new(),
Successors,
Key_fn,
Is_goal,
Add,
Compare
).
-file("src/yog/pathfinding/dijkstra.gleam", 431).
?DOC(
" Finds the shortest path using **integer weights**.\n"
"\n"
" This is a convenience wrapper around `shortest_path` that uses:\n"
" - `0` as the zero element\n"
" - `int.add` for addition\n"
" - `int.compare` for comparison\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" // Much cleaner than the full explicit version\n"
" dijkstra.shortest_path_int(graph, from: 1, to: 5)\n"
" // => Some(Path([1, 2, 5], 15))\n"
"\n"
" // Equivalent explicit call:\n"
" // dijkstra.shortest_path(\n"
" // graph, from: 1, to: 5,\n"
" // with_zero: 0,\n"
" // with_add: int.add,\n"
" // with_compare: int.compare\n"
" // )\n"
" ```\n"
"\n"
" ## When to Use\n"
"\n"
" Use this for graphs with `Int` edge weights (hop counts, distances in meters,\n"
" costs in cents, etc.). For custom weight types (Money, Distance, etc.), use\n"
" the full `shortest_path` function with your own semiring operations.\n"
).
-spec shortest_path_int(yog@model:graph(any(), integer()), integer(), integer()) -> gleam@option:option(yog@pathfinding@utils:path(integer())).
shortest_path_int(Graph, Start, Goal) ->
shortest_path(
Graph,
Start,
Goal,
0,
fun gleam@int:add/2,
fun gleam@int:compare/2
).
-file("src/yog/pathfinding/dijkstra.gleam", 466).
?DOC(
" Finds the shortest path using **float weights**.\n"
"\n"
" This is a convenience wrapper around `shortest_path` that uses:\n"
" - `0.0` as the zero element\n"
" - `float.add` for addition\n"
" - `float.compare` for comparison\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" dijkstra.shortest_path_float(graph, from: 1, to: 5)\n"
" // => Some(Path([1, 2, 5], 15.5))\n"
" ```\n"
"\n"
" ## When to Use\n"
"\n"
" Use this for graphs with `Float` edge weights (probabilities, distances in\n"
" kilometers with decimal precision, continuous costs, etc.). Note that float\n"
" arithmetic has precision limitations - for exact calculations, prefer `Int`\n"
" weights (e.g., store cents instead of dollars).\n"
).
-spec shortest_path_float(yog@model:graph(any(), float()), integer(), integer()) -> gleam@option:option(yog@pathfinding@utils:path(float())).
shortest_path_float(Graph, Start, Goal) ->
shortest_path(
Graph,
Start,
Goal,
+0.0,
fun gleam@float:add/2,
fun gleam@float:compare/2
).
-file("src/yog/pathfinding/dijkstra.gleam", 484).
?DOC(
" Computes shortest distances using **integer weights**.\n"
"\n"
" Convenience wrapper for `single_source_distances` with `Int` weights.\n"
).
-spec single_source_distances_int(yog@model:graph(any(), integer()), integer()) -> gleam@dict:dict(integer(), integer()).
single_source_distances_int(Graph, Source) ->
single_source_distances(
Graph,
Source,
0,
fun gleam@int:add/2,
fun gleam@int:compare/2
).
-file("src/yog/pathfinding/dijkstra.gleam", 500).
?DOC(
" Computes shortest distances using **float weights**.\n"
"\n"
" Convenience wrapper for `single_source_distances` with `Float` weights.\n"
).
-spec single_source_distances_float(yog@model:graph(any(), float()), integer()) -> gleam@dict:dict(integer(), float()).
single_source_distances_float(Graph, Source) ->
single_source_distances(
Graph,
Source,
+0.0,
fun gleam@float:add/2,
fun gleam@float:compare/2
).