Pythonで学ぶ最短経路探索~ダイクストラ法の実装~

はじめに

こんにちは！今回は、Pythonを使って「ダイクストラ法」を実装し、グラフ上の最短経路を求めるプログラムを紹介します。ダイクストラ法は、グラフ理論において単一始点から他のすべての頂点への最短経路を求めるアルゴリズムです。ネットワークのルーティングや地図アプリの経路検索でよく使われています。

ダイクストラ法とは？

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

1. 各頂点への最短距離を無限大(inf)で初期化
2. 始点から訪問可能な頂点を優先度付きキュー(heapq)を使って管理
3. 隣接頂点への距離を計算し、より短い経路が見つかった場合は距離と経路を更新
4. すべての頂点が探索されるまで繰り返し

実装コード

以下のダイクストラ法の実装例を示します。

import heapq

def dijkstra(adj_matrix, start_node):
    """
    ダイクストラ法を用いて始点から各頂点への最短距離を求める関数

    Args:
        adj_matrix: グラフを表す隣接行列 (リストのリスト)
        start_node: 始点 (0から始まるインデックス)

    Returns:
        distances: 各頂点への最短距離を表すリスト
        paths: 各頂点への最短経路を表すリスト
    """
    num_nodes = len(adj_matrix)
    distances = [float('inf')] * num_nodes  # 各頂点への距離を無限大で初期化
    paths = [[] for _ in range(num_nodes)]  # 各頂点への経路を空リストで初期化
    distances[start_node] = 0  # 始点への距離を0で初期化
    paths[start_node] = [start_node + 1]  # 始点への経路を始点自身で初期化

    priority_queue = [(0, start_node)]  # 優先度付きキューを初期化

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)  # 優先度付きキューから最小の距離の頂点を取り出す

        if current_distance > distances[current_node]:  # 現在の距離が既に記録されている距離よりも大きい場合はスキップ
            continue

        for neighbor_node in range(num_nodes):  # 全ての頂点をループ
            weight = adj_matrix[current_node][neighbor_node]  # 現在の頂点から隣接頂点への重み

            if weight > 0:  # 重みが0より大きい場合 (接続されている場合)
                distance = current_distance + weight  # 隣接頂点への距離を計算

                if distance < distances[neighbor_node]:  # 計算した距離が既に記録されている距離よりも小さい場合
                    distances[neighbor_node] = distance  # 距離を更新
                    paths[neighbor_node] = paths[current_node] + [neighbor_node + 1]  # 経路を更新
                    heapq.heappush(priority_queue, (distance, neighbor_node))  # 優先度付きキューに隣接頂点を追加

    return distances, paths

実行例

# 隣接行列
adj_matrix = [
    [0, 10, 55, 20, 0, 0, 0, 0],
    [10, 0, 0, 0, 20, 40, 0, 0],
    [55, 0, 0, 0, 0, 10, 15, 0],
    [20, 0, 0, 0, 20, 0, 55, 0],
    [0, 20, 0, 20, 0, 10, 0, 0],
    [0, 40, 10, 0, 10, 0, 30, 50],
    [0, 0, 15, 55, 0, 30, 0, 20],
    [0, 0, 0, 0, 0, 50, 20, 0]
]

# ダイクストラ法を実行
distances, paths = dijkstra(adj_matrix, 0)  # 始点はv1 (インデックス0)


print('最短経路において1番目に通過する頂点:',paths[0][0]) # 終点v8への経路の1番目の頂点
print('最短経路において2番目に通過する頂点:',paths[7][1]) # 終点v8への経路の2番目の頂点
print('最短経路において3番目に通過する頂点:',paths[7][2]) # 終点v8への経路の3番目の頂点
print('最短経路において4番目に通過する頂点:',paths[7][3]) # 終点v8への経路の4番目の頂点
print('最短経路において5番目に通過する頂点:',paths[7][4]) # 終点v8への経路の5番目の頂点
print('最短経路において6番目に通過する頂点:',paths[7][5]) # 終点v8への経路の6番目の頂点
print('最短経路において7番目に通過する頂点:',paths[7][6]) # 終点v8への経路の7番目の頂点
print('d1:', distances[0])  # v1への最短距離
print('d2:', distances[1])  # v2への最短距離
print('d3:', distances[2])  # v3への最短距離
print('d4:', distances[3])  # v4への最短距離
print('d5:', distances[4])  # v5への最短距離
print('d6:', distances[5])  # v6への最短距離
print('d7:', distances[6])  # v7への最短距離
print('d8:', distances[7])  # v8への最短距離

実行結果

各頂点への最短距離と経路は以下のように求められます。

最短経路において1番目に通過する頂点: 1
最短経路において2番目に通過する頂点: 2
最短経路において3番目に通過する頂点: 5
最短経路において4番目に通過する頂点: 6
最短経路において5番目に通過する頂点: 3
最短経路において6番目に通過する頂点: 7
最短経路において7番目に通過する頂点: 8
d1: 0
d2: 10
d3: 50
d4: 20
d5: 30
d6: 40
d7: 65
d8: 85

まとめ

今回の実装で、ダイクストラ法を使った最短経路探索がどのように動作するかを理解できたと思います。優先度付きキューを活用することで効率的な探索が可能です。最後まで読んでくださり、ありがとうございました。もし改善点や質問があれば、ぜひコメントしてください！