algorithm - グラフの最小パスとは?

Question

グラフ理論では、最小距離 (ダイクストラのアルゴリズムが検出する) と最小パス (それが何であるかはわかりません) の違いは何ですか?

score 6 · Accepted Answer

最小パスは、通過したときに 2 つのエッジ間の距離が最小になるエッジのセットです。最小距離は、最小パスのエッジ間の距離の合計です。

score 2 · Accepted Answer

2

距離はスカラーです。数。パスは頂点/エッジのペアのリストですか?

于 2008-11-13T21:29:08.710 に答える

score 1 · Accepted Answer

ソースとシンクを持つネットワークの範囲内でこの質問に答えさせてください。パスが一連のエッジによって定義される場合、最短パスと最小パスを区別したいと思います。

最短パスとは、対応する距離が最も短いソースからシンクへのパスです。最小パスは、ソースをシンクに接続する任意のパスにすることができます。

i) サイクルを含まない。と

ii) パスからエッジを削除すると、ソースとシンクの間に接続がなくなります。

score 1 · Accepted Answer

最小距離 = エッジの重みの最小合計。最小パス = 最小エッジ。

つまり// バンクーバーからトロント、そしてウィニペグに飛ぶのはより短い経路ですが、バンクーバーからカルガリー、レジーナ、そしてウィニペグに飛ぶのはより短い距離です.

編集：私が思うにそれをひっくり返します。

score 0 · Accepted Answer

100% 確実ではありませんが、最小パスは、頂点 A から頂点 B への最小距離パスをたどるときに訪れた頂点のリストのように思えます。

score -2 · Accepted Answer

-2

最小距離は最小パスと同じです。

于 2008-11-13T20:57:51.453 に答える

6 に答える 6