グラフの最小パスとは何ですか?
-
08-07-2019 - |
質問
グラフ理論では、最小距離(ダイクストラのアルゴリズムが検出する)と最小経路(これが何であるかわからない)の違いは何ですか?
解決
最小パスは、2つのエッジ間の最小距離をカバーするエッジのセットです。最小距離は、最小パスのエッジ間の距離の合計です。
他のヒント
距離はスカラーです。数。パスは頂点/エッジのペアのリストですか?
最小距離=エッジの重みの最小合計。 最小パス=最小エッジ。
Ie //バンクーバーからカルガリー、レジーナ、そしてウィニペグへと飛ぶ距離は短いですが、バンクーバーからトロントへ、そしてウィニペグへと飛ぶ方が短い経路です。
編集:考えてみてください。
100%確信はありませんが、最小パスは頂点Aから頂点Bへの最小距離パスをトラバースするときに訪れた頂点のリストになるようです。
ソースとシンクのあるネットワークの範囲内でこの質問に答えさせてください。パスがエッジのセットによって定義される最短パスと最小パスを区別したいと思います。
最短経路とは、対応する距離が最短のソースからシンクへの経路です。最小パスは、ソースをシンクに接続する任意のパスです。
i)サイクルが含まれていない。そして
ii)パスからエッジを削除するということは、ソースとシンクの間に接続がなくなることを意味します。
最小距離は最小パスと同じです。
所属していません StackOverflow