回答編集履歴
1
参照リンクの追加
test
CHANGED
|
@@ -1,4 +1,5 @@
|
|
|
1
|
-
ワーシャルフロイド法は
|
|
1
|
+
ワーシャルフロイド法で負の重みがあるときに解が求められるのはループがない時だけです。一周した時に値が負になるループがあると答えが出ません。ループをずっと回っていれば、いくらでも値が減るからです。j -> k -> p -> jと回っても、単にjとpを行ったり来たりしても、いくらでも値が減っていきます。
|
|
2
|
+
英語版Wikipediaの[Floyd–Warshall algorithm]( https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm)の中のBehavior with negative cyclesの項を参照してください (何故か、日本語版にはループの時の記述がない)。
|
|
2
3
|
|
|
3
4
|
リンク先の問題の重みは全て正のようですし、疑問点に書いてある図は、そもそも、どこから来たのでしょう?
|
|
4
5
|
実は有向グラフで、ループができないようになっているとか?
|