双方向ダイクストラ談義
-
masashinakata
- 2492
- 0
- 1
- 0
-
- いいね！0
みさわ
@Mi_Sawa
@tatanaideyo 「"両方で探索済みになった頂点 v" ができたら終了する. 但し, v が最短経路に含まれるとは限らず, 今の距離ラベルで d_s[u] + d_t[u] が最小になる所を探しなおさなければいけない」という感じだと思います.
2015-10-30 21:53:16
tshita
@tshita0
@Mi_Sawa アドバイス有り難うございます．"両方で初めて探索済みとなった頂点v"ができたら終了でしょうか？ こんな感じで変更したのですが上手くいきませんでした（ideone.com/qvFBNv）．
2015-10-30 22:33:54
みさわ
@Mi_Sawa
@tatanaideyo push じゃなくて pop の方です. que1 からも que2 からも pop された(つまり, s からも t からも距離が確定した)頂点が出てきた時ですね.
2015-10-30 22:37:12
みさわ
@Mi_Sawa
そういえば, ICPC 会津で, dijkstra しても A^* しても通らなくて, 双方向 A^* で通したような記憶がある. 多分, dijkstra の時点で if(now > d[u]) continue; みたいなのを忘れたかなんかしていたんだろうなぁ.
2015-10-30 22:59:45
tshita
@tshita0
双方向ダイクストラの実装（ideone.com/CDoa5m）．普通のダイクストラよりは早くなったけどそもそも自分の実装が上手くなさそう．
2015-10-30 23:02:36
tshita
@tshita0
s-t最短路問題の問題ないかな．AOJのライブラリのところ（judge.u-aizu.ac.jp/onlinejudge/de…）は単一始点最短路問題になってる．
2015-10-30 23:12:39
みさわ
@Mi_Sawa
コンパイル通ることしかチェックしていないけれど, こんな感じ. ideone.com/UayEyc 基本的に, 普通の dijkstra とかを書いて, 倍にして, 終了条件チェックする.
2015-10-30 23:20:47
tshita
@tshita0
はてなブログに投稿しました 双方向ダイクストラ - tatanaideyoの備忘録Ⅱ tatanaideyo.hatenablog.com/entry/2015/11/… #はてなブログ
2015-11-01 03:17:26
™
@tmaehara
これまでに見たことのある (sからの距離) --(枝)-- (tまでの距離) の上界 μ を覚えておいて，キューの先頭の和がこれを越えたところで終了条件にしていい．
2015-11-02 22:33:51
™
@tmaehara
もう１つ．tatanaideyo.hatenablog.com/entry/2015/11/…の最後部分の必要性はw(12)=1,w(13)=2,w(24)=2,w(35)=3,w(45)=1を考えればわかる．実は出会ったところで止めて良いのは未確定頂点のdも更新されているという実装のおかげで，ちょっと得してる．
2015-11-02 23:44:21
™
@tmaehara
tatanaideyo.hatenablog.com/entry/2015/11/… これ，比較するなら「各点について，近い10点にしか移動できない」みたいにするのが良いっすね．
2015-11-05 08:08:49