LOFTER-网易轻博

Bellman-Ford 是用于处理有负边权的单源最短路径的算法，基本过程是：

1. 初始化各点到其他点的距离到一个数组；

2. 对每一条边进行松弛（Relax）操作；

                                            （算法书对松弛操作的定义）

3. 由于排列组合，每个环路最多进行n-1次，如果还能进行第n次，则证明有负环。

因为算法需要遍历边和结点，时间复杂度为O(E*V)。

---

实际问题：

我们对于不同货币之间汇率应该有一个基本的了解，货币之间的汇率是实时变化的，我们在进行货币之间的兑换时，可以在同一时间将一种货币连续兑换为不同的货币，最后再兑换回来原来的货币，这样是有可能实现货币总量的增加的。

具体：由于货币之间是用乘法来进行转换的，为了方便使用Bellman-Ford算法的松弛操作，我们先将不同货币之间的汇率转换成为负对数形式。

例子汇率，在5月19日获取的数据：

0 RMB

1 USD

2 JPY

3 GBP

4 EUR

在算法中，我们多进行一次Bellman-Ford算法的松弛，正常来说，我们只需进行n-1次算法的松弛操作，而第n-1次是用来判断有无负环的，如果直接进行n次，则可直接将负环放入距离数组中，并可以记录并输出最后的货币兑换路径。

结果：

我们可以看出，从日元兑换英镑再兑换欧元，最后回到日元，每1日元可以获得0.003833的收益，而如果我们用一些别的货币，则存在很真实的问题：如果使用别的货币作为输入，则可以用该货币兑换成日元，并一直使用日元的获利循环来一直获利，当然，如果只需要循环一遍的话，即路径中存在了相同的结点，可以增加一个判断条件使其终止松弛。