最短経路で使用されるエッジ

-1

"最短経路アルゴリズム"を学習しました。今、私は最短経路グラフがどのように見えるか疑問に思っています。最短経路で使用されるエッジ

I.e.私はノードNにいるので、ここから最短経路アルゴリズムを実行しました。ですから、最短経路アルゴリズムで使用されるエッジを使ってグラフを作成すると、グラフはどのように見えますか？

グラフは、ルートがTreeで、Nであり、ルートと他のノードとの間のパスが最短であると思います。

2016-10-19 DreamWorks

はいあなたが正しいですが、グラフは基本的に私はあなたの仮定がほとんど保持すると思うルートN –

と（スパニングツリーと呼ばれる）ツリーを形成しています。しかし、コストが同じ複数のパスを持つグラフや、負のサイクルのグラフではさらに複雑なものになることがあります。 – Binus

基本的に、最短パスから作成されたサブグラフが表示されている場合、それはツリー、実際にはスパニングツリーになります。同様の特性を持つことになります。私が投稿したリンクを参照してください。

接続され、無向グラフGは、頂点vを根と最短経路ツリーはGのスパニングツリーT、Tの任意の他の頂点UにルートVから経路距離は、であることで考えるとG.
におけるVからUへの最短経路距離

参照

shortest-path-tree

Spanning Tree。

shortest ptah tree.pdf

2016-10-19 06:16:56 v78

確かに、それは答えではありません、あなたが落としたのはちょうど2つのリンクです – Rerito

@Rerito、彼は私の答えを受け入れました。これで十分ではないと思わないなら、より良い方法で答えることでやる方法を教えてください。 – v78

[このリンク]（http://meta.stackexchange.com/q/225370/284827）を参照してください。 –

答えて