具有固定边数的最短路径

在高效的时间内找到通过图形的最短路径，并附加该路径必须完全包含的约束n nodes.

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

我们能想到的最好的办法是保留一个节点的最佳 n 条路径的列表，但这比普通 Dijkstra 占用了大量的内存。

这是一种简单的动态规划算法。

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

做一个表D[.,.], where D[v,k]是长度最短路径的成本k从起始顶点x到顶点v.

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] 中。

如果我们有一个边较少的图（稀疏图），我们可以通过仅搜索来有效地做到这一点u that v连接到。这可以通过邻接列表数组来最佳地完成。

恢复最短路径：

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.