1

多段グラフ問題については、「FundamentalsofComputerAlgorithms」の本を調べていました。

それは言う：

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ループは頂点の総数に対して実行され、内側の線は近端を選択する必要があることを知っています。

背後にある論理を理解できませんでした

4

1 に答える 1

0

さらに理解を深めるために、ダイクストラのアルゴリズムを有向グラフで見てください。各エッジも1回だけ考慮されます。実行時間はO（| E | + | V lg V |）です。

多段グラフはセットに分割されているため、セットX-1の前に、ターゲットノードへのセットXの頂点にアクセスする必要があることがわかっているため、セットごとに最短経路を見つけることができます。また、同じセット内の頂点の間にエッジがないことも知っています。要するに、あなたはそれらを処理する順序を知っており、Dijsktraのように毎回すべての可能な頂点を考慮する必要はありません

于 2012-03-22T07:00:45.587 に答える