具有固定边数的最短路径

Question

在有效的时间内找到通过图形的最短路径，附加约束是该路径必须恰好包含 n 个节点。

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

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

Answer 1

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

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

制作一个表 D[.,.]，其中 D[v,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] 中。

如果我们有一个边较少的图（稀疏图），我们可以通过仅搜索 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]。我们可以继续向后跟踪，最终将得到 v 的 P[v,2] = x。

Answer 2

我想到的替代方案是深度优先搜索（与 Dijkstra 的广度优先搜索相反），修改如下：

• 如果超过所需的顶点数，则停止“深度”

• 记录具有正确节点数的最短找到的（迄今为止）路径。

运行时间可能很糟糕，但它应该在使用非常合理的内存量的情况下得出正确的结果。

Answer 3

有趣的问题。您是否讨论过使用启发式图搜索（例如 A*），为超过或低于节点数添加惩罚？这可能会也可能不会被接受，但如果它确实有效，它可能比保留所有潜在路径的列表更有效。

事实上，您也许可以使用回溯来限制您讨论的 Dijkstra 变体所使用的内存量。

Answer 4

算法的大致思路：

设 A 为起始节点，设 S 为一组节点（加上一条路径）。不变的是，在步骤 n 结束时，S 将是距离 A 正好 n 步的所有节点，并且路径将是该长度的最短路径。当 n 为 0 时，该集合为 {A（空路径）}。给定步骤 n - 1 处的这样一个集合，您可以从一个空集合 S1 开始到达步骤 n，并且

for each (node X, path P) in S
  for each edge E from X to Y in S, 
    If Y is not in S1, add (Y, P + Y) to S1
    If (Y, P1) is in S1, set the path to the shorter of P1 and P + Y

只有 n 个步骤，并且每个步骤应小于 max(N, E)，这使得
对于稠密图，整个算法为 O(n^3)；对于稀疏图，整个算法为 O(n^2)。

该算法取自 Dijkstra 算法，尽管它是一种不同的算法。

Answer 5

假设我们想要 k 步骤中从节点 x 到 y 的最短距离
简单的 dp 解决方案是

A[k][x][y] = min over { A[1][i][k] + A[t-1][k][y] }
k 从 0 到 n-1 变化

A[1][i][j] = r[i][j]; p[1][i][j]=j;
for(t=2; t<=n; t++)
for(i=0; i<n; i++) for(j=0; j<n; j++)
{
A[t][i][j]=BG; p[t][i][j]=-1;
for(k=0; k<n; k++) if(A[1][i][k]<BG && A[t-1][k][j]<BG)
if(A[1][i][k]+A[t-1][k][j] < A[t][i][j])
{
A[t][i][j] = A[1][i][k]+A[t-1][k][j];
p[t][i][j] = k;
}
}

trace back the path
void output(int a, int b, int t)
{
while(t)
{

cout<<a<<" ";
a = p[t][a][b];
t--;
}
cout<<b<<endl;
}