Deque による 0-1 BFS
重みが 0 または 1 のときの最短経路を求めます
「Deque による 0-1 BFS」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。
特殊な種類のグラフ
辺の重みが0または1だけのグラフもあります。その場合は、より簡単で高速な方法によってDijkstraを上回れます。
0-1 BFSを使う
0-1 BFSは、0または1の重みを持つグラフで最短経路を線形時間で求めます。ヒープも対数係数も必要ありません。
使う道具：deque
ヒープをdequeに置き換えます。dequeは、先頭と末尾の両方から要素を追加・削除できるキューです。
from collections import deque
dq = deque([src])核心となる考え方
重み0の辺では距離が変わらず、重み1の辺では1増えます。dequeはこの2つのグループを順序どおりに保ちます。
重み0の辺は先頭へ
重み0の辺を通った場合は、隣接ノードをappendleftします。追加の距離がかからないため、次に処理する必要があるからです。
dq.appendleft(v)重み1の辺は末尾へ
重み1の辺を通った場合は、隣接ノードを末尾にappendします。始点から1層遠い位置にあるためです。
dq.append(v)先頭から取り出す
現在のノードは必ずpopleftします。層ごとに探索するBFSと同じように、dequeを距離順に保てます。
u = dq.popleft()重みを使って緩和する
各辺を緩和します。新しい距離は dist[u] と辺の重みの合計とし、その重みに応じて先頭または末尾に追加します。
nd = dist[u] + w
if nd < dist[v]:
dist[v] = nd順序が保たれる理由
dequeには、同時に異なる距離が最大2種類だけ入ります。この不変条件があるからこそ、先頭と末尾への追加が機能します。
線形時間の高速さ
ヒープを使わないため、0-1 BFSの計算量はO(V + E)です。同じグラフなら、Dijkstraより明らかに高速です。
使うべき場面
移動のコストが0または1のときに使います。たとえば、一部の移動が無料で、他の移動に1のコストがかかるグリッドなどです。
確認問題
重み0の辺を通って隣接ノードを緩和した場合、そのノードはどこに入れますか？
まとめ：0-1 BFS
dequeを使い、重み0の辺は先頭に、重み1の辺は末尾に追加します。O(V+E)という明快な線形時間で最短経路を求められます。⚡
よくある質問
「Deque による 0-1 BFS」レッスンは無料ですか？
はい。「Deque による 0-1 BFS」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。
「Deque による 0-1 BFS」で何を学びますか？
重みが 0 または 1 のときの最短経路を求めます ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Competitive Programming Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。
「Deque による 0-1 BFS」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCompetitive Programming Academyレッスンでコードを書いて実行できますか？
はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- ヒープを使う Dijkstra 法
- Deque による 0-1 BFS
- Bellman-Ford と負辺
- Floyd-Warshall 全点対最短経路