最长/最短路径算法

用于实现最长（和最短）路径算法的算法。路径成本通过求和或相乘边权重来计算。

Floyd-Warshall

Floyd-Warshall 算法能够计算最长路径（即最盈利的交易）计算，尽管代价是 $O(n^3)$。

对于基于乘法的权重，我们利用了乘积最大化等价于权重对数最大化的事实，即：$x*y = 2^{log2(x) + log2(y)}$。

对于最长路径，权重已乘以 $-1$ 并在最短路径算法中重用。

注意： Floyd-Warshall 可以检测负路径环（即无限套利机会），这会导致忽略最新的价格更新。待定 - 删除受影响的边以消除负环...

Floyd-Warshall 计算器的示例使用。所有价格均为 $10^{12}$，包括自引用，例如 BNB -> BNB 的成本为 $10^{12}$

use best_path::prelude::*;
use best_path::prelude::floyd_warshall::calculator::FloydWarshallCalculator;

let in_graph = &[
    (
        ProviderPair { pair: Pair { source: "BNB".to_owned(), target: "USDT".to_owned() }, provider: "CRYPTO_COMPARE".to_owned() },
        364_190_000_000_000_u128
    ),
    (
        ProviderPair { pair: Pair { source: "USDT".to_owned(), target: "ETH".to_owned() }, provider: "COINGECKO".to_owned() },
        2_745_000_000_u128
    ),
];
let res_out = FloydWarshallCalculator::calc_best_paths(in_graph);
let as_nodes = res_out.unwrap().into_iter().collect::<Vec<(_, _)>>();
let res_ref = res_out.as_ref().unwrap();
// multi-hop path path
assert_eq!(
    &PricePath { total_cost: 999_701_550_000_u128, steps: vec![
        PathStep { pair: Pair { source: "BNB".to_owned(), target: "USDT".to_owned() }, provider: "CRYPTO_COMPARE".to_owned(), cost: 364_190_000_000_000_u128 },
        PathStep { pair: Pair { source: "USDT".to_owned(), target: "ETH".to_owned() }, provider: "COINGECKO".to_owned(), cost: 2_745_000_000_u128 }
    ] },
    res_ref.get(&Pair { source: "BNB".to_owned(), target: "ETH".to_owned() }).unwrap()
);
// 1 hop path, based on input ProviderPair
assert_eq!(
    &PricePath { total_cost: 364_190_000_000_000_u128, steps: vec![
        PathStep { pair: Pair { source: "BNB".to_owned(), target: "USDT".to_owned() }, provider: "CRYPTO_COMPARE".to_owned(), cost: 364_190_000_000_000_u128 }
    ] },
    res_ref.get(&Pair { source: "BNB".to_owned(), target: "USDT".to_owned() }).unwrap()
);
// path to self, note cost is still in scale 10^12
assert_eq!(
    &PricePath { total_cost: 1_000_000_000_000_u128, steps: vec![] },
    res_ref.get(&Pair { source: "BNB".to_owned(), target: "BNB".to_owned() }).unwrap()
);

组件内的实用程序

Best-path 作为 best-path-pallet 的最佳交易发现机制。