c# - 在有向图中找到最大的产品

Question

我的问题类似于寻找最小路径(Dijkstra 算法)，但我想找到从一个节点到任何其他节点的所有边的最大乘积，而不是最短路径。

鉴于所有边都是正权重的，并且每个节点都与相邻节点双向连接，我的理解是这种算法的实现与寻找最短路径正好相反。但我不确定我的想法是否正确，谁能建议我应该从 C# 的哪里开始？ ？

举一个双向连接的例子:

节点:A,B 权重:A->B =2;B->A=1/2

所以一个节点的边的权重总是互惠的

Answer 1

所有权重都是正数，对吗？

1. 将每个权重 W 替换为 log(1/W)。

2. 运行 Bellman-Ford 算法，这是 Dijkstra 对负权重图的扩展。