在N个步骤内直接绘制非循环图最短路径
我有一个在正向加权有向无环图中找到最短路径的问题，但是有N个步骤的最大数目（路径中的边）的限制。 假定路径存在。 图的附加属性是，如果边（i，j）在图中，那么对于i <k <j，任何边（i，k）也在图中。 我只关心图的开始和结束之间的最短路径（拓扑排序之后）。
我知道O（V + E）中有向非循环图的最短路径有一个有效的算法，但它没有考虑到步骤的限制。 我想不出有什么方法可以使它成为O（（V + E）* N），但这将是理想的性能，因为它应该足够处理1000个节点和100个步骤的图形。
例如考虑下面的图表。
问题是找到最多使用k = 3个步骤（边缘）的最短路径。 答案是6（路径1-> 4-> 5-> 6）。
它实际上是O(N + M) ，其中N是顶点的数量， M是边的数量。 你可以在这里找到更多的信息：http://www.geeksforgeeks.org/shortest-path-for-directed-acyclic-graphs/
寻找路径（我使用geeksforgeeks中的代码）：而不是int dist[V]使用pair<int, int> dist[V] 。 最初dist[S] = {0, -1} 。 因此，在这种情况下if (dist[i->getV()].first > dist[u].first + i->getWeight())您需要将父项设置为dist[i->getV()] = {dist[u].first + i->getWeight(), u} if (dist[i->getV()].first > dist[u].first + i->getWeight()) 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)调用它restore(FINAL_POINT)