SPFA談義

tubo28 @tubo28

SPFAやっぱりよくわからない

みさわ @Mi_Sawa

SPFA は, bellman 方程式に従って更新する順番を, 「更新しなきゃいけなくなったら queue に突っ込む. 既に queue にあるなら無視」にしただけと思うと, (負閉路が無いときは)理解できる.

みさわ @Mi_Sawa

(bellman-ford も SPFA も dijkstra も bellman 方程式に従って更新する順番を変えただけ)

tubo28 @tubo28

@Mi_Sawa なるほど… 確かに inf + e.weight = inf みたいな更新は無くなりますね…

みさわ @Mi_Sawa

@tubo28 あと, queue から出てくるものは距離ラベルが更新された後にまだ伝播していないものだけなので, 既に確定した頂点を何度も見ないで済むというのも, bellman-ford に比べてよいところですかね.

tubo28 @tubo28

@Mi_Sawa なるほどなるほど。ありがとうございます。

tubo28 @tubo28

やっぱり負辺あると手戻りが発生する(既に確定した頂点を何度も見る必要があるかもしれない)のでかなり辛いという感じですかね

tubo28 @tubo28

閉路検出もなるほどって感じ codeforces.com/blog/entry/124…

tubo28 @tubo28

@tubo28 負閉路

みさわ @Mi_Sawa

SPFA, ごく稀に牛で便利.

コルン @colun

シラナイ＞SPFA SPFAで検索したら、次のようなのが出てきた。 hogloid.hatenablog.com/entry/20120409… #Code_Festival

コルン @colun

優先度付き待ち行列をキューで代用したことで、不安定に何度も安定しない更新をかけちゃって、計算量が増える、、、みたいなのはありますが、それ自体は正しい答えを捻じ曲げるものではなかったりします。 #Code_Festival