グラフアルゴリズムとは？具体的なコードも交えて紹介！

この記事では

グラフアルゴリズムとは
グラフアルゴリズムの種類（主にダイクストラ法）
具体的なPythonコードの具体例

を紹介します。

全般的なアルゴリズムについてはこちらから！

グラフアルゴリズム
まとめ

グラフアルゴリズム

グラフアルゴリズムを簡単に言うと、「ネットワークや関係性を解析するための方法」です。

グラフアルゴリズムはグラフ理論に基づいてグラフ構造を操作します。グラフは、頂点（ノード）とそれらを結ぶ辺（エッジ）から構成されるデータ構造です。

グラフアルゴリズムは、ネットワーク分析、経路探索、クラスタリングなど、さまざまな分野で利用されます。

ダイクストラ法

概要: 簡単に言うと、「出発地点から目的地までの最も短い道のりを見つける方法」です。負の重みを持つ辺がない場合に使用されます。

ダイクストラ法を現実の具体例で言うと

「カーナビが最短ルートを見つける方法」

です。

カーナビゲーションシステムの例

あなたが車で移動するとき、カーナビゲーションシステムは出発地点から目的地までの最短経路を計算します。このとき、道路ネットワークをグラフとしてモデル化します。

各交差点や地点を頂点（ノード）として、道路を辺（エッジ）として表します。道路の長さや所要時間が辺の重みになります。

例えば、以下のような道路ネットワークがあるとします。

A地点からB地点までの距離は3km
A地点からC地点までの距離は6km
B地点からC地点までの距離は2km
B地点からD地点までの距離は7km
C地点からD地点までの距離は1km

このネットワークをグラフとして表すと、次のようになります：

A --3-- B --2-- C --1-- D
 \      /       /
  \    /       /
   \  /       /
    6       7

ダイクストラ法を使って、A地点からD地点までの最短経路を計算します。以下のように進めます。

出発地点Aからスタートし、Aの距離を0に設定します。
Aから直接行けるBとCの距離を更新します（Bは3km、Cは6km）。
次に、最も近い未訪問の地点Bを選びます。
Bから行けるCとDの距離を更新します（Cは3+2=5km、Dは3+7=10km）。
次に、最も近い未訪問の地点Cを選びます。
Cから行けるDの距離を更新します（Dは5+1=6km）。
最後に、D地点に到達します。

結果として、A地点からD地点までの最短経路はA -> B -> C -> Dで、合計距離は6kmです。

このように、ダイクストラ法はカーナビゲーションシステムで最短経路を計算するために使われています。

Pythonの具体例：鉄道の経路案内

以下に、鉄道の経路案内システムでのダイクストラ法の具体例を示します。

import heapq

def dijkstra(graph, start):
    queue = [(0, start)]
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    while queue:
        current_distance, current_vertex = heapq.heappop(queue)
        if current_distance > distances[current_vertex]:
            continue
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))
    return distances

# 鉄道ネットワークのグラフ
graph = {
    'A': {'B': 3, 'C': 6},
    'B': {'A': 3, 'C': 2, 'D': 7},
    'C': {'A': 6, 'B': 2, 'D': 1},
    'D': {'B': 7, 'C': 1}
}

# 出発駅 'A' から他の駅への最短経路を計算
print(dijkstra(graph, 'A'))

このコードは、駅 ‘A’ から他のすべての駅への最短経路を計算します。各駅間の移動時間を重みとして設定し、優先度付きキューを使用して効率的に最短経路を見つけます。

コードの詳細解説

ライブラリのインポート:
```
import heapq
```
- heapq は、優先度付きキュー（ヒープ）を使用するためのライブラリです。
ダイクストラ法の関数定義:
```
def dijkstra(graph, start):
    queue = [(0, start)]
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
```
- graph は、各頂点とその隣接頂点および重みを持つ辞書です。
- start は、探索を開始する頂点です。
- queue は、優先度付きキューで、初期状態では開始頂点と距離0を持ちます。
- distances は、各頂点への最短距離を記録する辞書で、初期状態では無限大に設定されます。開始頂点の距離は0に設定されます。
メインループ:
```
while queue:
    current_distance, current_vertex = heapq.heappop(queue)
    if current_distance > distances[current_vertex]:
        continue
    for neighbor, weight in graph[current_vertex].items():
        distance = current_distance + weight
        if distance < distances[neighbor]:
            distances[neighbor] = distance
            heapq.heappush(queue, (distance, neighbor))
```
- queue が空になるまでループを続けます。
- heapq.heappop(queue) で、現在の最短距離と頂点を取り出します。
- 取り出した距離が既知の最短距離よりも大きい場合はスキップします。
- 隣接する頂点とその重みを取得し、新しい距離を計算します。
- 新しい距離が既知の最短距離よりも小さい場合、最短距離を更新し、優先度付きキューに追加します。
結果の返却:
```
return distances
```
- 各頂点への最短距離を記録した辞書を返します。