Dijkstraは、負でないまたは正の重みに対して機能しますか？

私はDijkstraが負の重みに対しては機能しないが、重量として許容されるのはなぜですか？私は、2つのノードが0の重みを持つ場合、それらのノードを接続するエッジを排除し、ノードを1つにマージすると思います。これは正しいですか？または私は何かを欠いている？Dijkstraは、負でないまたは正の重みに対して機能しますか？

出典

2017-07-29 Intersect

*非負*と*正*が同じであることに注意してください。「0」は正の値です。 – Zabuza

さて、「0」は無署名で正の意味は厳密に私にとって正の意味であると思っています。 – Intersect

それは大丈夫ですが、他の人たちが「Dijkstraは正の重みのために働きます」と言うとき、「0」が正であるため、「0」のために働くことを意味します。 – Zabuza

はい、セグメントの重みがゼロの場合、そのポイントのペア間のすべてのセグメントがゼロであれば削除できます。すべて削除して2つのポイントを1つにマージできます。

この投稿をお寄せください。

出典

2017-07-29 13:10:23 codecrazer

答えを拡張する：通常のDijkstraアルゴリズムはゼロ加重エッジで問題ありません。マージしなくても正しい結果を出力します。 – Zabuza

Dijkstraは、負でないまたは正の重みに対して機能しますか？

答えて

関連する問題