グラフ理論の基礎（最短経路）

Q: グラフ理論の基礎（最短経路）とは何ですか？

グラフ G=(V,E) とは、頂点の集合 V と、頂点同士を結ぶ辺の集合 E の組である。各辺 (u,v)\in E に非負の重み w(u,v) を割り当てたものを「重み付きグラフ」と呼ぶ。始点 s から頂点 v までの「最短距離」d(v) とは、s から v に至るすべての経路の中で、通過する辺の重みの総和が最小となる値である。

Q: グラフ理論の基礎（最短経路）は社会やプログラミングでどのように使われていますか？

カーナビ・ネットワークルーティングにおけるダイクストラ法: 道路網を「交差点＝頂点」「道路区間＝重み付き辺（距離や所要時間）」としてモデル化すると、カーナビの経路探索は最短経路問題そのものになる。同じアルゴリズムはインターネットのパケットルーティング（OSPFなどのルーティングプロトコル）にも使われている。

点と線のネットワークから「最も安く」目的地へ到達する経路を見つける

この単元の発見をシェア

3行要約（Key Takeaways / AIOサマリー）

1: グラフとは「頂点（ノード）」と、それらを結ぶ「辺（エッジ）」の集合で、辺には移動コストを表す「重み」を持たせることができる
2: ダイクストラ法は、始点から各頂点までの最短距離を「確定済みの中で最も近い頂点」から順に確定させていく貪欲アルゴリズムで、負の重みがなければ最短経路を必ず正しく求められる
3: カーナビの経路案内、Webサイトのリンク解析、通信ネットワークのルーティングなど、現実世界の「最短で行きたい」問題の多くはグラフの最短経路問題に帰着する

なぜこれを学ぶのか？ — 現実社会とテクノロジーでの価値

Purpose & Motivation

なぜ生まれたのか？

グラフとは「頂点（ノード）」と、それらを結ぶ「辺（エッジ）」の集合で、辺には移動コストを表す「重み」を持たせることができる

身につく武器・思考力

ダイクストラ法は、始点から各頂点までの最短距離を「確定済みの中で最も近い頂点」から順に確定させていく貪欲アルゴリズムで、負の重みがなければ最短経路を必ず正しく求められる

実社会・ITでの活躍現場

•カーナビ・ネットワークルーティングにおけるダイクストラ法
•ITシステム・アルゴリズム実装における論理設計
•データ分析やシミュレーションにおける数理モデリング

Layer 1 — 直感・シミュレーター

重み付きの小さなネットワーク図から、始点となるノードをクリックし、次に終点となるノードをクリックしてみよう。ダイクストラ法が実行され、最短経路が太い線でハイライトされるとともに、合計コスト（距離）が表示される。別の始点・終点の組み合わせを試して、経路がどう変わるか確認してみよう。

ノードをクリックして始点を選び、次に別のノードをクリックして終点を選ぶと、ダイクストラ法による最短経路がハイライトされます。

A から F への最短距離: 11

直感チェック！ミニクイズ

ダイクストラ法で最短経路を求める際、「未確定の頂点の中から選ぶべき次の頂点」はどのような頂点か？

Layer 2 — 定義・受験・証明

定義

グラフ $G=(V,E)$ とは、頂点の集合 $V$ と、頂点同士を結ぶ辺の集合 $E$ の組である。各辺 $(u,v)\in E$ に非負の重み $w(u,v)$ を割り当てたものを「重み付きグラフ」と呼ぶ。始点 $s$ から頂点 $v$ までの「最短距離」 $d(v)$ とは、 $s$ から $v$ に至るすべての経路の中で、通過する辺の重みの総和が最小となる値である。

公式・数理モデル

d(v) = \min_{P:\,s\to v} \sum_{(u,w)\in P} \text{weight}(u,w), \qquad d(v) \leftarrow \min\big(d(v),\, d(u) + w(u,v)\big)\ (緩和操作)

証明・導出

ダイクストラ法の正当性（貪欲選択の妥当性）：確定済み頂点集合を $S$ 、各頂点の暫定距離を $d(\cdot)$ とし、初期状態は $S=\{s\}$ 、 $d(s)=0$ 、他は $\infty$ とする。アルゴリズムは、 $V\setminus S$ の中で $d$ が最小の頂点 $u$ を選び $S$ に追加、 $u$ に隣接する頂点 $v$ について $d(v) \leftarrow \min(d(v), d(u)+w(u,v))$ と更新（緩和）することを繰り返す。数学的帰納法でこの手続きの正しさを示す： $|S|=1$ のときは自明に正しい。 $|S|=k$ まで正しいと仮定し、次に選ばれる頂点を $u$ とする。すべての辺の重みが非負であるため、 $s$ から $u$ へ向かう「 $S$ の外を経由する」経路のコストは、途中で $S$ を出た時点で既に $d(u)$ 以上である（非負性より経路長は単調非減少）。したがって $S$ の外を経由しても $d(u)$ より短くはならず、 $u$ が選ばれた時点の $d(u)$ は真の最短距離と一致する。この論法を繰り返し適用すれば、すべての頂点で正しい最短距離が確定することが示される（負の重みが存在すると、この単調性が崩れ証明は成立しない）。

押さえておきたいポイント

ダイクストラ法は「負の重みの辺が存在しない」という条件下でのみ正しく動作する貪欲アルゴリズムである
優先度付きキュー（二分ヒープ）を使うと、頂点数 $V$ 、辺数 $E$ に対し計算量 $O((V+E)\log V)$ で解ける
負の重みを許容する場合はベルマン・フォード法、全点対間の最短距離を求めたい場合はワーシャル・フロイド法を用いる
グラフの探索順序を工夫すること（幅優先探索・深さ優先探索）は最短経路以外にも連結成分の判定やサイクル検出など多くの応用を持つ

参照基準・学習指導要領との対応

本トピックの内容・数理モデルは、文部科学省学習指導要領（算数・数学・情報）および国際標準カリキュラムに準拠し、エンジニアリング現場の実装事例と照らし合わせてMath World Lab編集部により検証・作成されています。

Layer 3 — 工学応用・現場実装

カーナビ・ネットワークルーティングにおけるダイクストラ法

道路網を「交差点＝頂点」「道路区間＝重み付き辺（距離や所要時間）」としてモデル化すると、カーナビの経路探索は最短経路問題そのものになる。同じアルゴリズムはインターネットのパケットルーティング（OSPFなどのルーティングプロトコル）にも使われている。

1type Graph = Map<string, Map<string, number>>; // 頂点 -> (隣接頂点 -> 重み)
2
3// ダイクストラ法による単一始点最短経路
4function dijkstra(graph: Graph, start: string): Map<string, number> {
5  const dist = new Map<string, number>();
6  const visited = new Set<string>();
7
8  for (const node of graph.keys()) dist.set(node, Infinity);
9  dist.set(start, 0);
10
11  while (visited.size < graph.size) {
12    // 未確定の中で距離最小の頂点を選ぶ（貪欲選択）
13    let current: string | null = null;
14    let minDist = Infinity;
15    for (const [node, d] of dist) {
16      if (!visited.has(node) && d < minDist) {
17        minDist = d;
18        current = node;
19      }
20    }
21    if (current === null) break; // 到達不能な頂点のみ残っている
22    visited.add(current);
23
24    // 隣接頂点の距離を緩和（更新）
25    const neighbors = graph.get(current) ?? new Map();
26    for (const [next, weight] of neighbors) {
27      const candidate = dist.get(current)! + weight;
28      if (candidate < (dist.get(next) ?? Infinity)) {
29        dist.set(next, candidate);
30      }
31    }
32  }
33  return dist;
34}
35
36// 例: 4つの交差点からなる簡単な道路網
37const roadNetwork: Graph = new Map([
38  ["A", new Map([["B", 4], ["C", 1]])],
39  ["B", new Map([["D", 1]])],
40  ["C", new Map([["B", 2], ["D", 5]])],
41  ["D", new Map()],
42]);
43
44console.log(dijkstra(roadNetwork, "A"));
45// A->C->B->D という経路で D への最短距離は 4 になる