Python WebAcademy

学習モード

グラフ理論とグラフアルゴリズム

Section 6 / 12

Dijkstraアルゴリズムの実装と理解

Dijkstraアルゴリズムは、非負の重みを持つグラフにおける最短経路を求めるための効率的なアルゴリズムです。ここでは、このアルゴリズムの理解を深めるために、基本的な概念とPythonによる実装を行います。

Dijkstraアルゴリズムの概要

Dijkstraアルゴリズムは、以下の手順で動作します。

  1. 初期化: 始点ノードの距離を0、他のノードの距離を無限大に設定します。また、未訪問のノードの集合を用意します。
  2. 訪問: 最も距離が短い未訪問ノードを選び、そのノードを訪問済みにします。
  3. 距離の更新: 訪問したノードから直接接続されているノードの距離を更新します。もし新たに計算された距離が既存の距離より短ければ、距離を更新します。
  4. 繰り返し: すべてのノードを訪問するまで、2と3のステップを繰り返します。

このアルゴリズムの計算量は、通常の配列を使用する場合はO(V^2)、優先度付きキューを使用する場合はO((V + E) log V)となります。

PythonによるDijkstraアルゴリズムの実装

以下に、Dijkstraアルゴリズムの実装例を示します。この例では、グラフは隣接リストで表現されます。

import heapq

def dijkstra(graph, start):
    # 最短距離を保持する辞書を初期化
    shortest_distances = {vertex: float('infinity') for vertex in graph}
    shortest_distances[start] = 0

    # 優先度付きキューを初期化
    priority_queue = [(0, start)]  # (距離, ノード)

    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)

        # 既に訪問済みのノードはスキップ
        if current_distance > shortest_distances[current_vertex]:
            continue

        # 隣接ノードの距離を更新
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight

            # より短い距離を見つけた場合、更新
            if distance < shortest_distances[neighbor]:
                shortest_distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return shortest_distances

コードの解説

  1. ライブラリのインポート: heapqを使って、優先度付きキューを実現します。
  2. 最短距離の初期化: 各ノードの最短距離を無限大で初期化し、スタートノードの距離を0に設定します。
  3. 優先度付きキューの初期化: スタートノードを距離0でキューに追加します。
  4. メインループ:
  5. キューから最小距離のノードを取り出します。
  6. そのノードから接続されているノードの距離を計算し、更新します。
  7. 更新があった場合は、新しい距離でキューにノードを追加します。
  8. 最短距離の返却: 最終的に、各ノードの最短距離を返します。

グラフの定義とアルゴリズムの実行

次に、上記の実装を使用して、具体的なグラフを定義し、Dijkstraアルゴリズムを実行してみましょう。

# グラフの定義
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

# Dijkstraアルゴリズムの実行
start_node = 'A'
shortest_paths = dijkstra(graph, start_node)

# 結果の表示
print(f"最短経路 (スタートノード: {start_node})")
for vertex, distance in shortest_paths.items():
    print(f"{vertex}: {distance}")

コードの解説

  • グラフの定義: 辞書を使って、各ノードとその隣接ノード、およびそれぞれの重みを定義しています。
  • アルゴリズムの実行: dijkstra関数を呼び出し、スタートノードを指定します。
  • 結果の表示: 各ノードに対する最短距離を表示します。

このサンプルを実行すると、ノードAから各ノードへの最短距離が計算され、出力されます。Dijkstraアルゴリズムを用いることで、効率的に最短経路問題を解決できることが分かります。

まとめ

Dijkstraアルゴリズムは、実際のアプリケーションや問題において非常に有用な手法です。グラフの構造やノード間の関係を理解することが、より効果的なアルゴリズムの実装につながります。今回の実装を通じて、Dijkstraアルゴリズムの基礎を学び、実際に動作させることで、その理解を深めていただければと思います。

前に戻る