固定边数的最短路径 [英] Shortest path with a fixed number of edges

问题描述

在有效时间内找到通过图的最短路径，并附加约束，即该路径必须精确地包含 n 个节点.

Find the shortest path through a graph in efficient time, with the additional constraint that the path must contain exactly n nodes.

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

We have a directed, weighted graph. It may, or may not contain a loop. We can easily find the shortest path using Dijkstra's algorithm, but Dijkstra's makes no guarantee about the number of edges.

我们能想到的最好的方法是保留一个节点的n条最佳路径的列表，但这要比Vanilla Dijkstra占用大量的内存.

The best we could come up with was to keep a list of the best n paths to a node, but this uses a huge amount of memory over vanilla Dijkstra's.

推荐答案

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

It is a simple dynamic programming algorithm.

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

Let us assume that we want to go from vertex x to vertex y.

制作一个表D [.，.]，其中D [v，k]是从根到顶点v的最短路径k的开销.

Make a table D[.,.], where D[v,k] is the cost of the cheapest path of length k from the root to the vertex 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]中.

The cost of the cheapest path will then be stored in D[y,n].

如果我们有一个边数较少的图，则可以通过仅搜索v连接到的u来有效地做到这一点.最好使用邻接表数组来完成此操作.

If we have a graph with fewer edges, we can do this efficiently by only searching over the u that v is connected to. This can be done optimally with an array of adjacency lists.

要恢复最便宜的路径:

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.

The last node is y. The node before that is P[y,n]. We can keep following backwards, and we will eventually arrive at P[v,2] = x for some v.

这篇关于固定边数的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！