DIrected Acyclic Graph shortest path within N steps

Question

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).

@SaeedAmiri The problem is to get a shortest path within N steps(edges used for the path), not just a shortest path... — kuba1024g
As it is written the problem asks for path of length at most N, and later it is promised that such path exists, if such path exists then certainly shortest path has length at most N. — Saeed Amiri

Rasul Kerimov Rasul Kerimov · Accepted Answer · 2017-02-05T19:35:56

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)

DIrected Acyclic Graph shortest path within N steps

1 Answers