概要
ダイクストラ法は、非負な辺重みをもつグラフが与えられたときに、スタート地点から各地点までの最短距離を求めるアルゴリズムです。頂点数 $V$, 辺数 $E$ で辺の重みが非負なグラフが与えられたとき、ダイクストラ法の計算量は愚直にやると $O(V^2)$, 優先度付きキュー（二分ヒープ）を使うと $O((V+E)\log V)$ です（Fibonacci heap や（整数重みの場合） radix heap を使うとより高速になるらしいですが、ここでは扱いません）。優先度付きキューではなく（複数の）キューを使って計算量を落とす事例をいくつか勉強したのでこのメモにまとめます。
参考文献
ダイクストラ法高速化いろいろ(yosupot さん)
01-BFSのちょっと丁寧な解説（アルメリアさん）
[Dial’s Algorithm (Optimized Dijkstra for small range weights): geek for geeks]
(https://www.geeksforgeeks.org/dials-algorithm-optimized-dijkstra-for-small-range-weights/)
学術的な参考文献は詳しくないので、 英語版Wikipedia を参照してください。
ダイクストラ法
密グラフに対するダイクストラ法の python風疑似コードを以下に示します。g[v][w]で辺vwの重みを表します（隣接行列表現）。トータルの計算量は $O(V^2)$ です。
dist = [float('inf')]*V
dist[start] = 0
for _ in range(V):
未確定頂点のうち、スタートからの暫定距離 dist[v] が最も小さい頂点 v0 を確定状態にする
for 未確定頂点 u:
dist[u] = min(dist[u], dist[v0] + g[v0][u])
疎なグラフの場合、「スタートからの暫定距離が最も小さいもの」を取り出すために優先度付きキューを使うと効率化できます。 python のコード例を以下に示します。
from heapq import *
def dijkstra(g,V,start): # g: グラフの隣接リスト表現
dist = [float('inf')]*V # start からの最短距離
dist[start] = 0
q = [(0,start)] #(そこまでの距離、頂点)
while q:
dv,v = heappop(q)
if dist[v] < dv: continue
for to, cost in g[v]:
if dv + cost < dist[to]:
dist[to] = dv + cost
heappush(q, (dist[to], to))
return dist
辺の重みがすべて等しい場合（幅優先探索）
辺の重みがすべて等しい場合は、幅優先探索により $O(V+E)$ で問題が解けます。幅優先探索についてはdrkenさんの記事をご覧ください。ここで大事な事実: 幅優先探索で持つキューの中身は、自動的に距離順でソートされた状態になっています。このおかげで、優先度付きキューではなくただのキューで「未確定頂点のうち、スタートからの暫定距離が最も小さいもの」を pop できます。この例のように、優先度付きキューを使わずに「距離順でソートされた状態」を実現できると嬉しいです。
辺の重みが 0,1,...,W の場合 (Dial's algorithm)
$2$ 点が何本かの辺をたどってつながっているとき、辺をたどるときに踏む頂点にダブりがないようにできるので、2点間の距離は $W(V-1)$ 以下です。よって、この個数だけバケットを持つバケット法をすれば、「最小のものを取り出す」部分を優先度付きキューなしで実現できます。要するに、q[i]を「スタートからの道のりが $i$ となる点を入れる箱」として、q[0]が空になるまで見る -> q[1]が空になるまで見る -> ... としてやればよいです。計算量は $O(WV+E)$ です。
なお、各キューを連結リストとして管理すれば、陽に $WV$ 個のキューを持たずとも長さ $WV$ の配列を管理すればよいようです。yaketake08さんの実装
キューを W+1 個持つ実装
Dial's algorithm の過程で、いま見ているキューがq[i]だとしましょう。このとき最大重みが $W$ なので、空でないキューは q[i], ..., q[i+W] の $W+1$ 個です。よって $W+1$ 個のキューを使いまわすことでも Dial's algorithm が実装できます。具体的には、q[i]にいる頂点から重み $c$ の辺を伸ばした先の頂点はq[(i+c)%(W+1)]に入れます。python による参考実装として リンク先（AOJ: ALDS1_12_Bの提出） をご覧ください。（なお、各バケットとしてキューではなくスタックを使うこともできます）
辺の重みが 0 or 1 の場合（いわゆる01BFS）
この場合はさらにシンプルに、deque を1つ持つだけでOKです。辺の重みが $0$ なら appendleft, 重みが $1$ ならappendすれば、deque の中身は距離順でソートされた状態になっています。このアルゴリズムは俗に 01BFS と呼ばれています。計算量は $O(V+E)$ です。詳しい解説や実装などはアルメリアさんの記事などをご覧ください。
辺の重みが k 種類の場合
辺の重みが $a,b$ の $2$ 種類の場合で説明します。qa,qbという2つのキューを用意します。pop するときは、qa[0]とqb[0]のうち小さいほうを pop します（ここで qa[0] はキューの先頭の値です。 c++ のqa.front()に相当します）。push するときは、辺の重みが $a$ なら qa に、辺の重みが $b$ なら qb に push します。こうすれば、それぞれのキューの中身は距離順でソートされた状態になっています。pop するときに毎回 $k$ 個の値の最小値を計算するので、計算量は $O(k(V+E))$ です。また、コメントでご指摘がありました通り、最小値を優先度つきキューなどで管理すれば計算量は $O((\log k)(V+E))$ となります（2020/8/26 追記）。もしこのアルゴリズムの名前をご存じの方がいれば教えてください。
応用例
このアルゴリズムを応用して、次の問題を$O(N)$ 回の演算回数で解くことができます。
問題 $2^a3^b5^c$の形の正整数を小さい順に$N$個列挙せよ。
q2,q3,q5という $3$ つのキューを用意します。pop するときは、min(q2[0],q3[0],q5[0])を pop します。$x$ が popされたとき、$2x$ をq2に、$3x$ をq3に、$5x$ をq5に pushする...としたいですがこれはダメです。たとえば $6 = 2\cdot 3 = 3\cdot 2$ が 2 回 push, pop されます。
なので、q2,q3,q5という $3$ つのキューを「最小素因数がそれぞれ $2,3,5$ となる値をためるキュー」と思って以下のように push すれば、最終的に各値がちょうど1回ずつ push, pop されます。
- $x$ が
q2から pop されたとき、 $2x$ をq2に push - $x$ が
q3から pop されたとき、 $2x$ をq2に、$3x$ をq3に push - $x$ が
q5から pop されたとき、 $2x$ をq2に、$3x$ をq3に、$5x$ をq5に push
(2020/9/11追記：コードの定数倍が悪かったので差し替えました)
from collections import deque
n = 16
res = [1]*n
q = [deque(),deque(),deque()]
min_values = [2,3,5]
for i in range(1,n):
res[i] = v = min(min_values)
idx = min_values.index(v)
q[0].append(2*v)
if idx >= 1:
q[1].append(3*v)
if idx >= 2:
q[2].append(5*v)
min_values[idx] = q[idx].popleft()
print(res) #[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25]
過去のコード
from collections import deque
n = 15
res = [1]*n
q = [deque([2]),deque([3]),deque([5])]
f = lambda i: q[i][0]
for i in range(1,n):
idx = min(range(3), key = f)
res[i] = v = q[idx].popleft()
q[0].append(2*v)
if idx >= 1:
q[1].append(3*v)
if idx >= 2:
q[2].append(5*v)
print(res) #[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24]