0

最大コスト エッジと最小コスト エッジの差が最小になるグラフで、ソースからシンクへのルートを見つける必要があります。

再帰的なソリューションを使用しようとしましたが、サイクルの状態で失敗し、変更されたダイクストラも失敗しました。

すべてのルートを見つけて最小値を見つける必要がないアルゴリズムはありますか?

4

2 に答える 2

1

ソースとシンクが接続されるまで、次のエッジ (重みが大きいか等しいエッジ) を追加し、ソースとシンクを更新します。次のように、最後のエッジとの差で答えてください。

    ans = INFINITE
    for each Edge e1 in E (sorted by weight in non-decreasing order)
        clear the temporal graph
        for each Edge e2 in E
            if e2.weight >= e1.weight  
                add e2 to the temporal graph
                if sink and source are connected in the temporal graph
                    ans = min(ans, e2.weight - e1.weight)
                    break
    print ans

UNION-FIND 構造を使用してエッジを追加し、ソースとシンクの間の接続を確認すると、全体の時間が O(edges^2) になるはずです。

于 2017-08-08T03:25:40.797 に答える
-1

OK、グラフができたので、あるノード (ソース) から別のノード (シンク) へのパスを見つけて、パスの最大エッジ ウェイトからパスの最小エッジ ウェイトを引いた値が最小になるようにする必要があります。グラフが有向かどうか、エッジの重みが負になる可能性があるかどうか、またはサイクルがあるかどうかはわかりません。したがって、これらすべての質問に対する答えが「はい」であると仮定しましょう。

パスの「スコア」(エッジの重みの最大差) を計算すると、これらはパスの距離に似ていることがわかります。A から B へのパスのスコアが高い (望ましくない) または低い (望ましい) 場合があります。パス スコアをパスの重みのように扱うと、新しいエッジを追加してパスを構築すると、パス スコア (= 重み) は増加するだけであることがわかります。 =1 および weight(B->C)=5 の場合、パス スコアは 4 になります。エッジ C->D をパス A->B->C に追加すると、パス スコアは増加するか、同じままになります。最小エッジ ウェイトと最大エッジ ウェイトの差が 4 未満になることはありません。

これらすべてからの結論は、負のエッジのないグラフで最適なパスを探しているかのように、最適なパスを探してグラフを探索できるということです。ただし、サイクルが発生する可能性があります (説明されている接続性を考えると、発生する可能性があります)。これは、適切に実装されたダイクストラのアルゴリズムが、現在わかっているこのグラフのトポロジに対して最適なパフォーマンスを発揮することを意味します。

完全なグラフ探索なしに解決策なし

グラフ全体を調査しなくても、どのエッジが最適なパスに属すべきかについて局所的に適切な決定を下すことができると誤解される可能性があります。次のサブグラフは、この問題を示しています。

ここに画像の説明を入力

A から F へのパスが必要で、ノード B にいるとします。既知のすべてを考えると、パス スコアが最小になる C へのパスを選択します。(まだ) わかっていないことは、そのパスの次のエッジによって、このパスのスコアが大幅に増加することです。エッジ B->D を最適なパスの次の要素として選択することがわかっている場合。

于 2013-04-02T04:38:32.087 に答える