什么是加权有向图，它们建模了什么问题？

Question

什么是加权有向图，它们建模了什么问题？

IT Interview Practice · Accepted Answer

在**有向**图 (digraph) 中，边具有**方向性** (`A → B` ≠ `B → A`)。在**加权**图中，每条边都有一个**数值成本**（距离、时间、容量）。将两者结合可以对具有单向关系且有成本的真实系统进行建模。

## 表示

```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.
```

## 建模的场景

| 领域 | 顶点 | 加权有向边 |
|---|---|---|
| 地图 / GPS | 交叉路口 | 单向道路 + 旅行时间 |
| 网络 | 路由器 | 链路 + 延迟/带宽 |
| 任务调度 | 任务 | 依赖关系 + 持续时间 |
| 金融 | 货币 | 汇率 |

## 关键算法

| 目标 | 算法 | 复杂度 |
|---|---|---|
| 最短路径（非负权重） | Dijkstra | O((V+E) log V) |
| 最短路径（负边） | Bellman-Ford | O(VE) |
| 依赖排序 | Topological sort | O(V+E) |
| 检测环 / 可达性 | DFS | O(V+E) |

## 为什么这很重要

方向性和权重是将抽象图转化为路由、调度和依赖问题的忠实模型的关键，这些问题驱动着真实应用。

算法的选择取决于这些属性——例如，负权重排除了 Dijkstra，需要使用 Bellman-Ford。

领域	顶点	加权有向边
地图 / GPS	交叉路口	单向道路 + 旅行时间
网络	路由器	链路 + 延迟/带宽
任务调度	任务	依赖关系 + 持续时间
金融	货币	汇率

目标	算法	复杂度
最短路径（非负权重）	Dijkstra	O((V+E) log V)
最短路径（负边）	Bellman-Ford	O(VE)
依赖排序	Topological sort	O(V+E)
检测环 / 可达性	DFS	O(V+E)

表示

相关问题

建模的场景

关键算法

为什么这很重要