はじめに
先日のZONeコンでダイクストラの定数倍高速化が大事な問題が出たので、ダイクストラ典型問題である、ABC192Eの実装をもとに手法をまとめる。
初期実装
def divceil(n, k): return 1+(n-1)//k # n/kの切り上げを返す
def main():
n, m, x, y = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(m):
s, t, tm, km = map(int, input().split())
s -= 1
t -= 1
graph[s].append((t, tm, km))
graph[t].append((s, tm, km))
mindist = [-1] * n
hq = []
heappush(hq, (0, x-1))
while hq:
dist, node = heappop(hq)
if mindist[node] != -1:
continue
mindist[node] = dist
for i, t, k in graph[node]:
if mindist[i] != -1:
continue
heappush(hq, (divceil(dist, k)*k+t, i))
print(mindist[y-1])
これは最もシンプルなダイクストラの実装。mindistをhheapqから取り出した順に確定していき、mindistが確定していない頂点をheapqに突っ込んでいる。
枝刈り高速化⓵ heapqからゴールを取り出した時点でbreak
def divceil(n, k): return 1+(n-1)//k # n/kの切り上げを返す
def main():
n, m, x, y = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(m):
s, t, tm, km = map(int, input().split())
s -= 1
t -= 1
graph[s].append((t, tm, km))
graph[t].append((s, tm, km))
mindist = [-1] * n
hq = []
heappush(hq, (0, x-1))
while hq:
dist, node = heappop(hq)
if node==y-1:
print(dist)
return
if mindist[node] != -1:
continue
mindist[node] = dist
for i, t, k in graph[node]:
if mindist[i] != -1:
continue
heappush(hq, (divceil(dist, k)*k+t, i))
print(-1)
最も簡単なダイクストラの枝刈りは、heapqが空になるのを待たずにheapqから取り出されて確定した頂点がゴールの時点で結果を出力して終了すること。これは、ダイクストラが使える単一始点最短経路問題の中でも、終点も単一の場合に使用することが出来る。
枝刈り高速化②heapqに入れる値を制限
def divceil(n, k): return 1+(n-1)//k # n/kの切り上げを返す
def main():
n, m, x, y = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(m):
s, t, tm, km = map(int, input().split())
s -= 1
t -= 1
graph[s].append((t, tm, km))
graph[t].append((s, tm, km))
mindist = [10**20] * n
fixed=[False]*n
hq = []
heappush(hq, (0, x-1))
while hq:
dist, node = heappop(hq)
if node==y-1:
print(dist)
return
if fixed[node]:
continue
fixed[node] = True
for i, t, k in graph[node]:
if divceil(dist, k)*k+t >= mindist[i]:
continue
heappush(hq, (divceil(dist, k)*k+t, i))
mindist[i]=divceil(dist, k)*k+t
print(-1)
このスライドの14~15ページ目と同じ。mindistを、heapqから取り出して確定した距離ではなく、heapqに入れた暫定の最短距離とする。heapqに入れる時に、暫定の最短距離を確認して、それより長い場合heapqに入れないことで、heapqに入れる値の数を減らして、枝刈りすることができる。ただし、距離が確定したかどうかの配列を別に作るので、元から速い場合さらなる高速化にはならないこともある。
別実装
https://atcoder.jp/contests/abc192/submissions/22259820
距離が確定したかどうかの配列を作らずに、暫定最短距離と取り出した距離が同じ時に探索する手法
距離が確定したかどうかの配列を作らない分、同じ頂点を複数回探索する可能性があるので高速化するかどうかは微妙
枝刈り高速化③heapqにタプルではなく数値を入れる
def divceil(n, k): return 1+(n-1)//k # n/kの切り上げを返す
def main():
n, m, x, y = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(m):
s, t, tm, km = map(int, input().split())
s -= 1
t -= 1
graph[s].append((t, tm, km))
graph[t].append((s, tm, km))
mindist = [10**20] * n
fixed=[False]*n
hq = []
op=lambda d,i:d*n+i
heappush(hq, op(0, x-1))
while hq:
dist, node = divmod(heappop(hq),n)
if node==y-1:
print(dist)
return
if fixed[node]:
continue
fixed[node] = True
for i, t, k in graph[node]:
if divceil(dist, k)*k+t >= mindist[i]:
continue
heappush(hq, op(divceil(dist, k)*k+t, i))
mindist[i]=divceil(dist, k)*k+t
print(-1)
heapqに入れる時、タプルではなく数値の方が高速に動作する。そこで、2つの数値を商と余りとして1つの数値にまとめて保持しておくことで、高速化が見込める。ただしこれも、タプルから数値の計算と数値からタプルの復元が必要なので、元から速い場合さらなる高速化にはならないこともある。
タプル⇔数値相互変換ライブラリ
2値のタプルと数値の変換ならまだ書きやすいが、3値以上のタプルと数値の変換を直接書くと、コードが汚くなってしまうので、クラスとして処理できる自作ライブラリを紹介する。コンストラクタで、変換したい値のそれぞれの最大値のリストを渡すと、packingでタプルを数値に、unpackingで変換した数値をタプルに戻すことが出来る。使用例は下記ZONeコンE実践例を参照。
class tuplepacking:
def __init__(self,maxsizelist):
self.n=len(maxsizelist)
self.maxsizelist=tuple(maxsizelist)
def packing(self,*tuples):
ans=0
for size,tu in zip(self.maxsizelist,tuples):
ans*=size
ans+=tu
return ans
def unpacking(self,value):
ans=[0]*self.n
for i in range(self.n)[::-1]:
value,ans[i]=divmod(value,self.maxsizelist[i])
return ans
ZONeコンEを上記枝刈り高速化を用いて愚直ダイクストラで通す
こちらの問題では、下方向の複数通りの遷移を、頂点拡張でうまく1つにまとめることで計算方法を削除することが想定解だが、下方向の複数通りの遷移を愚直にループ回しても上記のような適切な枝刈り高速化で間に合わせることが出来る。
枝刈り高速化①,②使用 1728ms
枝刈り高速化①,②,③全部使用 1253ms
枝刈り高速化②,③使用 1229ms
まとめ
ダイクストラは色々な実装があり、その違いで実行時間が大きく変わることもあるので奥が深い