如果给我一个具有货币转换率的数据结构：
具有汇率的货币关系列表。(人民币-美元(
那么我如何找到从1到2的最佳汇率呢？
我的思考过程：方法1:
如果我取交换值的列表并将其转换为图邻接列表和权重列表(因为这看起来像是一个加权图问题(，我可以使用DFS找到所有可能的路径，然后跟踪生成最高汇率的路径(所以我会乘以路径中的每个转换率并存储它。每当路径生成更好的转换率时，我都会更新这个变量，因此我有最大值(
请评论此算法的正确性。我的想法正确吗？这会产生正确的结果吗？
我马上看到的一个问题是，这是非常低效的，因为它需要指数级的时间。
方法2：我可以否定所有的转换并使用Bellman-Ford吗？由于Bellman Ford被用来在加权图中寻找成本最低的路径。
谢谢。非常感谢任何指导
你的直觉是正确的-你可以使用DFS，它会给你最好的汇率(按权重计算的最短路径(，但对于大型图来说，它会非常慢。
你的第二种方法(贝尔曼·福特(是一个更好的主意。正如你所提到的，你必须乘以汇率/边缘权重，而不是将它们相加，但这不会带来任何问题。
我想你已经解决了这个问题，但对于未来引用这个问题的人来说，你不能使用Dijkstra的算法，也不能像A*那样使用它的后代，因为这个图在精神上有负循环。你可以找到一个低于1的兑换率，并可能利用它来获得总体较低的最低兑换率(然后你只需将两种货币倒置，就可以获得相反方向的最高兑换率(。
数学题外话：
一种更清楚地看到这一点的方法——假设我们有几个兑换率，在3对货币之间——A、B和C。假设单元检出，则这三个交换机之间的总转换率R将为R = A * B * C。另一种写法是R = e ^ log(A * B * C)，其中e是欧拉数，log()是自然对数(我们也可以使用10和log10()，或任何其他基数(。用对数规则重写，我们可以得到R = e ^ (log(A) + log(B) + log(C))，最后得到log(R) = log(A) + log(B) + log(C)。
现在，如果我们不关心R的实际值，只关心哪个最大/最小(或者我们愿意进行一些求幂运算来得到它(，我们就可以满足于计算log(R)，或者汇率的对数。这样做的好处是，权重在转换为对数时，是加在一起，而不是乘以。这使我们能够在不改变的情况下使用图算法的传统实现(我们只给它们log(weight)而不是weight(。如果我们试图给它一些通常在0和1之间的东西，我们会看到log(x)实际上变成了负的，暴露了该边缘的真实性质，以及它可能产生的潜在负循环。
摘要
你可能想要使用Bellman-Ford，用乘法代替加法应该没问题。如果您手头有一个现有的实现，但它使用加法来组合边权重，那么您可以通过将边权重的log()传递给它来轻松作弊，事情就会成功；"自动"；。