N步内有向无环图最短路径

Question

在正加权有向无环图中，我有一个求最短路径的问题，但有最大N步（路径中的边）的限制。假定路径存在。图的另一个性质是，如果边（i,j）在图中，那么对于i

例如，考虑下图。

问题是最多使用k=3步（边）来寻找最短路径。答案是6（路径1->4->5->6)。

Answer 1

它实际上是O(N+M)，其中N是顶点数，M是边数。您可以在以下网站找到更多信息：http://www.geeksforgeeks.org/storest-path-for-directed-acyclip-graphs/

查找路径（我使用的是geeksforgeeks中的代码）：不使用int dist[V]，而是使用pair dist[V] 。最初dist[S]={0,-1}。因此，在此条件下if(dist[i->getv()].first>dist[u].first+i->getweight())，您需要将parent设置为dist[i->getv()]={dist[u].first+i->getweight(),u}。

然后使用这个递归代码恢复路径：

void restore(int v) { 
   if(dist[v].second == -1) return;
   else answer.push_back(v);
   if(v == START_POINT) return;
   restore(dist[v].second);
}

用restore(FINAL_POINT)调用它