DIrected Acyclic Graph shortest path within N steps

I have a problem of finding a shortest path in positively weighted Directed Acyclic Graph, but with the restriction of maximum number of N steps(edges in the path). It is assumed that the path exists. Additional property of the graph is that if the edge (i, j) is in the graph, then any edge (i, k) is also in the graph for i < k < j. I'm only interested in shortest path between start and end of the graph (after topological sorting).

I know that there is an efficient algorithm for the shortest path in Directed Acyclic Graph in O(V+E) but it doesn't account for the steps limit. I can't think of any way to make it O((V+E)*N), but this would be ideal performance, as it should be good enough to handle graphs of 1000 nodes and 100 steps.

For example consider the following graph.

The problem is to find the shortest path using at most k=3 steps (edges). The answer is 6 (path 1->4->5->6).

---

It is actually O(N + M) where N is the number of vertices and M is the number of edges. You can find more information here: http://www.geeksforgeeks.org/shortest-path-for-directed-acyclic-graphs/

Finding the path (I'm using the code from geeksforgeeks): Instead of int dist[V] use pair<int, int> dist[V] . Initially dist[S] = {0, -1} . So in this condition if (dist[i->getV()].first > dist[u].first + i->getWeight()) you need to set parent as dist[i->getV()] = {dist[u].first + i->getWeight(), u} .

Then use this recursive code to restore the path:

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

Call it with restore(FINAL_POINT)

链接地址: http://www.djcxy.com/p/35236.html

上一篇: Dijkstra在有向图上具有负边的算法

下一篇: 在N个步骤内直接绘制非循环图最短路径