python - 加权循环有向图中的最长路径

Question

堆栈溢出！

我正在尝试创建套利策略，以更好地了解如何使用图表。我正在使用python。
图形：

表格格式：

任务：找到我们将获得最大利润的货币交易路径。例如：USD->EUR(0.75), EUR->GBP(2),GBP->USA(0.7): 0.75*2*0.7=1.05，所以我们得到 5% 的利润。

我认为我可以修改 Floyd-Warshall 算法或 Dijkstra 算法来找到不是最短但最长的路径。但它失败了......
这些任务使用什么算法？

标签： pythonalgorithmnetworkxgraph-theory

Answer 1

最昂贵的路径由

• 找到最昂贵的边缘
• 在边缘上循环 E
  • 从 E 的成本中减去最昂贵边的成本
  • 将边缘成本设置为绝对值
  • 结束循环
• 遍历所有顶点对
  • 应用 Dijkstra 并保持最佳效果。
  • 结束循环