カーナビゲーションのアルゴリズムには、ダイクストラ法など、グラフ理論に基づいた計算手法が利用されています。
物流の配送計画やSNSの人間関係分析、通信ネットワークの設計など、グラフ理論はさまざまな分野で活用されています。今回は、グラフ理論の基礎概念と代表的なアルゴリズムについて解説します。
本記事の内容
- グラフの基本概念と用語
- グラフの数学的表現（隣接行列・隣接リスト）
- ダイクストラ法による最短経路探索
- Pythonでの実装と可視化
グラフとは
グラフ $G$ は、頂点（ノード）の集合 $V$ と辺（エッジ）の集合 $E$ の組で定義されます。
$$ G = (V, E) $$
ここで、$V = \{v_1, v_2, \dots, v_n\}$ は頂点の集合、$E \subseteq V \times V$ は辺の集合です。
基本用語
- 無向グラフ: 辺に方向がないグラフ。$(v_i, v_j) = (v_j, v_i)$
- 有向グラフ: 辺に方向があるグラフ。$(v_i, v_j) \neq (v_j, v_i)$
- 重み付きグラフ: 各辺に重み（コスト）$w(e)$ が割り当てられたグラフ
- 次数: ある頂点に接続する辺の数。頂点 $v$ の次数を $\deg(v)$ と書く
- 経路: 頂点の列 $v_1, v_2, \dots, v_k$ で、連続する頂点間に辺が存在するもの
- 閉路（サイクル）: 始点と終点が同じ経路
握手の補題
無向グラフの全頂点の次数の総和は、辺の数の2倍に等しいという基本的な性質があります。
$$ \sum_{v \in V} \deg(v) = 2|E| $$
これは各辺が2つの頂点の次数にそれぞれ1ずつ寄与するためです。
グラフの表現方法
隣接行列
$n$ 個の頂点を持つグラフは、$n \times n$ の隣接行列 $\bm{A}$ で表現できます。
$$ A_{ij} = \begin{cases} w(v_i, v_j) & \text{if } (v_i, v_j) \in E \\ 0 & \text{otherwise} \end{cases} $$
無向グラフの場合、隣接行列は対称行列（$\bm{A} = \bm{A}^T$）になります。
隣接行列の利点は、2頂点間の辺の有無を $O(1)$ で判定できることです。一方、辺の数が少ない疎なグラフではメモリ効率が悪くなります。
隣接リスト
各頂点に対して、接続する頂点のリストを保持する方法です。疎なグラフではメモリ効率が良く、辺の列挙も高速です。
ダイクストラ法
ダイクストラ法は、重みが非負のグラフにおいて、始点から各頂点への最短経路を求めるアルゴリズムです。
アルゴリズム
- 始点 $s$ の距離を $d(s) = 0$、他の全頂点の距離を $d(v) = \infty$ に初期化
- 未確定の頂点のうち、距離 $d(v)$ が最小の頂点 $u$ を選択
- $u$ に隣接する各頂点 $v$ について、$d(u) + w(u,v) < d(v)$ なら $d(v) = d(u) + w(u,v)$ に更新
- $u$ を確定済みにする
- 全頂点が確定されるまで2-4を繰り返す
計算量
優先度付きキュー（ヒープ）を用いた実装では、計算量は次のようになります。
$$ O((|V| + |E|) \log |V|) $$
Pythonでの実装
import numpy as np
import heapq
import matplotlib.pyplot as plt
def dijkstra(graph, start):
"""ダイクストラ法による最短経路探索
Parameters
----------
graph : dict
隣接リスト {頂点: [(隣接頂点, 重み), ...]}
start : int
始点
Returns
-------
dist : dict
始点からの最短距離
prev : dict
最短経路上の前の頂点
"""
dist = {v: float('inf') for v in graph}
prev = {v: None for v in graph}
dist[start] = 0
# 優先度付きキュー: (距離, 頂点)
pq = [(0, start)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue
for v, w in graph[u]:
new_dist = dist[u] + w
if new_dist < dist[v]:
dist[v] = new_dist
prev[v] = u
heapq.heappush(pq, (new_dist, v))
return dist, prev
def get_shortest_path(prev, start, end):
"""最短経路を復元"""
path = []
v = end
while v is not None:
path.append(v)
v = prev[v]
return path[::-1]
# グラフの定義（隣接リスト）
graph = {
0: [(1, 4), (2, 2)],
1: [(0, 4), (2, 1), (3, 5)],
2: [(0, 2), (1, 1), (3, 8), (4, 10)],
3: [(1, 5), (2, 8), (4, 2), (5, 6)],
4: [(2, 10), (3, 2), (5, 3)],
5: [(3, 6), (4, 3)],
}
# 最短経路の計算
start, end = 0, 5
dist, prev = dijkstra(graph, start)
path = get_shortest_path(prev, start, end)
print(f"頂点{start}から各頂点への最短距離:")
for v, d in sorted(dist.items()):
print(f" 頂点{v}: {d}")
print(f"\n頂点{start}から頂点{end}への最短経路: {path}")
print(f"最短距離: {dist[end]}")
# グラフの可視化
fig, ax = plt.subplots(figsize=(8, 6))
# 頂点の座標
pos = {
0: (0, 1), 1: (1, 2), 2: (1, 0),
3: (2, 2), 4: (2, 0), 5: (3, 1),
}
# 辺の描画
for u in graph:
for v, w in graph[u]:
if u < v:
x = [pos[u][0], pos[v][0]]
y = [pos[u][1], pos[v][1]]
# 最短経路上の辺は赤色
if u in path and v in path and abs(path.index(u) - path.index(v)) == 1:
ax.plot(x, y, 'r-', linewidth=3, zorder=1)
else:
ax.plot(x, y, 'gray', linewidth=1, zorder=1)
mx, my = (x[0]+x[1])/2, (y[0]+y[1])/2
ax.text(mx, my + 0.1, str(w), ha='center', fontsize=10, color='blue')
# 頂点の描画
for v, (x, y) in pos.items():
color = 'red' if v in path else 'lightblue'
ax.scatter(x, y, s=500, c=color, edgecolors='black', zorder=2)
ax.text(x, y, str(v), ha='center', va='center', fontsize=14, fontweight='bold')
ax.set_title(f"Dijkstra: Shortest Path from {start} to {end} (cost={dist[end]})")
ax.set_xlim(-0.5, 3.5)
ax.set_ylim(-0.5, 2.5)
ax.set_aspect('equal')
ax.axis('off')
plt.tight_layout()
plt.show()
隣接行列による表現と行列演算
隣接行列を使うと、グラフの性質を線形代数の手法で分析できます。例えば、隣接行列 $\bm{A}$ の $k$ 乗 $\bm{A}^k$ の $(i,j)$ 成分は、頂点 $i$ から頂点 $j$ への長さ $k$ の経路の数を表します。
import numpy as np
# 隣接行列の定義
A = np.array([
[0, 1, 1, 0, 0, 0],
[1, 0, 1, 1, 0, 0],
[1, 1, 0, 1, 1, 0],
[0, 1, 1, 0, 1, 1],
[0, 0, 1, 1, 0, 1],
[0, 0, 0, 1, 1, 0],
])
# A^2: 長さ2の経路の数
A2 = np.linalg.matrix_power(A, 2)
print("A^2 (長さ2の経路数):")
print(A2)
# 各頂点の次数
degrees = np.sum(A, axis=1)
print(f"\n各頂点の次数: {degrees}")
print(f"次数の総和: {np.sum(degrees)} (= 2 * 辺の数 = {2 * np.sum(A) // 2})")
まとめ
本記事では、グラフ理論の基礎とダイクストラ法について解説しました。
- グラフは頂点と辺の組 $G = (V, E)$ で定義される基本的なデータ構造である
- グラフの表現方法として隣接行列と隣接リストがあり、用途に応じて使い分ける
- ダイクストラ法は非負重みグラフの最短経路を $O((|V|+|E|)\log|V|)$ で求められる
- 隣接行列の行列演算により、グラフの構造的性質を分析できる
次のステップとして、以下の記事も参考にしてください。