我有货币列表和汇率表。给定1单位某种货币，我需要查找兑换交易清单以获取其他货币的最大金额。我知道没有任何周期可以让我通过套利来致富。
我将此问题转换为图形问题。每种货币都是一个顶点，可能的交换交易是边缘。边的权重减去汇率的对数，因此问题被转换为最短路径问题（对数总和的负数的最小值类似于最大化乘法）现在执行Belman-Ford并从中找到最佳路径我对任何顶点（货币）的来源。运行时间为O（n ^ 3）
我的问题是，有没有更好更快的算法？
谢谢！
罗恩
我有货币列表和汇率表。给定1单位某种货币，我需要查找兑换交易清单以获取其他货币的最大金额。我知道没有任何周期可以让我通过套利来致富。
我将此问题转换为图形问题。每种货币都是一个顶点，可能的交换交易是边缘。边的权重减去汇率的对数，因此问题被转换为最短路径问题（对数总和的负数的最小值类似于最大化乘法）现在执行Belman-Ford并从中找到最佳路径我对任何顶点（货币）的来源。运行时间为O（n ^ 3）
我的问题是，有没有更好更快的算法？
谢谢！
罗恩