最短経路アルゴリズムの日常

使うアルゴリズムは……君に決めた！

うっ、コンテストはあと３０分か。

３問目に時間を使いすぎてしまった。あのタイポが無ければ１５分は早くACできていたはずなのに。

まあいい、まだ30分もある。次は個人的な壁である４問目だが、†天才†をすれば十分間に合うだろう。問題は……どれどれ。

”あなたは○×小学校の生徒です。あなたは授業中に友達のAさんまで手紙を回したいと思いました。怒られたくないので、先生が板書している間にこっそりと出来るだけ早く手紙を回す必要があります。”

ふむ、授業中に友達に手紙をこっそり回す問題か。たしかにそんなことをしている人はいたな。手紙を回す時間の最小化問題か。

”あなたのクラスには生徒がN×M人在籍しており、縦にN個、横にM個の格子状に机が並んでいます。生徒は手紙を、前後左右に机が隣接している生徒へ渡すことができます。この作業にかかる時間は生徒によらずいつも１秒です。手渡す作業以外に時間はかからないものとします。”

ふむふむ。生徒の机はN×Mの格子状に並んでいる、前後左右に手紙を回すには１秒かかる、なるほどなるほど。

知らんけど、直感的にはスタートの人とゴールの人のマンハッタン距離を求めるだけで良いのでは？４問目にしては簡単すぎないか？

”ただし、手紙は友達同士の間でしか渡すことができません。このクラスでの友達関係についての情報が与えられます。”

え、前後左右だけど友達じゃなかったら手紙を回せないのか。全員仲良くして！

この問題設定じゃ、マンハッタン距離が答えとは限らないな。４問目、やはり壁としての手応えがある。

”手紙をAさんに回すのにかかる最小時間を求めてください。Aさんに届けるのが不可能な場合にはその旨を答えてください。”

手紙回しに失敗する不仲なクラス、嫌だな……。

さて、問題を読んだ限り、グラフの最短経路問題な気がする。とても典型っぽい。これは今日こそ４問目の壁を超えられるんじゃないか？

グラフの最短経路アルゴリズムといえば、ダイクストラ、ベルマンフォード、ワーシャルフロイド……。今回はどれだ？３０分しかない。嘘方針に走っている時間はない。慎重に見極めるぞ……。

＊＊＊＊＊＊＊＊＊＊

《ダイクストラ法視点》

グラフの最短経路といえばオレ、ダイクストラ一択だな！単一始点最短経路を求めるときにオレを使わない選択肢なんて存在しない！

近いところから確定していくから直感的に理解しやすい！

適切なデータ構造を併用すれば頂点と辺の和に対してほぼ線形で動く！

log？定数！

しかし、オレの素質を十分に引き出すには注意が必要だ。簡単に計算量が悪化する罠が多いからな。汎用性が高いが難易度が高いオレ、罪な男だぜ……フッ。

間違ってもベルマンフォードやワーシャルフロイドに手を出すなよ？

＊＊＊＊＊＊＊＊＊＊

《ベルマンフォード法視点》

はぁ、どうせまた僕は使われないだろうな……。

そうだよね、僕が使われることなんて滅多にないもんね……。

負の重みの辺があっても動く？負閉路を検出できる？

たしかにそれは僕の強みだ。傲慢なダイクストラや神経質なワーシャルフロイドには、逆立ちしたって解けっこない。

でも、負の辺をもつグラフが出題されること、ほとんど無くない……？

無駄な更新処理もダイクストラより多くて優雅さに欠けるし……。

でもでも、僕の生みの親の１人であるベルマンさんは動的計画法の生みの親でもあるし、僕が一番正統な最短経路アルゴリズムだよね……？

信じているよ、僕を使ってくれるって。その問題の制約なら僕でも十分高速に間に合うから……。

＊＊＊＊＊＊＊＊＊＊

《ワーシャルフロイド法視点》

全く、ダイクストラの奴は五月蝿いったらありゃしない。

ベルマンフォードも、じめじめしていて面倒くさい。

やっぱりここはアタシが頑張らなきゃね。

あいつらは単一始点最短経路を求めるだけで満足しているお子ちゃまさ。

全点対最短経路を求めるには始点ごとにアルゴリズムを走らせる必要がある。

その点、アタシはスパッと僅かな実装量で全点対について最短経路を求めてしまえるのさ。そりゃ３重ループを回すからグラフのサイズがあんまり大きいと困るけど。

「なあなあワーさん、きちんと問題を読んだらどうだ？今回はアンタの出番はまず無いぜ？」

「ダイくんの言うとおりだよ……今回は単一始点だからワーさんはお門違いだよ……」

「アンタ達！アタシが滔々と語っているのを邪魔するんじゃないよ！」

「短さが取り柄のワーさんは引っ込んでな！」

「なんだって！？短いことの何が悪いのさ！？コーダーにバグを踏ませまくって不快な気持ちにさせるアンタより余程マシだね。」

「でも、ワーさんだって、ループの順番を間違えられがちだよね……。適当な順番で３回繰り返せば良いなんて言われちゃっているし……」

「ベルマンフォード、どうしてアンタがダイクストラの肩を持つのさ！？それにさっきから”ワーさん”って、きちんと名前で呼んでもらおうじゃないか！」

「ワーシャルフロイドなんて名前、長くて呼んでられねーよ！」

「ねえねえ、落ち着いて……」

「ダイクストラだって英語だと読みづらいじゃない！それとも、独り親なことを気にしているのかい？」

「あー、それは触れない約束だろう！いや、オレの親は１人でもすごいんだから関係ないね！」

「ねえねえ……」

「なんだい、ベルマンフォード、はっきり喋りなさい」

「ベル、言いたいことがあるなら手短に言え」

「あの……その、方針が決まったみたいだよ……？ほら、コーディングを始めようとしている……」

「なんだって！？」

「そういうことは早く言えよ。で、どのアルゴリズムなんだ？十中八九オレだろうけど」

「えっと……q……u……e……」

「queueかしら？」

「ん？priority_queueではなく？」

「みたいだね……。ということは、つまり……」

＊＊＊＊＊＊＊＊＊＊

ダイクストラは、速いけど実装に罠が多いからあんまり書きたくないな。気軽に指数アルゴリズムになられると困ってしまう。ライブラリ化しとくべきかな。

とりあえず今回はダイクストラじゃなくても解けそうだし、バグらせてタイムアップしたくないからパスで。

ベルマンフォードは……論外だな。辺の重みは全部１秒だから負の辺とかないし。また別の機会に。や、ほとんど使った覚えは無いけどね。

ワーシャルフロイドは、今回さらに関係なさそう。クラスがもっと治安悪くて沢山の人が手紙を回すのならともかく、今回は１人だけだから全点対最短経路アルゴリズムの出番じゃない。

というか、辺の重みが同じならわざわざ高度なアルゴリズムを持ち出さなくても良いのでは？

……幅優先探索、でいけるのでは？

うん、大丈夫そう。よし、幅優先探索なら何度も書いたことがあるし、残り２０分でも実装しきれそうだ！

カタカタ、カタカタ

アドレナリンがドパドパ出ているのを感じる。競技をしているって感じだ！

よし、サンプルは通ったぞ、提出っと。

頼む、通ってくれ……！

1/23　……　5/23　……　15/23　……　22/23　……　AC

やった！４問目の壁を超えたぞ！いつになく典型問題だったけど、それでも４完は４完だ！やったー！

最短経路も他も解ける幅優先探索、やっぱり最高のアルゴリズムだ！