algorithm - 两个顶点之间的最小成本的不同行走的数量

Question

我只需要一个想法，如何找到加权有向图中两个顶点之间的所有最小成本行走。我不知道有什么算法可以做到这一点。我正在考虑使用算法来找到成本最低的步行，然后修改顶点的权重，这样如果我再次运行它，它将被迫下次给我另一条路径。但是，如果新的行走使用将要修改的边缘，则此方法将不起作用。

Answer 1

只需使用您最喜欢的最短路径算法并修改relax操作，以便它更新到目标节点的最短路径数量:

# initialization
count(src) = 1
dis(src) = 0
dis(v) = infinity forall v != src

relax(e = (v,w,c)):
  cdis = dis(v) + c
  if cdis < dis(w):
    dis(w) = cdis
    count(w) = count(v)
  else if cdis == dis(w)
    count(w) += count(v)

在算法结束时，count(dst) 将是从源到 dst 的路径数。

显然，在存在零权重循环的情况下，您必须考虑顶点之间存在无限多个不同路径的特殊情况。