Module bellman_ford 

Bellman-Ford algorithm with SPFA optimization for simulation-driven routing.

Runs actual pool simulations (get_amount_out()) during edge relaxation to find optimal A-to-B routes that account for slippage, fees, and pool mechanics at the given trade size.

Key features:

• Gas-aware relaxation: When token prices and gas price are available, relaxation compares net amounts (gross output minus cumulative gas cost in token terms) instead of gross output alone. Falls back to gross comparison when data is unavailable.
• Subgraph extraction: BFS prunes the graph to nodes reachable within max_hops
• SPFA (Shortest Path Faster Algorithm) queuing: Only re-relaxes edges from nodes whose amount improved
• Forbid revisits: Skips edges that would revisit a token or pool already in the path

Known limitation: SPFA order-dependence

SPFA reads and writes the same amount[] array within a round (unlike textbook Bellman-Ford which snapshots between rounds). Processing node B before node C can update intermediate amounts that C then builds on, producing different routes depending on iteration order. Active nodes are sorted by NodeIndex for determinism, but the chosen ordering is not guaranteed to find the globally optimal route. A proper fix would be to snapshot amounts between rounds or use a priority-based processing order.

Structs

BellmanFordAlgorithm

Bellman-Ford algorithm with SPFA optimisation for simulation-driven DEX routing.