search
LoginSignup
5
Help us understand the problem. What are the problem?

More than 1 year has passed since last update.

posted at

ダイクストラの枝刈り高速化まとめ【python実装】

はじめに

先日のZONeコンでダイクストラの定数倍高速化が大事な問題が出たので、ダイクストラ典型問題である、ABC192Eの実装をもとに手法をまとめる。

初期実装

dijkstrasimple.py
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

dijkstraeda1.py
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に入れる値を制限

dijkstraeda2.py
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にタプルではなく数値を入れる

dijkstraeda3.py
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実践例を参照。

tuplepacking.py
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

枝刈り高速化①,③使用 1TLE

まとめ

ダイクストラは色々な実装があり、その違いで実行時間が大きく変わることもあるので奥が深い

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
5
Help us understand the problem. What are the problem?