コンテンツにスキップ

ダイクストラ法

タグ「ダイクストラ法」の記事 4 件

ABC481 F - Evil Shortest Path

NN 頂点 MM 辺の有向グラフがあり、各辺には 11 以上 99 以下の数字が書かれています。通った辺の数字を順につなげた整数をその移動のスコアとします。v=2,3,…,Nv = 2, 3, \ldots, N のそれぞれについて、頂点 11 から頂点 vv へ移動するときのスコアの最小値を 998244353998244353 で割ったあまりを求める問題です。

同じ頂点や辺を何度通ってもよく、頂点 11 から全頂点に到達できることが保証されます(2≤N≤2×1052 \le N \le 2 \times 10^5、N−1≤M≤2×105N - 1 \le M \le 2 \times 10^5)。

辺の数字はどれも 11 以上なので、スコアの桁数は通った辺の本数に等しく、桁数が少ないほどスコアは小さくなります。よって、スコアが最小になる移動は、頂点 11 からの最短路(辺の本数が最小の移動)のどれかです。桁数が同じ整数どうしの大小は、数字の列の辞書順と一致するので、最短路のうち数字の列が辞書順で最小のものを求めればよいです。

頂点 11 からの最短距離 dd を BFS で求めます。最短路で使える辺は、dv=du+1d_v = d_u + 1 を満たす辺 u→vu \to v だけです。頂点 vv への辞書順最小の列を svs_v とすると、

sv=min⁡u→v, dv=du+1(su の後ろに辺の数字をつなげた列)s_v = \min_{u \to v,\ d_v = d_u + 1} (s_u \text{ の後ろに辺の数字をつなげた列})

です。長さの同じ列どうしでは、sus_u より大きい列の後ろに数字をつなげても、sus_u の後ろにつなげた列より小さくはならないからです。dd の小さい順に頂点を見ていけば、sus_u を使うときには sus_u が確定しています。

列 svs_v の長さは最大で N−1N - 1 になるので、すべての列をそのまま持つと間に合いません。そこで、列を Trie のノードで表します。sus_u のノードから辺の数字で 1 文字進んだノードが「sus_u の後ろに数字をつなげた列」です。1 本の辺でノードは高々 1 個しか増えないので、ノードは M+1M + 1 個以下です。

2 つのノードの列の辞書順の比較は、2 つのノードの最小共通祖先(LCA)のすぐ下の文字を比べればできます。ノードごとに祖先への飛び先を持っておけば、LCA は O(log⁡N)O(\log N) で求まります。

答えのあまりは、svs_v を更新するたびに (su のあまり)×10+(数字)(s_u \text{ のあまり}) \times 10 + (\text{数字}) として一緒に更新します。計算量は O((N+M)log⁡N)O((N + M) \log N) です。

なお、Trie を使わなくても、同じ距離の頂点どうしの svs_v の順位を距離ごとに求めておき、「sus_u の順位、辺の数字」の組をソートして次の距離の順位を決める方法でも解けます。

別解:スコアを距離にしてダイクストラ法

Section titled “別解:スコアを距離にしてダイクストラ法”

スコアを「数字の列の長さで比べ、長さが同じなら辞書順で比べる」値と考えると、この問題はスコアを距離とする最短路問題です。この距離には次の 2 つの性質があります。

  • 辺をたどると、列が 1 文字長くなるので、距離は必ず大きくなる。
  • 列 aa が列 bb より小さければ、同じ数字をつなげた後も、aa のほうが bb 以下になる。

この 2 つが成り立つので、ダイクストラ法がそのまま使えます。距離は上と同じく Trie のノードで持ち、比較 1 回が O(log⁡N)O(\log N) なので、全体の計算量は O(Mlog⁡Mlog⁡N)O(M \log M \log N) です。BFS の層ごとに処理する工夫を、ダイクストラ法に任せる形になります。

C++(BFS)
#include "shogo-library/base/all"
#include "shogo-library/graph/shortest-path.hpp"
#include "shogo-library/math/modint.hpp"
#include "shogo-library/string/trie.hpp"
#include "shogo-library/utility/vector_func.hpp"
using mint = modint998244353;
void solve() {
LL(N, M);
Graph<> g(N);
g.read(M, -1, true, true);
auto d = shortest_path(g, 0, false).dist;
Trie<9, 1> trie;
vl node(N, -1);
vec<mint> ans(N);
node[0] = 0;
for (ll u : sorted_idx(d)) {
for (auto &e : g[u]) {
if (d[e.dst] != d[u] + 1)
continue;
ll v = trie.extend(node[u], e.cost);
if (node[e.dst] == -1 || trie.less(v, node[e.dst])) {
node[e.dst] = v;
ans[e.dst] = ans[u] * 10 + e.cost;
}
}
}
rep(v, 1, N) print(ans[v]);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

g.read(M, -1, true, true) は、辺の数字を重みとして、有向辺を MM 本読みます。shortest_path(g, 0, false) の第 3 引数 false は重みを無視することを表し、BFS で辺の本数の最短距離を求めます。

Trie<9, 1> は、文字 11 から 99 を使う Trie です。根(ノード 00)が空の列で、頂点 11 の列に対応します。node[v] は svs_v のノード、ans[v] はそのあまりです。

sorted_idx(d) は d の小さい順に並べた頂点の番号の列です。trie.extend(node[u], e.cost) で sus_u の後ろに辺の数字をつなげた列のノードを(なければ作って)求め、trie.less(v, node[e.dst]) で、いまの svs_v より辞書順で小さいかを O(log⁡N)O(\log N) で比べています。

使用ライブラリ:cpp_include@4b58304

C++(ダイクストラ法)
#include "shogo-library/base/all"
#include "shogo-library/graph/shortest-path.hpp"
#include "shogo-library/math/modint.hpp"
#include "shogo-library/string/trie.hpp"
using mint = modint998244353;
Trie<9, 1> trie;
struct Score {
ll node = 0;
ll digit = 0;
mint val = 0;
Score() = default;
Score(ll digit) : digit(digit) {}
static Score inf() {
Score res;
res.node = -1;
return res;
}
friend Score operator+(const Score &a, const Score &e) {
Score res;
res.node = trie.extend(a.node, e.digit);
res.val = a.val * 10 + e.digit;
return res;
}
friend bool operator<(const Score &a, const Score &b) {
if (a.node == -1)
return false;
if (b.node == -1)
return true;
if (trie.depth(a.node) != trie.depth(b.node))
return trie.depth(a.node) < trie.depth(b.node);
return trie.less(a.node, b.node);
}
friend bool operator>(const Score &a, const Score &b) { return b < a; }
friend bool operator==(const Score &a, const Score &b) { return a.node == b.node; }
friend std::istream &operator>>(std::istream &is, Score &s) { return is >> s.digit; }
};
void solve() {
LL(N, M);
Graph<Score> g(N);
g.read(M, -1, true, true);
auto d = shortest_path(g, 0, true, Score::inf()).dist;
rep(v, 1, N) print(d[v].val);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

Score は距離と辺のコストの両方に使う型です。距離としては、node がスコアの列の Trie のノード、val がそのあまりです。辺のコストとしては、digit に辺の数字を入れます。

  • operator+ は、距離に辺のコストを足す操作で、Trie を辺の数字で 1 文字進めます。
  • operator< は、列の長さ(Trie の深さ)で比べ、同じなら trie.less で辞書順に比べます。node == -1 は到達できないことを表す最大の値 inf() です。
  • operator> と operator== は、ライブラリのダイクストラ法の中で、距離の比較と未到達の判定(inf との比較)に使われます。
  • shortest_path の inf の既定値は std::numeric_limits<Cost>::max() / 4 で、この型では使えないので、Score::inf() を渡しています。
  • g.read は、重みを Cost c(1) で作ってから std::cin >> c で読むので、整数からのコンストラクタと operator>> を用意しています。始点の距離 0 は Score(0) で、Trie の根(空の列)になります。

使用ライブラリ:cpp_include@4b58304

ABC481 D - Autopilot

NN 頂点 MM 辺の有向グラフがあります。いまいる頂点から、次のどちらかの方法で移動できます。

  • 出ている辺の行き先のうち、番号が最小の頂点に燃料 00 で移動する。
  • 出ている辺の行き先を好きに選び、燃料 11 で移動する。

頂点 SS から頂点 TT へ移動するのに必要な燃料の最小値を求める問題です。到達できなければ −1-1 を出力します(2≤N≤2×1052 \le N \le 2 \times 10^5、1≤M≤2×1051 \le M \le 2 \times 10^5)。

各頂点 uu から出ている辺の行き先のうち、番号が最小の頂点へはコスト 00、それ以外の頂点へはコスト 11 の辺を張った新しいグラフを作ります。このグラフで SS から TT への最短距離が答えです。

辺のコストは 00 か 11 で非負なので、ダイクストラ法で求められます。計算量は、行き先のソートも含めて O((N+M)log⁡(N+M))O((N + M) \log (N + M)) です。コストが 00 と 11 だけなので 01-BFS でも求められ、その場合は最短路の部分が O(N+M)O(N + M) になります。

ダイクストラ法については ダイクストラ法のリンク集 も見てください。

C++
#include "shogo-library/base/all"
#include "shogo-library/graph/shortest-path.hpp"
#include "shogo-library/utility/container_func.hpp"
void solve() {
LL(N, M, S, T);
S--, T--;
Graph<> g(N), h(N);
g.read(M, -1, false, true);
rep(u, N) {
vl tmp;
for (ll v : g[u])
tmp.push_back(v);
sort(tmp);
rep(i, len(tmp)) {
h.add_directed_edge(u, tmp[i], i > 0);
}
}
ll ans = shortest_path(h, S).dist[T];
print(ans > M ? -1 : ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

g.read(M, -1, false, true) は、頂点番号から 11 を引き、重みなしの有向辺として MM 本の辺を読みます。

g で頂点 u から出ている辺の行き先を tmp に集めてソートし、先頭(番号が最小の頂点)へはコスト i > 0 すなわち 00、それ以外へは 11 の辺を h に張ります。

shortest_path(h, S) は、h での S から各頂点への最短距離をダイクストラ法で求めます。到達できない頂点の距離はとても大きな値になります。到達できるときの答えは、同じ辺を 2 回使わない経路で考えれば MM 以下なので、MM より大きければ −1-1 を出力しています。

使用ライブラリ:cpp_include@4b58304

ダイクストラ法のリンク集

ダイクストラ法について、参考になる記事や資料をまとめました。

ダイクストラ法は、辺の重みがすべて非負のグラフで、1 つの始点から各頂点への最短距離を求めるアルゴリズムです。「まだ確定していない頂点のうち、暫定の距離が最小のもの」を確定させ、そこから出る辺で隣の頂点の距離を更新する、という操作を繰り返します。優先度付きキュー(二分ヒープ)を使うと O((V+E)log⁡V)O((V + E) \log V)、ヒープを使わずに毎回最小の頂点を探すと O(V2)O(V^2) です。負の重みの辺があると正しく動かないので、そのときはベルマン-フォード法などを使います。

競プロでよく書く実装では、距離を更新するたびに (距離, 頂点) をキューに追加し、古い要素は消さずに残します。そのため、取り出した距離が記録している距離より大きいときは読み飛ばす処理(if d > dist[v]: continue)が必要です。これがないと計算量が悪化します。また、距離は 64 bit 整数で持つ必要があることが多いです。

AtCoder Library(ACL)にはダイクストラ法がなく、AtCoder Algorithm Lectures にも今のところ最短経路の講座はありません。

  • 最短経路問題総特集!!!BFSから拡張ダイクストラまで(ageprocpp、Qiita)
    • BFS、ベルマン-フォード法、ダイクストラ法、ワーシャル-フロイド法、経路復元、拡張ダイクストラ(頂点を増やしたグラフ上のダイクストラ法)までを、文章で順に説明しています。ダイクストラ法の手順には、古い要素を読み飛ばす処理も書かれています。コードはほとんどありません。
    • ワーシャル-フロイド法の節の「途中で辺の長さが変わるクエリがあっても O(V2)O(V^2) で対応できる」は、辺が短くなる場合に限った話です。
  • ダイクストラ法による単一始点最短経路を求めるアルゴリズム(アルゴリズムロジック)
    • 手順、計算量、C++ の実装、経路復元、正当性の考え方を、図を使って説明しています。
    • キューに入れる距離の型が pair<long, int> の long です。AtCoder では 64 bit ですが、Windows などでは 32 bit なので、書き写すときは long long にしてください。
  • ダイクストラ法・ダイクストラ法の高速化(アルゴ式)
    • 問題を解きながら手順を学ぶ形式です。まずヒープを使わない O(N2+M)O(N^2 + M) の方法を実装し、次の問題でヒープを使って高速化します。
  • ダイクストラ法のよくあるミスと落し方(snuke)
    • 古い要素を読み飛ばす処理を忘れる、最大ヒープのまま使う、負の辺のあるグラフに使う、といったよくあるミスで、実際にどれだけ遅くなるかを撃墜ケースつきで説明しています。自分の実装を確かめるのに役立ちます。
  • Dijkstra 法(Kyopro Encyclopedia of Algorithms)
    • 定義、計算量、高速化の要点(キューに入れる前の枝刈り、0-1 BFS、拡張したグラフでの利用など)を短くまとめた辞典の項目です。
  • 色々なダイクストラ高速化(yosupo、スライド)
    • キューに入れる前の枝刈り、辺の重みが 0/10/1 のときの 0-1 BFS、重みが小さい整数のときの方法、Radix Heap などの高速化を紹介しています。C++ です。
  • 01-BFSのちょっと丁寧な解説(ARMERIA)
    • ダイクストラ法、BFS、01-BFS を「暫定の距離が最小の頂点を取り出す」という共通点から説明しています。C++ と Python のコードがあります。
  • heapq --- ヒープキューアルゴリズム(Python 公式ドキュメント)
    • heapq は最小ヒープで、(距離, 頂点) のタプルをそのまま入れられます。「優先度キュー実装の注釈」の節では、優先度が変わった要素に無効の印をつけて残し、新しい要素を追加し直す方法を紹介しています。ダイクストラ法で古い要素を読み飛ばすのと同じ考え方です。
  • Dijkstra (単一始点最短路)(Luzhiled’s Library)
    • C++ の実装で、距離に加えて、直前の頂点と辺の番号を返すので経路復元にも使えます。距離の型はテンプレート引数なので、long long を指定してください。
  • Yosupo Library Checker - Shortest Path(けんちょんの競プロ精進記録)
    • 下の Library Checker の問題の解説で、ダイクストラ法での経路復元の方法を説明しています。C++ のテンプレートつきです。
  • ダイクストラ法(日本語版 Wikipedia)
    • 擬似コード、ヒープの種類ごとの計算量、ビー玉と紐のたとえによる説明があります。擬似コードはキューの中の値を書き換える(decrease-key)形で、競プロでよく書く「追加して読み飛ばす」形とは違います。
  • Dijkstra’s algorithm(英語版 Wikipedia)
    • 歴史、擬似コード、正当性の証明、計算量、双方向ダイクストラ法などの変種まで載っています。キューに追加して読み飛ばす形の実装にも触れています。
  • Dijkstra - finding shortest paths from given vertex・Dijkstra on sparse graphs(cp-algorithms)
    • 前者はヒープを使わない O(n2+m)O(n^2 + m) の方法を正当性の証明と経路復元つきで、後者は set と priority_queue を使う O(mlog⁡n)O(m \log n) の方法を説明しています。後者には、読み飛ばす処理がないと O(nm)O(nm) まで悪化しうることも書かれています。
    • コードは距離を int で持っています。また、後者でフィボナッチヒープを使った O(nlog⁡n+m)O(n \log n + m) を「理論上の下限」としているのは、比較に基づく方法に限った話です。
  • Shortest Paths with Non-Negative Edge Weights(USACO Guide)
    • 後半がダイクストラ法の節で、C++・Java・Python の実装と問題の一覧があります。読み飛ばす処理を外すと TLE する例も説明しています。前半はベルマン-フォード法とワーシャル-フロイド法です。
  • ABC477 E - Wheel Distance
    • 中心の頂点から各頂点への最短距離をダイクストラ法で前計算し、各クエリに場合分けで答えています。

ABC477 E - Wheel Distance

頂点 1,…,N1, \ldots, N が重み AiA_i の辺で円環状につながり、さらに各頂点 ii が中心の頂点 N+1N+1 と重み BiB_i の辺でつながったグラフがあります。QQ 個のクエリ (S,T)(S, T) それぞれについて、頂点 SS から頂点 TT への最短経路の長さを求める問題です(N,Q≤2×105N, Q \le 2 \times 10^5)。

中心の頂点を H=N+1H = N + 1 とし、HH から各頂点への最短距離 FvF_v をダイクストラ法で求めておきます。

T=HT = H のときは、答えは FSF_S です。

T≠HT \ne H のときは、最短経路が HH を通るかどうかで場合分けします。

  • HH を通る場合: SS から HH へ行き、HH から TT へ行く経路になるので、長さは FS+FTF_S + F_T 以上です。逆に、S→HS \to H と H→TH \to T の最短経路をつなげれば長さ FS+FTF_S + F_T の経路が作れます。なので、この場合の最短は FS+FTF_S + F_T です。
  • HH を通らない場合: 円環の上だけを通るので、SS から TT へ時計回りに行くか、反時計回りに行くかの 2 通りです。AA の累積和を Gi=A1+⋯+AiG_i = A_1 + \cdots + A_i とすると、長さはそれぞれ GT−1−GS−1G_{T-1} - G_{S-1} と GN−(GT−1−GS−1)G_N - (G_{T-1} - G_{S-1}) です。

この 3 つの最小値が答えです。前処理が O(Nlog⁡N)O(N \log N)、各クエリが O(1)O(1) です。

cLay
ll@N,@Q,@A[N],@B[N],E[2N],F[N+1],G[N+1]{};int C[2N],D[2N];rep(i,N)C[i]=i,D[i]=(i+1)%N,G[i+1]=G[i]+(E[i]=A[i]),C[N+i]=i,D[N+i]=N,E[N+i]=B[i];wgraph<ll>g;g.setEdge(N+1,2N,C,D,E);g.getDist(N,F);rep(Q){ll@S--,@T--,x;if(N-T)x=F[S]+F[T],x<?=G[T]-G[S],wt(x<?=G[S]+G[N]-G[T]);else wt(F[S]);}

cLay で書いています。頂点は 0 始まりで、0,…,N−10, \ldots, N-1 が円環、NN が中心です。

C、D、E に辺の両端と重みを入れ、wgraph の setEdge で重み付き無向グラフを作り、getDist(N, F) で中心からの最短距離を F に求めています。G は AA の累積和です。

クエリでは x<?= (小さい方を代入する cLay の演算子)で 3 つの候補の最小値をとっています。N-T が 00、つまり TT が中心のときは F[S] を出力します。

Python
from heapq import heappop, heappush
from itertools import accumulate
N, Q = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
graph = [[] for _ in range(N + 1)]
for i in range(N):
graph[i].append(((i + 1) % N, A[i]))
graph[(i + 1) % N].append((i, A[i]))
graph[i].append((N, B[i]))
graph[N].append((i, B[i]))
F = [None] * (N + 1)
pq = [(0, N)]
while pq:
d, v = heappop(pq)
if F[v] is not None:
continue
F[v] = d
for u, w in graph[v]:
if F[u] is None:
heappush(pq, (d + w, u))
acc = [0, *accumulate(A)]
ans = []
for _ in range(Q):
S, T = map(int, input().split())
S -= 1
T -= 1
if T == N:
ans.append(F[S])
else:
ans.append(min(F[S] + F[T], acc[T] - acc[S], acc[S] + acc[N] - acc[T]))
print(*ans, sep="\n")

cLay 版と同じ処理です。ダイクストラ法は heapq で書いています。