有向图中的最大权重路径

Question

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

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

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

基本上，我们要做的是找到一条从ci到cj的最大权重路径，对吧？我正在考虑使用拓扑排序之类的东西，但问题是在ci和cj之间有两条路径，一条从ci到w_ijcj，另一条从cj-至ci值1/w_ij

Answer 1

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

如果图表有一个负循环，那么就没有最短（非简单）的路径，也没有购买货币的最佳方式：总有一种更好的方式对应于在循环中多走几次。

Bellman-Ford算法适用于多项式时间。如果存在负循环，它可以报告负循环，如果没有负循环，则可以找到最短路径。

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))