带权有环有向图最长路径求解：货币套利适用算法咨询

你遇到的是典型的汇率套利环检测问题，直接修改Floyd-Warshall或Dijkstra求最长路径不可行的原因是：如果图中存在可套利的正权环，理论上路径收益可以无限叠加，不存在有限的最长路径。这类问题的核心是检测总兑换倍率乘积大于1的闭环，需要将问题转换为最短路径域的负权环检测问题求解，适用算法如下：

• Bellman-Ford算法
  这是这类问题最常用的基础算法，你可以对汇率做对数转换：将边的权重设置为 -ln(汇率)，原问题中路径总乘积大于1的要求，就等价于转换后路径总权重小于0的负权环。Bellman-Ford可以在O(nm)的时间复杂度内（n为货币种类数，m为兑换关系数）检测是否存在负权环，同时支持回溯得到完整的套利路径。
• SPFA（最短路径快速算法）
  是Bellman-Ford的队列优化实现，平均时间复杂度可以降到O(m)，实际运行效率远高于基础Bellman-Ford，适合兑换关系较多的场景，同样支持负权环检测和路径回溯。
• 适配负权环检测的Floyd-Warshall算法
  不需要改求最长路径，直接基于转换后的负权重做迭代，最后判断dist[i][i]（节点i出发回到i的路径总权重）是否小于0即可判断是否存在以i为起点的套利环。时间复杂度为O(n³)，仅适合货币种类较少的场景（一般n小于50都可以流畅运行），优势是可以一次计算得到所有可能的套利环。

Python开发可以直接调用networkx库的现成接口：nx.negative_edge_cycle()可以直接检测负权环，nx.bellman_ford_predecessor_and_distance()可以用来回溯套利路径，不需要手动从零实现算法。

内容的提问来源于stack exchange，提问作者John Adams