Pythonでダイクストラ法(Dijkstra's algorithm)を実装してみる-ABC012
本記事ではダイクストラ法の全体的な流れを確認したあとに実際に例題をPythonで解いていきます。
ダイクストラ法とは
実装する前にダイクストラ法がどのようなアルゴリズムなのかを知る必要があります。
ダイクストラ法がどのような動きをするのかを確認するには文章や画像よりも動画を見た方が理解しやすいと思います。
そこで、以下のヨビノリさんの動画がダイクストラ法について非常にわかりやすく説明されているので、全体的な流れを確認するのに最適です。
www.youtube.com
ヨビノリさんの動画を見て思った方もいるかもしれませんが、ダイクストラ法の基本的な考え方は貪欲法です。
最短距離でいけるところを選んで距離をひたすら更新していきます。
ダイクストラ法は最短経路問題を解くためのアルゴリズムですが、最短経路問題を解くためのアルゴリズムは他にもあります。
したがって、どのような場面でどの最短経路を解くアルゴリズムが最適なのかを考えることが重要です。
それぞれのアルゴリズムの使い道は以下の通りです。
- ダイクストラ法：辺の重みがバラバラで非負数
- ベルマンフォード法：辺の重みがバラバラで負数あり
- ワーシャルフロイド法：グラフ上のあらゆる2頂点間の最短経路
また、辺の重みが全て同じ場合は幅優先探索などもあります。
例題
それでは実際に以下の問題を解いていきます。
問題文
高橋君は、バスがあまり好きではありません。ですが、社会に出ると、バスを乗るという行為を避けることはできません。
社会人になると、自宅から会社まで、バスで通わなければなりません。高橋君はまだ内定を貰っていないので、会社の場所は解りません。
高橋君は、バスに乗っている時間が最も長くなってしまうような、最悪のケースを常に想定します。 この、最悪なケースのバスに乗っている時間が、出来るだけ短くなるような場所に引っ越そうと思っています。
なお、最悪のケースとは、バスに乗る時間の合計が最も短くなるように、乗るバスを選択した時に、最もバスに乗る時間の合計が長くなってしまうような位置に会社があるケースのことを指します。また、自宅から会社に行く際に、高橋君が乗るバスを選ぶことができ、高橋君はバスに乗る時間の合計が最も短い経路を選択するものとします。
各バスは、2つのバス停を往復するように走っており、行き・帰りでかかる時間に差はありません。 バスにはいつでも乗ることが可能であり、乗継にかかる時間などは無視することが可能です。
また、自宅や会社はバス停に隣接しており、他のバス停まで歩いたり、バス以外の手段で移動することはできません。
高橋君が引っ越すべき場所を求め、そこに引っ越した際の、バスに乗らなければならない時間の最大値を出力してください。
実装
それではいよいよPythonで実装していきます。
最小値を取り出すときに優先度付きキューを使うことで計算量を減らすことができます。
import heapq def dijkstra(s): hq = [(0, s)] heapq.heapify(hq) # リストを優先度付きキューに変換 cost = [float('inf')] * n # 行ったことのないところはinf cost[s] = 0 # 開始地点は0 while hq: c, v = heapq.heappop(hq) if c > cost[v]: # コストが現在のコストよりも高ければスルー continue for d, u in e[v]: tmp = d + cost[v] if tmp < cost[u]: cost[u] = tmp heapq.heappush(hq, (tmp, u)) return cost n,m = map(int,input().split()) e = [[] for _ in range(n)] for _ in range(m): a,b,t = map(int,input().split()) a,b = a-1, b-1 e[a].append((t, b)) e[b].append((t, a)) ans = float('inf') for i in range(n): dist = dijkstra(i) ans = min(ans, max(dist)) print(ans)
ちなみにこの問題はちらっと説明したベルマンフォード法で解くこともできます。
