質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.48%
Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Q&A

解決済

5回答

978閲覧

ワーシャルフロイド法がなぜ2点間で最短といえるのか

Logarithm

総合スコア80

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

0グッド

0クリップ

投稿2022/09/22 14:30

編集2022/09/22 16:07

前提

競プロをしている際に気になったので。
解いていた問題(ABC051 D問題)

ワーシャルフロイド法の理解

自分の理解では始点iから終点jまで点kを経由して経由した場合現時点での最短距離よりも短ければ更新(DPと同じ)する。
という手順と理解しています。

疑問点

なぜ、点kという一点のみ経由しただけで始点iと終点jの最短経路と言えるのでしょうか?
もし、以下の画像のように点kの先に点pがあった場合、
i → k → p → j
という経路が最も重みが少なくなるように思うのですが。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答5

0

「始点iから終点jまで点kを経由して経由した場合現時点での最短距離よりも短ければ更新(DPと同じ)する。」の点kは固定された点ではなく、全ての点をkとした場合を試します。
ワーシャルフロイド法のアルゴリズムをもう一度確認してください。

通常は、各頂点から直接行ける点への距離辺の長さとし、直接行けないところは無限大とし、自身へは0として初期化し、全ての頂点を順にkとした場合の、kを経由した場合の距離を算出して、「始点iから終点jまで点kを経由して経由した場合現時点での最短距離よりも短ければ更新(DPと同じ)する。」のです。

投稿2022/09/23 15:21

TakaiY

総合スコア12749

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

ベストアンサー

Dijをk経由で評価してその時のDik+Dkjである40で更新した後に、Dkjはp経由評価がかかって-480とかになったらDijはどうなるんだ、最短ではないだろう、という話と思います。
その場合、Dipがk経由評価で40をもらっているはずなので、p経由評価でDijが-460になります。経路はikpj。
負の重みを持っていることにより、経由評価の順序によってはDipはj経由評価で-400をもらうので、そのばあいはDijは-900になります。経路はijpj。

投稿2022/09/22 21:56

matukeso

総合スコア1590

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

ワーシャルフロイド法で負の重みがあるときに解が求められるのはループがない時だけです。一周した時に値が負になるループがあると答えが出ません。ループをずっと回っていれば、いくらでも値が減るからです。j -> k -> p -> jと回っても、単にjとpを行ったり来たりしても、いくらでも値が減っていきます。
英語版WikipediaのFloyd–Warshall algorithmの中のBehavior with negative cyclesの項を参照してください (何故か、日本語版にはループの時の記述がない)。

リンク先の問題の重みは全て正のようですし、疑問点に書いてある図は、そもそも、どこから来たのでしょう?
実は有向グラフで、ループができないようになっているとか?

投稿2022/09/22 18:04

編集2022/09/24 01:43
Bearded-Ockham

総合スコア430

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

Logarithm

2022/09/23 15:35

ワーシャルフロイド法の勉強中には負の重みでも最短経路が分かると書いてあったので、上記の画像の時反例っぽいと思ったので自分で画像を書きました。
guest

0

i→j→k→pでは、「始点iから終点jまで」という条件を満たしていません。

投稿2022/09/22 16:01

swordone

総合スコア20651

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

Logarithm

2022/09/22 16:08

i → k → p → jでした。申し訳ありません
guest

0

距離の定義上、距離が負になることはありません

投稿2022/09/22 15:19

yuki23

総合スコア1448

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

Logarithm

2022/09/22 16:06

距離の話にしたのが悪かったです。 重みつきグラフです。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.48%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問