マルチステージグラフの複雑さ

Question

多段階グラフ問題の「コンピュータアルゴリズムの基礎」の本を見ていました。

それは言う：

Algorithm Graph(G,k,n,p) 
{ 
cost[n]=0; 
for j=n-1 to 1 step -1 do 
{ 
Let r be a vertex such that<j,r> is an edge of G and c[j,r]+cost[r] is minimum 
cost[j]=c[j,r]+cost[r] 
} 
} 

著者は複雑さがOであることを述べている（| V | + | E |）。 | V |は頂点の数であり、| E |エッジの数です。

私は、forループの数が頂点の総数であり、内側の線が近い辺を選択しなければならないことを知っています。

私はabritrary有向グラフ上Dijsktraのアルゴリズムを見て、あなたの理解を促進するために

Answer 1

の後ろの論理を理解できなかった、各エッジだけのようにも一度考えられています。実行時間はO（| E | + | V lg V |）です。

多段グラフは集合に分割されているため、X-1を設定する前にターゲットノードへの集合Xの頂点を訪問しなければならないことが分かっているため、最短経路を求めることができます。また、同じセット内の頂点には互いにエッジがないこともわかります。要するに、それらを処理する順序を知っていて、Dijsktraのようにすべての可能な頂点を考慮する必要はありません