重み付きグラフと有向グラフとは何か、またどのような問題をモデル化するのか？

Question

Accepted Answer

**有向**グラフ(digraph)では、辺は**方向**を持ちます(`A → B` ≠ `B → A`)。**重み付き**グラフでは、各辺が**数値コスト**(距離、時間、容量)を持ちます。両者を組み合わせると、関係が一方向であり、コストを持つ実際のシステムをモデル化できます。

## Representation

```text
Weighted directed graph:
  A --5--> B
  A --2--> C
  C --1--> B
Adjacency list with weights:
  A: [(B,5), (C,2)]
  B: []
  C: [(B,1)]
```

```python
graph = {
    'A': [('B', 5), ('C', 2)],   # directed, weighted edges
    'B': [],
    'C': [('B', 1)],
}
# Shortest A->B is A->C->B = 2 + 1 = 3, not the direct edge 5.
```

## What they model

| Domain | Vertices | Weighted directed edges |
|---|---|---|
| Maps / GPS | intersections | one-way roads + travel time |
| Networks | routers | links + latency/bandwidth |
| Task scheduling | tasks | dependencies + durations |
| Finance | currencies | exchange rates |

## Key algorithms

| Goal | Algorithm | Complexity |
|---|---|---|
| Shortest path (non-negative weights) | Dijkstra | O((V+E) log V) |
| Shortest path (negative edges) | Bellman-Ford | O(VE) |
| Ordering with dependencies | Topological sort | O(V+E) |
| Detect cycles / reachability | DFS | O(V+E) |

## なぜ重要なのか

方向と重みは、抽象的なグラフをルーティング、スケジューリング、依存関係の問題の忠実なモデルに変える要素です。これらは実際のアプリケーションを駆動しています。

アルゴリズムの選択はこれらのプロパティに依存します。たとえば、負の重みは Dijkstra を除外し、Bellman-Ford が必要になります。

Domain	Vertices	Weighted directed edges
Maps / GPS	intersections	one-way roads + travel time
Networks	routers	links + latency/bandwidth
Task scheduling	tasks	dependencies + durations
Finance	currencies	exchange rates

Goal	Algorithm	Complexity
Shortest path (non-negative weights)	Dijkstra	O((V+E) log V)
Shortest path (negative edges)	Bellman-Ford	O(VE)
Ordering with dependencies	Topological sort	O(V+E)
Detect cycles / reachability	DFS	O(V+E)