3

私はこの問題の解決に取り組んでいます：

ゲーデル教授は、ダイクストラのアルゴリズムを実装していると主張するプログラムを作成しました。プログラムは、Vの各頂点vに対してvdとv.πを生成します。教授のプログラムの出力をチェックするために、O。（V + E）時間アルゴリズムを与えます。d属性とπ属性がいくつかの最短経路ツリーの属性と一致するかどうかを判断する必要があります。すべてのエッジの重みは負ではないと想定できます。

vdは、開始ノードからvvまでの最短距離です。vvπは、開始ノードからvまでの最短経路におけるvの先行です。

私の考えは次のとおりです。すべての頂点（i）について、idを（i.π）.dと比較します。iの前任者のd値が大きい場合、最短経路ツリーを作成することはできません。

これにより、教授の出力が最短経路ツリーではないかどうかを確認できると思いますが、出力が最短経路ツリーであるかどうかは確認できないと思います。これ以上の情報がなければ、これを行う方法を考えることはできません。

私は正しい方向に進んでいますか？

4

1 に答える 1

3

私はこれがうまくいくと思う

DFS を実行しますが、通常のグラフ エッジを追跡する代わりに、各頂点の π 値のみを追跡します。トポロジー順序付けを生成するためにこれを行っているため、最初に終了する頂点がトポロジー順序付けの最初の頂点になります。生成する topo ソートの最初の頂点は、Gaedel のアルゴリズムに与えられた「ソース」頂点になることに注意してください。

トポの順序付けができたので、DAG で行う場合と同様に、エッジを最も効率的な順序で緩和できます。

for each v in topoSortedVerts
    if v.d_verify != v.d_Gaedel
        //fail

    for each u in v.adjacencies
        relax(v, u)

if v.d_verify != v.d_Gaedel
    //fail

すべての V 頂点が考慮され、ソース頂点が一致していることも確認する必要があると思います。多分。また、π値によって引き起こされたゲーデルの前身のサブグラフは、実際にジャッキアップされ、あらゆる種類のクレイジーな問題が発生する可能性があると思いますが、そうではないと思います。

これはO(V + E)、外側のループの実行時間と、集約分析を使用しVた内側のループの実行時間によるものです。E

于 2012-11-26T06:06:05.877 に答える