有向图的最大加权路径

Question

关于这个问题，我有一个问题：

设c1，c2，.，cn为不同货币。1美元的ci可以用cj货币购买w_ij>0美元。考虑到所有的汇率，我们想找出购买货币cn的最佳方式，从货币c1开始。

1. 最优汇率总是存在的吗？
2. 在最优汇率存在的情况下，设计了一种多项式时间算法来确定最优汇率。

基本上，我们要做的是找到一条从ci到cj的最大重量的路径，对吗？我想做一些类似拓扑排序的工作，但问题是ci和cj之间有两条路，一条是从ci到cj的值w_ij，另一条是从cj到值为1/w_ij的ci。我该如何解决这个问题？

Answer 1

考虑一个边权值为-log w_ij的有向图。图中从c_i到c_j的最短路径对应于从c_i开始购买c_j的最佳方式。

如果图有负循环，那么就没有最短的(非简单的)路径，也没有购买货币的最佳方法:总是有一个更好的方法，能更好地在循环中来回走几次。

Bellman算法在多项式时间内工作.如果有负循环，它可以报告一个负循环，如果没有这样的循环，它可以找到最短的路径。

Answer 2

为了计算一个节点的最大路径，我们计算每个其他节点的权重乘积从当前节点到另一个节点的最大路径值(递归计算)，然后选择最大的这样的乘积。

def maxPath(weights):

  def _maxPath(i):
    if path_nodes.get(i):
      return 0
    elif i==n-1:
      return 1
    path_nodes[i]=1

    max_path=0
    for j in range(0, n):
      cur_path=weights[i][j]*_maxPath(j)
      if cur_path>max_path:
        max_path=cur_path

    del path_nodes[i]
    return max_path

  n=len(weights)
  path_nodes = {}
  return _maxPath(0)

def main():
  weights=[[1,2,3],[0.5,1,4],[0.33, 0.25, 1]]
  print(weights)
  print(maxPath(weights))