dijkstra

date: 2021-04-25 excerpt: ダイクストラ法について

tag: algorithm network dijkstra ダイクストラ法

ダイクストラ法(dijkstra)について

幅優先探索、深さ優先探索以外の、コスト付き(優先度付き)探索である
優先度の並び替えに計算量が\(O(log N)\)のheapキューを用いる
- よくある展開として、最もコストが安い順にネットワークをたどるなど
- bfsを2分探索したほうが計算コストが安いこともあり、適応を見極める必要がある
計算量は\(O((E+V)logV)\)なので、辺の\(V\)が多いときはワーシャルフロイド法よりも早い

例; 典型的な最短経路問題(何度か繰り返す)

問題

AtCoder Beginner Contest 160; D - Line++

解説

途中が短絡しているところをコストを0とした最短経路問題と読み替えることができる
ワーシャルフロイド法の方が軽いと思ったがTLEしたので、多分、dijkstraの方が軽い

解答

N,X,Y=map(int,input().split())
X-=1; Y-=1
import heapq
import collections
 
Entity = collections.namedtuple("Entity", ["node", "w"])
Entity.__lt__ = lambda self, other: self.w <= other.w
 
G = [[] for _ in range(N)]
for n in range(N-1):
    G[n].append(Entity(n+1,1))
    G[n+1].append(Entity(n,1))
G[X].append(Entity(Y, 1))
G[Y].append(Entity(X, 1))
 
def dijkstra(start) -> "List":
    dist = [-1 for _ in range(N)]
    dist[start] = 0
    que = []
    heapq.heappush(que, Entity(start, 0))
    done = [False for _ in range(N)]
    while que:
        i, w = heapq.heappop(que)
        # すでに訪れたところは処理しない
        if done[i]:
            continue
        done[i] = True
        for j, c in G[i]:
            # 評価が未知のエッジ or より安くなる可能性がある場合は探索し、結果をヒープに入れる
            if dist[j] == -1 or dist[j] > dist[i] + c:
                dist[j] = dist[i] + c
                heapq.heappush(que, Entity(j, dist[j]))
    return dist
 
cnt = collections.defaultdict(int)
for n in range(N):
    dist = dijkstra(n)
    # print(dist)
    for i in range(n+1, N):
        cnt[dist[i]] += 1
 
for k in range(1, N):
    print(cnt[k])

例; 典型的な最短経路問題

問題

典型アルゴリズム問題集; D - 単一始点最短経路問題
解説
経路の長さがcのパラメータで与えられた場合
回答

import heapq

N, M = map(int, input().split())
G = [[] for _ in range(N)]

for _ in range(M):
    u, v, c = map(int, input().split())
    G[u].append((v,c))
 
dist = [-1 for _ in range(N)]
dist[0] = 0
Q = []
heapq.heappush(Q, (0,0)) # 距離d, 頂点iの順
done = [False for _ in range(N)]
 
while len(Q) > 0:
    d, i = heapq.heappop(Q)
    # すでに訪れたところは処理しない
    if done[i]:
        continue
    done[i] = True
    for j, c in G[i]:
        # 評価が未知のエッジ or より安くなる可能性がある場合は探索し、結果をヒープに入れる
        if dist[j] == -1 or dist[j] > dist[i] + c:
            dist[j] = dist[i] + c
            heapq.heappush(Q, (dist[j], j))
print(dist[N-1])

例; 折返しのある最短経路問題(行って戻ってくるまでの最短経路)

問題

AtCoder Beginner Contest 191; E - Come Back Quickly

解説

折返しがあるので有方向でグラフを定義する
一度たどった道かどうかを管理するのではなく、何回通ったかを管理する(管理しなくても解けるが計算量が大幅に増える)

回答

import collections
import heapq
import math

N,M=map(int,input().split())
G = collections.defaultdict(list)

for _ in range(M):
    u, v, c = map(int, input().split())
    G[u-1].append((v-1,c))

for n in range(N):
    dist = [math.inf for _ in range(N)]
    Q = []
    heapq.heappush(Q, (0,n)) # 距離d, 頂点iの順
    flag = True
    nums = [0]*N
    while Q:
        d, i = heapq.heappop(Q)
        # 帰り際であったら終了する
        if i == n and d > 0:
            print(d)
            flag = False
            break
        # 行き帰りで二回だからたかだか二回に限定する
        if nums[i] >= 2:
            continue
        nums[i] += 1
        for j, c in G[i]:
            # より安くなる可能性がある場合は探索し、ノードをヒープに入れる
            if dist[j] > d + c:
                dist[j] = d + c
                heapq.heappush(Q, (dist[j], j))
    if flag:
        print(-1)

例; 最大許容積載量

問題

No.1473 おでぶなおばけさん

解説
各通路の最大積載量をマイナスし、経路のコストを足し合わせる代わりに、最大のコスト(つまり最小の積載量)を次に繋げる

提出

def dijkstra():
    weights = [None for _ in range(N)]
    que = []
    heapq.heapify(que)
    heapq.heappush(que, (math.inf, 0)) # weight, index
    nums = [0]*N
    while que:
        '''
        aw: accumlated weight
        nw: next weight
        '''
        aw, i = heapq.heappop(que)
        if weights[i] and aw <= weights[i]:
            continue
        weights[i] = aw
        for j, nw in G[i]:
            nw = min(aw, nw)
            heapq.heappush(que, (nw, j))
    ans = weights[N-1]
    return ans

例; greedyっぽさがある最短経路問題

問題

AtCoder Beginner Contest 192; E - Train

解説

特定の倍数のときだけ通れるということであるが、シンプルに累積コストを計算しておき、累積コストが小さいものから順に見ていく

import collections
import heapq
import math

N,M,X,Y=map(int,input().split())
X-=1
Y-=1

G = collections.defaultdict(list)

for _ in range(M):
    A,B,T,K = map(int, input().split())
    G[A-1].append((B-1,T,K))
    G[B-1].append((A-1,T,K))

cost = [math.inf for _ in range(N)]
que = []
heapq.heapify(que)
heapq.heappush(que, (0, X)) # コスト
nums = [0]*N
while que:
    '''
    ac: accumlated cost
    nc: next cost
    '''
    ac, i = heapq.heappop(que)
    if ac > cost[i]:
        continue
    cost[i] = ac

    for j, t, k in G[i]:
        nc = ac
        if ac%k != 0:
            nc += k - ac%k
        nc += t
        heapq.heappush(que, (nc, j))

if cost[Y] is math.inf:
    print(-1)
else:
    print(cost[Y])

例; 典型的なdijkstra適応例

問題

第７回日本情報オリンピック予選（過去問）;F - 船旅

解答

import heapq

def dijkstra(s, t, G):
    dist = [float('inf') for _ in range(N)]
    dist[s] = 0
    que = []
    heapq.heapify(que)
    heapq.heappush(que, (0,s)) # 距離d, 頂点iの順
    done = [False for _ in range(N)]
    while que:
        d, i = heapq.heappop(que)
        # すでに訪れたところは処理しない
        if done[i]:
            continue
        done[i] = True
        for j, c in sorted(G[i]):
            # 評価が未知のエッジ or より安くなる可能性がある場合は探索し、結果をヒープに入れる
            if dist[j] > dist[i] + c:
                dist[j] = dist[i] + c
                heapq.heappush(que, (dist[j], j))
    print(dist[t] if dist[t] != float('inf') else -1)

N, K = map(int, input().split())
G = [[] for _ in range(N)]
Q = []
for _ in range(K):
    lst = list(map(int, input().split()))
    if lst[0] == 0:
        a, s, t = lst
        s-=1
        t-=1
        dijkstra(s,t,G)
    else:
        a, s, t, w = lst
        s-=1
        t-=1
        G[s].append((t, w))
        G[t].append((s, w))

例; 典型的なグリッドのdijkstra適応例

問題

AtCoder Beginner Contest 020; C - 壁抜け

解説

実装が面倒なのでテンプレート化していると楽

解答

import heapq
import collections

H, W, T = map(int,input().split())
G = [list(input()) for _ in range(H)]

for h in range(H):
    for w in range(W):
        if G[h][w] == "S":
            s = (h, w)
        if G[h][w] == "G":
            t = (h, w)

def dijkstra(s: "Tuple", G, CMax):
    dist = collections.defaultdict(lambda :float("INF"))
    dist[s] = 0
    done = collections.defaultdict(lambda :False)

    que = []
    heapq.heapify(que)
    heapq.heappush(que, (0,s)) # 距離d, 頂点iの順
    while que:
        d, i = heapq.heappop(que)
        if done[i]:
            continue
        done[i] = True
        for dh,dw in [(1,0), (0, 1), (-1, 0), (0, -1)]:
            jh, jw = i[0] + dh, i[1] + dw
            if not (0 <= jh < H and 0 <= jw < W):
                continue
            if G[jh][jw] == "#":
                c = CMax
            elif G[jh][jw] == "G":
                c = 1
            else:
                c = 1
            j = (jh,jw)
            if dist[j] > dist[i] + c:
                dist[j] = dist[i] + c
                heapq.heappush(que, (dist[j], j))
    return dist

def is_ok(n):
    dist = dijkstra(s, G, CMax=n)
    if dist[t] <= T:
        return True
    else:
        return False

def meguru_bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok
print(meguru_bisect(10**20, 0))

例; 最短経路を構成する経路の数は何通りあるか

問題

AtCoder Beginner Contest 211; D - Number of Shortest paths

解説

dijkstraを改造することまでは発想が行き着く
何通りあるか、なのでdpのように解くことを試みる
初期値を1として前の頂点にいるときの数をどんどん累積していく(辺が２つ以上から参照されるとき、合算するので増える)
グラフdp的

解答

cont = [0 for n in range(N)]
cont[0] = 1 # グラフdp的変数
def dijkstra2(start) -> "List":
    dist = [-1 for _ in range(N)]
    dist[start] = 0
    que = []
    heapq.heappush(que, Entity(start, 0))
    done = [False for _ in range(N)]
    while que:
        (i, w) = heapq.heappop(que)
        for (j, c) in G[i]:
            if dist[j] == -1:
                dist[j] = dist[i] + c
                cont[j] = cont[i] # 初めてのノードでは配る
                heapq.heappush(que, Entity(j, dist[j]))
            elif dist[j] == dist[i] + c:
                cont[j] += cont[i] # 最短の経路であると期待されるときは足し合わせる
                cont[j] %= MOD
    return dist
dist = dijkstra2(0)
print(cont[N-1])

長いので一部のみ掲載
提出