【AtCoder】ダイクストラ法の使用するタイミング＆テンプレート

初めに

ダイクストラ法のテンプレートを作成しました。私自身、ダイクストラ法の問題にあたった経験は少なく、今後解く問題次第ではコードを改良する場合があります。

今回ダイクストラ法のテンプレートを作った理由ですが、使用するリストが多く実装に手間取ったからです。さらに時間制限の都合上AtCoderの問題では ${O(NlogN)}$のダイクストラを実装する必要のある場合が多く（${O(N^2)}$ のダイクストラもありますがこれだと時間が間に合わない）そのためにはヒープなど考える必要がありますが慣れていなくて面倒だったからです。

ダイクストラ（ヒープ使用）のテンプレート

dijkstra.py

import heapq

#必要な物：ノード数、テーブル（重み,ノード番号）、スタート、終了
def dijkstra(n,table,start,finish):
    visit = [False]*(n+2) #訪問行列
    length = [float("inf")]*(n+2) #startから各ノードまでの最短経路の長さ
    
    #準備＝＝＝＝＝＝＝＝＝＝
    length[start]=0#スタートの長さは０
    hp = []#未訪問の最短経路を記録
    heapq.heappush(hp,(0,start))#（0,start）＝（重み、ノード番号） #スタートを追加
    #＝＝＝＝＝＝＝＝＝＝＝＝
    
    
    while(hp):
        w,x = heapq.heappop(hp)
        
        if(visit[x]==True):
            #既に訪問が完了しているノードなので以下の操作は行わない。continueする。
            continue
        visit[x]=True
        
        for l,y in table[x]:
            if(not visit[y] and (length[y]>w+l)):
                length[y]=w+l
                heapq.heappush(hp,(length[y],y))
    
    #return length[n] #ノードnまでの最短経路を返す場合
    #return length #各ノードの最短路の長さを返す場合

引数は、dijkstra( ①ノード数 , ②テーブル , ③開始地点 , ④終了地点 ) テーブルは二次元リストであり、table[1]には、「ノード1と繋がっている（ノード１から移動できる）ノードの情報（移動の際に通る辺の重みなど）」が記録されています。
上のコード文では、必要に応じて戻り値を複数指定してあります。（コメントアウトしてあります。）

ダイクストラ法を使用するタイミング

私自身解説を見て初めてダイクストラ法で解ける問題であることを知る場合がほとんどでした。下２問はダイクストラで解けることに私が気づかなかった問題です。

ABC340 D問題

ABC192 E問題

この問題を解いた当時は、問題文を読んで「あ、これダイクストラ法だ」と瞬時に判断できることは難しいと感じました。上の２問から判断した、ダイクストラ法を見破るためのポイントを下にまとめます。（このポイントは自分の精進によって、変更される可能性があります。）

・グラフを使いそうなとき
・最短経路を知りたがっているとき（←これ大事なのではないか）
・グラフが有向グラフであるとき（無向でも良いが訪問行列を作る）
・辺に重みが関わっているとき（←重みが全て１の時もあった。）

これを書いているときに「BFSと指定されている問題でダイクストラ使えるのではないか？」と思って手を付けてみたら、ダイクストラは最短経路を求める物ということに気づきました。

結論

辺に重みが存在していて、(全部重み１とかになっていることもある。)最短経路が絡んでいるときはダイクストラ法です。

中々目にすることも少ない気がしますが、珍しいからこそコンテストで遭遇したときは確実に獲りたいです、