重み付きグラフの基礎と応用
重み付きグラフとは何か、辺の重みの格納方法、使用場面を学びます。Dijkstra、Prim、Kruskalを含む重み付きグラフの一般的なアルゴリズムを探索します。
Graph Types
詳細な説明
重み付きグラフ
重み付きグラフは各辺に数値（重み）を割り当てます。この重みは距離、コスト、時間、容量、その他の指標を表すことができます。
表現
重みは隣接構造の辺と一緒に格納されます：
隣接リスト:
A: [(B, 4), (C, 2)]
B: [(D, 3)]
C: [(B, 1), (D, 5)]
隣接行列:
A B C D
A 0 4 2 ∞
B ∞ 0 ∞ 3
C ∞ 1 0 5
D ∞ ∞ ∞ 0
重み付きグラフの一般的なアルゴリズム
- Dijkstraアルゴリズム — 単一ソースからの最短経路（非負の重み）
- Bellman-Ford — 負の重みを含む最短経路
- Primのアルゴリズム — 最小全域木（貪欲法、1つの木を成長）
- Kruskalのアルゴリズム — 最小全域木（辺をソート、Union-Find使用）
- Floyd-Warshall — 全ペア最短経路
特殊なケースとしての重みなしグラフ
重みなしグラフは、すべての辺の重みが1の重み付きグラフと見なせます。
ユースケース
重み付きグラフは接続にコストが伴う実世界のネットワークをモデル化します。道路ネットワークでは距離や移動時間、航空ルートプランナーではチケット価格やフライト時間、通信ネットワークでは帯域幅やレイテンシの重みを使用します。