ダイクストラ法の解説とPythonでの実装例

ダイクストラ法は、グラフ上の最短経路問題を解くためのアルゴリズムの一つです。具体的には、与えられた始点から各頂点への最短距離を求めることができます。以下では、ダイクストラ法のアルゴリズムと、Pythonでの実装を行います。

ダイクストラ法のアルゴリズム

このアルゴリズムは、貪欲法に基づいています。具体的には、始点から各頂点への最短距離が確定した頂点集合Sに含まれない頂点のうち、始点からの距離が最小のものを選び、その頂点をSに加えていくことで、最短距離を更新していくというアプローチを取ります。

ダイクストラ法は以下のような手順で動作します。

初期化
- スタート地点から各頂点までの最短距離を無限大、最短経路を空に設定する。
- スタート地点から自分自身への最短距離を0に設定する。
スタート地点を訪問済みとする。
スタート地点から直接つながっている頂点について、スタート地点からの距離を計算する。
計算した距離が現在の最短距離よりも短い場合、最短距離を更新する。
まだ訪問していない頂点のうち、最短距離が最小のものを次に訪問する。
3-5の手順を繰り返し、全ての頂点を訪問し終えるまで繰り返す。

ダイクストラ法は、負の辺がないグラフに対しては正しい結果を返しますが、負の辺がある場合には正しい結果を返さないことがあります。また、負の辺がある場合でも、始点から到達可能な頂点については最短経路を求めることができます。

pydocument.hatenablog.com

Pythonでのダイクストラ法の実装例

以下は、ダイクストラ法をPythonで実装した例です。グラフの辺は隣接行列で表現されており、始点からの最短距離を示すdistanceリストを返します。

import sys

def dijkstra(graph, start):
    # 初期化
    n = len(graph)
    visited = [False] * n
    distance = [sys.maxsize] * n
    distance[start] = 0

    # ダイクストラ法
    for i in range(n):
        # 未処理の中で最小の距離を持つ頂点を探す
        min_distance = sys.maxsize
        for j in range(n):
            if not visited[j] and distance[j] < min_distance:
                min_distance = distance[j]
                u = j

        # 訪問済みにする
        visited[u] = True

        # uから到達可能な頂点の距離を更新する
        for v in range(n):
            if not visited[v] and graph[u][v] != 0:
                new_distance = distance[u] + graph[u][v]
                if new_distance < distance[v]:
                    distance[v] = new_distance

    return distance

この関数を以下のように使うことができます。ここでは、グラフの辺を隣接行列で表現しています。

graph = [
    [0, 2, 4, 0, 0],
    [2, 0, 1, 4, 0],
    [4, 1, 0, 1, 3],
    [0, 4, 1, 0, 1],
    [0, 0, 3, 1, 0]
]

start = 0
distance = dijkstra(graph, start)
print(distance) # [0, 2, 3, 5, 6]

上記の例では、グラフを隣接行列で表現していますが、隣接リストで表現することもできます。隣接リストの場合は、graphの各要素がリストとなり、リスト内のタプルに頂点と辺の距離が格納されています。以下は、隣接リストを使った実装例です。

import sys
import heapq

def dijkstra(graph, start):
    # 初期化
    n = len(graph)
    visited = [False] * n
    distance = [sys.maxsize] * n
    distance[start] = 0
    pq = [(0, start)]

    # ダイクストラ法
    while pq:
        # 未処理の中で最小の距離を持つ頂点を取り出す
        dist, u = heapq.heappop(pq)
        if visited[u]:
            continue

        # 訪問済みにする
        visited[u] = True

        # uから到達可能な頂点の距離を更新する
        for v, weight in graph[u]:
            if not visited[v]:
                new_distance = distance[u] + weight
                if new_distance < distance[v]:
                    distance[v] = new_distance
                    heapq.heappush(pq, (new_distance, v))

    return distance

この関数を以下のように使うことができます。ここでは、グラフの辺を隣接リストで表現しています。

graph = [
    [(1, 2), (2, 4)],
    [(0, 2), (2, 1), (3, 4)],
    [(0, 4), (1, 1), (3, 1), (4, 3)],
    [(1, 4), (2, 1), (4, 1)],
    [(2, 3), (3, 1)]
]

start = 0
distance = dijkstra(graph, start)
print(distance) # [0, 2, 3, 5, 6]

上記の例では、ヒープを使った実装方法が示されています。この方法では、頂点の最小距離を維持するために、未処理の頂点の中で最小の距離を持つ頂点を効率的に探すことができます。一方、ヒープを使わない場合は、未処理の中で距離が最小の頂点を線形探索する必要があるため、処理時間が増加します。

Pythonにはheapqモジュールが標準で含まれており、ヒープを使った処理を簡単に実装することができます。heapqモジュールには、heappush、heappop、heapreplace、heappushpop、heapify関数があります。上記の例では、heappushとheappopを使っていますが、heapifyを使ってヒープを構築し、heapreplaceを使って最小要素を更新することもできます。