具有固定边数的最短路径

Question

通过图表在有效时间内找到最短路径,其中附加约束条件路径必须包含n个节点.

我们有一个有向加权图.它可能包含也可能不包含循环.我们可以使用Dijkstra算法轻松找到最短路径,但Dijkstra不能保证边缘数量.

我们能想到的最好的方法是保留一个节点的最佳n路径列表,但这比vanilla Dijkstra的内存使用了大量内存.

Answer 1

它是一种简单的动态编程算法.

让我们假设我们想要从顶点x到顶点y.

制作表D [.,.],其中D [v,k]是从根到顶点v的最短路径长度为k的成本.

Initially D[x,1] = 0. Set D[v,1] = infinity for all v != x.
For k=2 to n:
  D[v,k] = min_u D[u,k-1] + wt(u,v), where we assume that wt(u,v) is infinite for missing edges. 
  P[v,k] = the u that gave us the above minimum.

然后将最便宜路径的成本存储在D [y,n]中.

如果我们有一个边缘较少的图形,我们可以通过仅搜索v所连接的u来有效地完成此操作.这可以通过一系列邻接列表以最佳方式完成.

要恢复最便宜的路径:

Path = empty list
v = y
For k= n downto 1:
  Path.append(v)
  v = P[v,k]
Path.append(x)
Path.reverse()

最后一个节点是y.之前的节点是P [y,n].我们可以继续跟进,我们最终会得到P [v,2] = x一些v.