我正在解决这个问题，我们有一个图，并试图从节点 1 到节点 N。边权重是“成本”，每条边也有一个“流量”值。对于从节点 1 到节点 N 的任何路径，总成本将是路径上所有边的成本之和，流量将是边中的最小流量值。我们希望最大化流量/成本的比率。
我的想法是使用 Dijkstra 找到从 1 到 N 的最小成本路径，当我尝试以这种方式找到路径时，我意识到我没有考虑流量。我想执行修改后的 Dijkstra，在计算最佳路径时我会考虑每条边的流量，但我不确定如何执行此操作。
我应该通过减去或增加额外的流量来操纵边缘成本，还是因为我们正在查看比率而这不起作用？
我也尝试通过 BFS 找到每条路径，但有时间限制，我也无法做到这一点。
谁能给我一些关于如何解决这个问题的提示？
编辑:
一个例子是有 3 个节点，1、2 和 3。1 和 2 的边成本为 2，流为 4。2 和 3 的边成本为 5，流为 3。在这个例子中，从 1 到 N 只有一条路径。它的流量是 min(3,4)=3，它的成本是 2+5=7。所以比例是3/7。但在大多数情况下，我们会有几种可能的路径。
最佳答案
遵循 Dijkstra 算法并为每个节点 v 维护一个距离标签 D[v](像往常一样)，以及一个额外的流标签 F[v]。目标是最大化比率 F[v]/D[v]。算法接下来应该选择的顶点 u 是使该比率最大化的顶点。
然后，在松弛任何入射边 e=(u,v) 期间，执行以下计算以查看从起始顶点到使用 u 作为中间顶点的 v 的新可能路径的比率是否比之前找到的任何路径都好小路。
// relaxing edge e = (u,v)
newDistance = min{ D[u], D[v] + cost(e) }
newFlow = min{ F[u], flow(e) }
if ( (newFlow / newDistance) > (F[v] / D[v]) )
v.parent = u
F[v] = newFlow
D[v] = newDistance
关于algorithm - 使用 Dijkstra 时如何加权其他因素，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/59331663/