3

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

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

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

4

5 回答 5

8

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

让我们假设我们想要从 vertexx到 vertex y。

做一个表格D[.,.]，哪里是从起始顶点到顶点D[v,k]的最短路径的成本。kxv

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那个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。

于 2010-02-09T06:53:35.167 回答
0

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

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

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

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

于 2009-11-06T21:03:26.410 回答
0

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

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

于 2009-11-06T21:09:47.673 回答
0

一个算法的粗略想法：

令 A 为起始节点，令 S 为一组节点（加上一条路径）。不变的是，在第 n 步结束时，S 将所有距 A 正好 n 步的节点，并且路径将是该长度的最短路径。当 n 为 0 时，该集合为 {A (empty path)}。在第 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 的，尽管它是一个不同的算法。

于 2009-11-06T22:11:59.560 回答
-1

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

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;
}
于 2013-02-16T17:47:00.243 回答