Nステップ内の非巡回グラフ最短パス

Question

正の重み付け有向無巡回グラフで最短パスを見つけることができますが、Nステップの最大数（パス内の辺）の制限があります。パスが存在するものとします。グラフの追加の特性は、エッジ（i、j）がグラフ内にある場合、任意のエッジ（i、k）もi < k < jのグラフにあることである。私は、グラフの開始と終了の間の最短経路（トポロジカルソート後）にのみ興味があります。

O（V + E）の有向無作為グラフで最短パスの効率的なアルゴリズムがあることはわかっていますが、ステップの制限を考慮していません。私はそれをO（（V + E）* N）にする方法は考えていませんが、1000ノードと100ステップのグラフを扱うのに十分なはずです。

たとえば、次のように考えてください。 graph

問題は、最大k = 3ステップ（エッジ）を使用して最短経路を見つけることです。答えは6です（パス1-> 4-> 5-> 6）。

Answer 1

実際にはO(N + M)です。ここで、Nは頂点の数であり、Mはエッジの数です。 http://www.geeksforgeeks.org/shortest-path-for-directed-acyclic-graphs/

パスを（私はgeeksforgeeksからのコードを使用しています）検索： の代わりにint dist[V]使用pair<int, int> dist[V] あなたはここでより多くの情報を見つけることができます。最初はです。したがって、この状態では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); 
} 

問題は、N段階（パスに使用エッジ）内の最短経路を取得することはないrestore(FINAL_POINT)