Current section
Files
Jump to
Current section
Files
src/yog@pathfinding@bellman_ford.erl
-module(yog@pathfinding@bellman_ford).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/pathfinding/bellman_ford.gleam").
-export([relaxation_passes/7, has_negative_cycle/5, reconstruct_path/4, bellman_ford/6, implicit_bellman_ford/6, implicit_bellman_ford_by/7, bellman_ford_int/3, bellman_ford_float/3]).
-export_type([bellman_ford_result/1, implicit_bellman_ford_result/1]).
-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(
" [Bellman-Ford algorithm](https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm) for \n"
" single-source shortest paths with support for negative edge weights.\n"
"\n"
" The Bellman-Ford algorithm finds shortest paths from a source node to all other nodes,\n"
" even when edges have negative weights. It can also detect negative cycles reachable\n"
" from the source, which make shortest paths undefined.\n"
"\n"
" ## Algorithm\n"
"\n"
" | Algorithm | Function | Complexity | Best For |\n"
" |-----------|----------|------------|----------|\n"
" | [Bellman-Ford](https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm) | `bellman_ford/6` | O(VE) | Negative weights, cycle detection |\n"
" | SPFA (Queue-optimized) | `bellman_ford/6` | O(E) average | Sparse graphs with few negative edges |\n"
" | Implicit Bellman-Ford | `implicit_bellman_ford/6` | O(VE) | Implicit/large graphs |\n"
"\n"
" ## Key Concepts\n"
"\n"
" - **Relaxation**: Repeatedly improve distance estimates (V-1 passes)\n"
" - **Negative Cycle**: Cycle with total negative weight (no shortest path exists)\n"
" - **Shortest Path Tree**: Tree of shortest paths from source to all nodes\n"
"\n"
" ## Why V-1 Relaxation Passes?\n"
"\n"
" In a graph with V nodes, any shortest path has at most V-1 edges.\n"
" Each pass of Bellman-Ford relaxes all edges, propagating shortest\n"
" path information one hop further each time.\n"
"\n"
" ## Comparison with Dijkstra\n"
"\n"
" | Feature | Bellman-Ford | Dijkstra |\n"
" |---------|--------------|----------|\n"
" | Negative weights | ✅ Yes | ❌ No |\n"
" | Negative cycle detection | ✅ Yes | ❌ N/A |\n"
" | Time complexity | O(VE) | O((V+E) log V) |\n"
" | Data structure | Simple loops | Priority queue |\n"
"\n"
" ## When to Use Bellman-Ford\n"
"\n"
" **Use Bellman-Ford when:**\n"
" - Edge weights may be negative\n"
" - You need to detect negative cycles\n"
" - The graph is small or sparse enough for O(VE)\n"
"\n"
" **Use Dijkstra when:**\n"
" - All edge weights are non-negative\n"
" - You need better performance\n"
"\n"
" ## Use Cases\n"
"\n"
" - **Currency arbitrage**: Detecting negative cycles in exchange rates\n"
" - **Financial modeling**: Cost calculations with credits/penalties\n"
" - **Chemical reactions**: Energy changes with positive and negative values\n"
" - **Constraint solving**: Difference constraints systems\n"
"\n"
" ## History\n"
"\n"
" Published independently by Richard Bellman (1958) and Lester Ford Jr. (1956).\n"
" The algorithm is a classic example of dynamic programming.\n"
"\n"
" ## References\n"
"\n"
" - [Wikipedia: Bellman-Ford Algorithm](https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm)\n"
" - [Wikipedia: Shortest Path Faster Algorithm (SPFA)](https://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm)\n"
" - [CP-Algorithms: Bellman-Ford](https://cp-algorithms.com/graph/bellman_ford.html)\n"
" - [CS 170: Bellman-Ford Lecture](https://cs170.org/lecture-notes/)\n"
).
-type bellman_ford_result(WQP) :: {shortest_path,
yog@pathfinding@utils:path(WQP)} |
negative_cycle |
no_path.
-type implicit_bellman_ford_result(WQQ) :: {found_goal, WQQ} |
detected_negative_cycle |
no_goal.
-file("src/yog/pathfinding/bellman_ford.gleam", 148).
-spec relaxation_passes(
yog@model:graph(any(), WQX),
list(integer()),
gleam@dict:dict(integer(), WQX),
gleam@dict:dict(integer(), integer()),
integer(),
fun((WQX, WQX) -> WQX),
fun((WQX, WQX) -> gleam@order:order())
) -> {gleam@dict:dict(integer(), WQX), gleam@dict:dict(integer(), integer())}.
relaxation_passes(
Graph,
Nodes,
Distances,
Predecessors,
Remaining,
Add,
Compare
) ->
case Remaining =< 0 of
true ->
{Distances, Predecessors};
false ->
{New_distances, New_predecessors} = gleam@list:fold(
Nodes,
{Distances, Predecessors},
fun(Acc, U) ->
{Dists, Preds} = Acc,
case gleam_stdlib:map_get(Dists, U) of
{error, nil} ->
Acc;
{ok, U_dist} ->
Neighbors = yog@model:successors(Graph, U),
gleam@list:fold(
Neighbors,
{Dists, Preds},
fun(Inner_acc, Edge) ->
{V, Weight} = Edge,
{Curr_dists, Curr_preds} = Inner_acc,
New_dist = Add(U_dist, Weight),
case gleam_stdlib:map_get(Curr_dists, V) of
{error, nil} ->
{gleam@dict:insert(
Curr_dists,
V,
New_dist
),
gleam@dict:insert(
Curr_preds,
V,
U
)};
{ok, V_dist} ->
case Compare(New_dist, V_dist) of
lt ->
{gleam@dict:insert(
Curr_dists,
V,
New_dist
),
gleam@dict:insert(
Curr_preds,
V,
U
)};
_ ->
Inner_acc
end
end
end
)
end
end
),
relaxation_passes(
Graph,
Nodes,
New_distances,
New_predecessors,
Remaining - 1,
Add,
Compare
)
end.
-file("src/yog/pathfinding/bellman_ford.gleam", 206).
-spec has_negative_cycle(
yog@model:graph(any(), WRK),
list(integer()),
gleam@dict:dict(integer(), WRK),
fun((WRK, WRK) -> WRK),
fun((WRK, WRK) -> gleam@order:order())
) -> boolean().
has_negative_cycle(Graph, Nodes, Distances, Add, Compare) ->
gleam@list:any(Nodes, fun(U) -> case gleam_stdlib:map_get(Distances, U) of
{error, nil} ->
false;
{ok, U_dist} ->
_pipe = yog@model:successors(Graph, U),
gleam@list:any(
_pipe,
fun(Edge) ->
{V, Weight} = Edge,
New_dist = Add(U_dist, Weight),
case gleam_stdlib:map_get(Distances, V) of
{error, nil} ->
false;
{ok, V_dist} ->
case Compare(New_dist, V_dist) of
lt ->
true;
_ ->
false
end
end
end
)
end end).
-file("src/yog/pathfinding/bellman_ford.gleam", 236).
-spec reconstruct_path(
gleam@dict:dict(integer(), integer()),
integer(),
integer(),
list(integer())
) -> {ok, list(integer())} | {error, nil}.
reconstruct_path(Predecessors, Start, Current, Acc) ->
case Current =:= Start of
true ->
{ok, Acc};
false ->
case gleam_stdlib:map_get(Predecessors, Current) of
{error, nil} ->
{error, nil};
{ok, Pred} ->
reconstruct_path(Predecessors, Start, Pred, [Pred | Acc])
end
end.
-file("src/yog/pathfinding/bellman_ford.gleam", 107).
?DOC(
" Finds shortest path with support for negative edge weights using Bellman-Ford.\n"
"\n"
" **Time Complexity:** O(VE)\n"
"\n"
" ## Returns\n"
"\n"
" - `ShortestPath(path)`: If a valid shortest path exists\n"
" - `NegativeCycle`: If a negative cycle is reachable from the start node\n"
" - `NoPath`: If no path exists from start to goal\n"
).
-spec bellman_ford(
yog@model:graph(any(), WQS),
integer(),
integer(),
WQS,
fun((WQS, WQS) -> WQS),
fun((WQS, WQS) -> gleam@order:order())
) -> bellman_ford_result(WQS).
bellman_ford(Graph, Start, Goal, Zero, Add, Compare) ->
All_nodes = yog@model:all_nodes(Graph),
Initial_distances = maps:from_list([{Start, Zero}]),
Initial_predecessors = maps:new(),
Node_count = erlang:length(All_nodes),
{Distances, Predecessors} = relaxation_passes(
Graph,
All_nodes,
Initial_distances,
Initial_predecessors,
Node_count - 1,
Add,
Compare
),
case has_negative_cycle(Graph, All_nodes, Distances, Add, Compare) of
true ->
negative_cycle;
false ->
case gleam_stdlib:map_get(Distances, Goal) of
{error, nil} ->
no_path;
{ok, Dist} ->
case reconstruct_path(Predecessors, Start, Goal, [Goal]) of
{ok, Path} ->
{shortest_path, {path, Path, Dist}};
{error, nil} ->
no_path
end
end
end.
-file("src/yog/pathfinding/bellman_ford.gleam", 283).
-spec do_implicit_bellman_ford(
yog@internal@queue:queue(WSA),
gleam@dict:dict(WSA, WSC),
gleam@dict:dict(WSA, integer()),
gleam@set:set(WSA),
fun((WSA) -> list({WSA, WSC})),
fun((WSA) -> boolean()),
WSC,
fun((WSC, WSC) -> WSC),
fun((WSC, WSC) -> gleam@order:order())
) -> implicit_bellman_ford_result(WSC).
do_implicit_bellman_ford(
Q,
Distances,
Relax_counts,
In_queue,
Successors,
Is_goal,
Zero,
Add,
Compare
) ->
case yog@internal@queue:pop(Q) of
{error, nil} ->
_pipe = Distances,
_pipe@1 = maps:to_list(_pipe),
_pipe@2 = gleam@list:filter(
_pipe@1,
fun(Entry) -> Is_goal(erlang:element(1, Entry)) end
),
_pipe@3 = gleam@list:sort(
_pipe@2,
fun(A, B) ->
Compare(erlang:element(2, A), erlang:element(2, B))
end
),
_pipe@4 = gleam@list:first(_pipe@3),
_pipe@5 = gleam@result:map(
_pipe@4,
fun(Entry@1) -> {found_goal, erlang:element(2, Entry@1)} end
),
gleam@result:unwrap(_pipe@5, no_goal);
{ok, {Current, Rest_queue}} ->
New_in_queue = gleam@set:delete(In_queue, Current),
Current_dist = begin
_pipe@6 = gleam_stdlib:map_get(Distances, Current),
gleam@result:unwrap(_pipe@6, Zero)
end,
{New_distances, New_counts, New_queue, New_in_q} = begin
_pipe@7 = Successors(Current),
gleam@list:fold(
_pipe@7,
{Distances, Relax_counts, Rest_queue, New_in_queue},
fun(Acc, Neighbor) ->
{Dists, Counts, Q_acc, In_q_acc} = Acc,
{Next_state, Edge_cost} = Neighbor,
New_dist = Add(Current_dist, Edge_cost),
case gleam_stdlib:map_get(Dists, Next_state) of
{ok, Prev_dist} ->
case Compare(New_dist, Prev_dist) of
lt ->
Updated_dists = gleam@dict:insert(
Dists,
Next_state,
New_dist
),
Relax_count = begin
_pipe@8 = gleam_stdlib:map_get(
Counts,
Next_state
),
gleam@result:unwrap(_pipe@8, 0)
end,
New_count = Relax_count + 1,
Updated_counts = gleam@dict:insert(
Counts,
Next_state,
New_count
),
case New_count > maps:size(Dists) of
true ->
{Updated_dists,
Updated_counts,
Q_acc,
In_q_acc};
false ->
case gleam@set:contains(
In_q_acc,
Next_state
) of
true ->
{Updated_dists,
Updated_counts,
Q_acc,
In_q_acc};
false ->
{Updated_dists,
Updated_counts,
yog@internal@queue:push(
Q_acc,
Next_state
),
gleam@set:insert(
In_q_acc,
Next_state
)}
end
end;
_ ->
Acc
end;
{error, nil} ->
Updated_dists@1 = gleam@dict:insert(
Dists,
Next_state,
New_dist
),
Updated_counts@1 = gleam@dict:insert(
Counts,
Next_state,
1
),
{Updated_dists@1,
Updated_counts@1,
yog@internal@queue:push(Q_acc, Next_state),
gleam@set:insert(In_q_acc, Next_state)}
end
end
)
end,
Has_negative_cycle = begin
_pipe@9 = New_counts,
_pipe@10 = maps:to_list(_pipe@9),
gleam@list:any(
_pipe@10,
fun(Entry@2) ->
erlang:element(2, Entry@2) > maps:size(New_distances)
end
)
end,
case Has_negative_cycle of
true ->
detected_negative_cycle;
false ->
do_implicit_bellman_ford(
New_queue,
New_distances,
New_counts,
New_in_q,
Successors,
Is_goal,
Zero,
Add,
Compare
)
end
end.
-file("src/yog/pathfinding/bellman_ford.gleam", 262).
?DOC(
" Finds shortest path in implicit graphs with support for negative edge weights.\n"
"\n"
" **Time Complexity:** O(VE) average case\n"
"\n"
" ## Returns\n"
"\n"
" - `FoundGoal(cost)`: If a valid shortest path to goal exists\n"
" - `DetectedNegativeCycle`: If a negative cycle is reachable from start\n"
" - `NoGoal`: If no goal state is reached\n"
).
-spec implicit_bellman_ford(
WRW,
fun((WRW) -> list({WRW, WRX})),
fun((WRW) -> boolean()),
WRX,
fun((WRX, WRX) -> WRX),
fun((WRX, WRX) -> gleam@order:order())
) -> implicit_bellman_ford_result(WRX).
implicit_bellman_ford(Start, Successors, Is_goal, Zero, Add, Compare) ->
do_implicit_bellman_ford(
begin
_pipe = yog@internal@queue:new(),
yog@internal@queue:push(_pipe, Start)
end,
maps:from_list([{Start, Zero}]),
maps:from_list([{Start, 0}]),
gleam@set:new(),
Successors,
Is_goal,
Zero,
Add,
Compare
).
-file("src/yog/pathfinding/bellman_ford.gleam", 412).
-spec do_implicit_bellman_ford_by(
yog@internal@queue:queue(WSP),
gleam@dict:dict(WSR, {WSS, WSP}),
gleam@dict:dict(WSR, integer()),
gleam@set:set(WSP),
fun((WSP) -> list({WSP, WSS})),
fun((WSP) -> WSR),
fun((WSP) -> boolean()),
WSS,
fun((WSS, WSS) -> WSS),
fun((WSS, WSS) -> gleam@order:order())
) -> implicit_bellman_ford_result(WSS).
do_implicit_bellman_ford_by(
Q,
Distances,
Relax_counts,
In_queue,
Successors,
Key_fn,
Is_goal,
Zero,
Add,
Compare
) ->
case yog@internal@queue:pop(Q) of
{error, nil} ->
_pipe = Distances,
_pipe@1 = maps:to_list(_pipe),
_pipe@2 = gleam@list:filter(
_pipe@1,
fun(Entry) ->
Is_goal(erlang:element(2, erlang:element(2, Entry)))
end
),
_pipe@3 = gleam@list:sort(
_pipe@2,
fun(A, B) ->
Compare(
erlang:element(1, erlang:element(2, A)),
erlang:element(1, erlang:element(2, B))
)
end
),
_pipe@4 = gleam@list:first(_pipe@3),
_pipe@5 = gleam@result:map(
_pipe@4,
fun(Entry@1) ->
{found_goal, erlang:element(1, erlang:element(2, Entry@1))}
end
),
gleam@result:unwrap(_pipe@5, no_goal);
{ok, {Current, Rest_queue}} ->
Current_key = Key_fn(Current),
New_in_queue = gleam@set:delete(In_queue, Current),
{Current_dist, _} = begin
_pipe@6 = gleam_stdlib:map_get(Distances, Current_key),
gleam@result:unwrap(_pipe@6, {Zero, Current})
end,
{New_distances, New_counts, New_queue, New_in_q} = begin
_pipe@7 = Successors(Current),
gleam@list:fold(
_pipe@7,
{Distances, Relax_counts, Rest_queue, New_in_queue},
fun(Acc, Neighbor) ->
{Dists, Counts, Q_acc, In_q_acc} = Acc,
{Next_state, Edge_cost} = Neighbor,
Next_key = Key_fn(Next_state),
New_dist = Add(Current_dist, Edge_cost),
case gleam_stdlib:map_get(Dists, Next_key) of
{ok, {Prev_dist, _}} ->
case Compare(New_dist, Prev_dist) of
lt ->
Updated_dists = gleam@dict:insert(
Dists,
Next_key,
{New_dist, Next_state}
),
Relax_count = begin
_pipe@8 = gleam_stdlib:map_get(
Counts,
Next_key
),
gleam@result:unwrap(_pipe@8, 0)
end,
New_count = Relax_count + 1,
Updated_counts = gleam@dict:insert(
Counts,
Next_key,
New_count
),
case New_count > maps:size(Dists) of
true ->
{Updated_dists,
Updated_counts,
Q_acc,
In_q_acc};
false ->
case gleam@set:contains(
In_q_acc,
Next_state
) of
true ->
{Updated_dists,
Updated_counts,
Q_acc,
In_q_acc};
false ->
{Updated_dists,
Updated_counts,
yog@internal@queue:push(
Q_acc,
Next_state
),
gleam@set:insert(
In_q_acc,
Next_state
)}
end
end;
_ ->
Acc
end;
{error, nil} ->
Updated_dists@1 = gleam@dict:insert(
Dists,
Next_key,
{New_dist, Next_state}
),
Updated_counts@1 = gleam@dict:insert(
Counts,
Next_key,
1
),
{Updated_dists@1,
Updated_counts@1,
yog@internal@queue:push(Q_acc, Next_state),
gleam@set:insert(In_q_acc, Next_state)}
end
end
)
end,
Has_negative_cycle = begin
_pipe@9 = New_counts,
_pipe@10 = maps:to_list(_pipe@9),
gleam@list:any(
_pipe@10,
fun(Entry@2) ->
erlang:element(2, Entry@2) > maps:size(New_distances)
end
)
end,
case Has_negative_cycle of
true ->
detected_negative_cycle;
false ->
do_implicit_bellman_ford_by(
New_queue,
New_distances,
New_counts,
New_in_q,
Successors,
Key_fn,
Is_goal,
Zero,
Add,
Compare
)
end
end.
-file("src/yog/pathfinding/bellman_ford.gleam", 388).
?DOC(" Like `implicit_bellman_ford`, but deduplicates visited states by a custom key.\n").
-spec implicit_bellman_ford_by(
WSK,
fun((WSK) -> list({WSK, WSL})),
fun((WSK) -> any()),
fun((WSK) -> boolean()),
WSL,
fun((WSL, WSL) -> WSL),
fun((WSL, WSL) -> gleam@order:order())
) -> implicit_bellman_ford_result(WSL).
implicit_bellman_ford_by(Start, Successors, Key_fn, Is_goal, Zero, Add, Compare) ->
Start_key = Key_fn(Start),
do_implicit_bellman_ford_by(
begin
_pipe = yog@internal@queue:new(),
yog@internal@queue:push(_pipe, Start)
end,
maps:from_list([{Start_key, {Zero, Start}}]),
maps:from_list([{Start_key, 0}]),
gleam@set:new(),
Successors,
Key_fn,
Is_goal,
Zero,
Add,
Compare
).
-file("src/yog/pathfinding/bellman_ford.gleam", 546).
?DOC(
" Finds shortest path with **integer weights**, handling negative edges.\n"
"\n"
" This is a convenience wrapper around `bellman_ford` 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"
" bellman_ford.bellman_ford_int(graph, from: 1, to: 5)\n"
" // => ShortestPath(Path([1, 2, 5], 15))\n"
" ```\n"
"\n"
" ## When to Use\n"
"\n"
" Use this for graphs with `Int` edge weights that may be negative (arbitrage\n"
" detection, time-dependent costs, etc.). For graphs with only non-negative\n"
" weights, prefer `dijkstra.shortest_path_int` which is faster.\n"
).
-spec bellman_ford_int(yog@model:graph(any(), integer()), integer(), integer()) -> bellman_ford_result(integer()).
bellman_ford_int(Graph, Start, Goal) ->
bellman_ford(
Graph,
Start,
Goal,
0,
fun gleam@int:add/2,
fun gleam@int:compare/2
).
-file("src/yog/pathfinding/bellman_ford.gleam", 573).
?DOC(
" Finds shortest path with **float weights**, handling negative edges.\n"
"\n"
" This is a convenience wrapper around `bellman_ford` that uses:\n"
" - `0.0` as the zero element\n"
" - `float.add` for addition\n"
" - `float.compare` for comparison\n"
"\n"
" ## Warning\n"
"\n"
" Float arithmetic has precision limitations. Negative cycles might not be\n"
" detected reliably due to floating-point errors. Prefer `Int` weights for\n"
" critical calculations.\n"
).
-spec bellman_ford_float(yog@model:graph(any(), float()), integer(), integer()) -> bellman_ford_result(float()).
bellman_ford_float(Graph, Start, Goal) ->
bellman_ford(
Graph,
Start,
Goal,
+0.0,
fun gleam@float:add/2,
fun gleam@float:compare/2
).