概要

通常の最短経路問題と違って、辺を通ったときのコストの変化のしかたが変な場合でも、ダイクストラ法で解けることがある。ダイクストラ法を適用できる条件は

「途中のコストをあえて大きくしたほうが最終的なコストが小さくなる」ということが起こらない
「辺を通ったことでコストが減る」ということが起こらない

（通常の）最短経路問題とダイクストラ法

（通常の）最短経路問題は、次のような問題です。

グラフがある。グラフの各辺には重みとよばれる値が設定されている。 $i$ 番目の辺の重みを $d_i$ とする。

あなたは頂点 $s$ にいる。また、コスト とよばれる値を持っている（最初のコストは $0$ である）。「今いる頂点を始点にもつ辺を一つ選び、その辺の終点に移動する」ことを繰り返して、頂点 $t$ に行きたい。ここで、コストが $x$ のとき、 $i$ 番目の辺を選んで移動すると、コストが $x + d_i$ になる。頂点 $t$ に着いたときのコストの値の最小値（これを頂点 $s$ と頂点 $t$ の 最短距離 という）を求めよ。

これは、一般にはベルマン・フォード法で、辺の重み $d_i$ がすべて非負のときはダイクストラ法で解くことができます。

ダイクストラ法についての詳細な解説はこの記事の趣旨から外れるので行いませんが、簡潔に述べると、「『現在最短距離が確定している頂点から $1$ 回の移動で行くことのできる（最短距離が確定していない）頂点のうち、その移動で行ったときのコストの値が最小となるもの』は最短距離が確定する（これは $d_i \geq 0$ だからです）ので、それを確定させていく」という感じのアルゴリズムです。詳細についてはこの記事が個人的にわかりやすかった（らしい*1）のでおすすめです。

変な最短経路問題とダイクストラ法

さっきの問題をちょっと変えてみましょう。（変えた部分を赤字で示しています）

グラフがある。グラフの各辺には関数が設定されている。 $i$ 番目の辺に設定されている関数を $f_i(x)$ とする。

あなたは頂点 $s$ にいる。また、コスト とよばれる値を持っている（最初のコストは $0$ である*2）。「今いる頂点を始点にもつ辺を一つ選び、その辺の終点に移動する」ことを繰り返して、頂点 $t$ に行きたい。ここで、コストが $x$ のとき、 $i$ 番目の辺を選んで移動すると、コストが $f_i(x)$ になる。頂点 $t$ に着いたときのコストの値の最小値（これを頂点 $s$ と頂点 $t$ の 最短距離 という）を求めよ。

これはダイクストラ法で解けるでしょうか？実は、 $f_i(x)$ たちが次の条件を満たすとき、ダイクストラ法で解けます。

$f_i(x)$ は $x$ に関して広義単調増加な関数である。つまり、「途中のコストをあえて大きくしたほうが最終的なコストが小さくなる」ということが起こらない。
$x \leq f_i(x)$ である。つまり、「辺を通ったことでコストが減る」ということが起こらない。

明らかに、通常のダイクストラ法の $f_i(x) = x + d_i, d_i \geq 0$ はこの条件を満たしています。

一つ目の条件は、これが成り立っていなければそもそも DP 的な考え方ができなくなります。たとえば XOR などはこの性質を満たしません（最短路ではないですが、たとえば D - Dance で DP するのは噓解法です）。これが原因でうまくいかないとき、場合によっては、頂点に持たせる情報を増やすこと（いわゆる拡張ダイクストラ）で対応できることもあります。

二つ目の条件は、通常のダイクストラ法で $d_i \geq 0$ であることに対応していて、最短距離をすぐ確定させることの正当性に関わっています*3。

また、二つ目の条件について、より厳しい条件である「コストの増加が $0$ または $1$ 」が成り立っているとき、（通常の最短経路問題と同様に）01BFS が正当でもあります。priority_queue が deque になっているだけであり、「最短距離が確定できるところから確定する」という点では結局同じことをしているためです。

具体例

atcoder.jp

$N$ 個の都市と $M$ 個の鉄道がある。 $i$ 番目の鉄道は都市 $A_i$ と都市 $B_i$ を結んでいて、時刻が $K_i$ の倍数になるたびに、双方の都市からそれぞれ他方の都市に時間 $T_i$ かけて移動する電車が発車する。時刻 $0$ に都市 $X$ から移動を開始できるとき、都市 $Y$ には最速でいつたどり着けるか？

都市を頂点、鉄道を辺、時刻をコストとみればよいです。鉄道を使うとき、その鉄道の中で最も早く出発する電車に乗るのが最適である（同じ鉄道なら、遅く出発する電車にわざと乗っても得しない）ので、 $f_i(x) = (x \ 以上の最小の \ K_i \ の倍数) + T_i = K_i \lceil \frac{x}{K_i} \rceil + T_i$ としてよいです。この関数は二つの条件を満たすので、ダイクストラ法が使えます。

「その鉄道の中で最も早く出発する電車に乗るのが最適」というのが、人によっては非自明と感じるかもしれません。そういうときは、問題設定に忠実に、グラフが無限本の辺をもつことにしてみましょう。つまり、各 $1 \leq i \leq N, 1 \leq j$ に対して、頂点 $A_i$ と頂点 $B_i$ を結ぶ無向辺 $(i, j)$ があるとして、辺 $(i, j)$ には $f_{i,j}(x) = (x \ 以上の \ K_i \ の倍数のうち、\ j \ 番目に小さいもの) + T_i$ という関数が設定されていると考えてみましょう。このとき、この関数は二つの条件を満たします。また、ダイクストラ法のアルゴリズムを考えると、 $j \geq 2$ のとき辺 $(i, j)$ は結局使われないことがわかります。