基于Bellman Ford的货币套利：所用图为有向还是无向？

问题背景 #

学习图论及Bellman-Ford算法时，了解到该算法可用于市场套利，但对套利场景所用的图是有向图还是无向图存在疑惑。套利机会的存在依赖负环，而资料显示Bellman-Ford仅适用于含负环的有向图或不含负环的无向图。

遇到如下示例：以rates作为邻接矩阵表示边，currencies作为顶点：

rates = [
    [1, 0.23, 0.25, 16.43, 18.21, 4.94],
    [4.34, 1, 1.11, 71.40, 79.09, 21.44],
    [3.93, 0.90, 1, 64.52, 71.48, 19.37],
    [0.061, 0.014, 0.015, 1, 1.11, 0.30],
    [0.055, 0.013, 0.014, 0.90, 1, 0.27],
    [0.20, 0.047, 0.052, 3.33, 3.69, 1],
]
 
currencies = ('PLN', 'EUR', 'USD', 'RUB', 'INR', 'MXN')

该示例中顶点间看似存在双向边，类似无向图，但Bellman-Ford检测负环需要有向图。现解析此图的类型，若为无向图，说明为何可用于套利的负环检测。

图类型与适用性解析 #

• 本质是有向完全图：示例中的邻接矩阵并非无向图的双向边，而是两组独立的有向边。比如rates[0][1] = 0.23代表从PLN兑换为EUR的汇率，rates[1][0] = 4.34代表从EUR兑换为PLN的汇率——这是两个独立的兑换动作，权重（汇率）也并非严格互为倒数（1/0.23≈4.347，与示例中的4.34存在差异），完全符合有向边的定义。因此这是一个任意两顶点间都存在双向有向边的有向完全图。

• 负环检测的合理性：套利场景中，会将汇率转换为负对数权重（即权重 = -ln(汇率)），此时一条兑换路径的总权重等于路径中所有汇率乘积的负对数。当存在套利机会时，循环兑换后货币增值，意味着汇率乘积>1，对应的总权重<0，即形成负权有向环。Bellman-Ford算法的核心能力就是检测这类负权有向环——由于每个兑换动作都是有方向的，必须用有向图建模才能准确反映交易逻辑，因此完全适配Bellman-Ford的适用场景。

参考文章相关内容翻译 #

Bellman-Ford算法可用于检测货币套利机会，因为套利本质上对应图中的负权环。一旦检测到这样的环，投资者就能通过在环中循环兑换货币实现无风险获利，不过这类无成本的交易机会通常需要快速行动才能抓住。

内容的提问来源于stack exchange，提问作者0xKitsune