当前位置：首页 > news >正文

有向网是一种带权的有向图，其中每条边都有一个非负的权值表示从一个顶点到另一个顶点的代价或距离

news 2026/5/11 20:41:43

有向网是一种带权的有向图，其中每条边都有一个非负的权值表示从一个顶点到另一个顶点的代价或距离。图 3-42 (a) 描述了这样的一个有向网，包含顶点 $ v_0 \sim v_5 $，并通过边上的数值标明了各边的权重。其对应的邻接矩阵（图 3-42 (b)）用二维数组形式表示该图：若存在从顶点 $ v_i $ 到 $ v_j $ 的边，则矩阵元素 $ A[i][j] $ 存储该边的权值；若无直接连接，则记为 $ \infty $，表示不可达。

迪杰斯特拉算法（Dijkstra’s Algorithm）用于解决单源最短路径问题，即从指定源点（此处为 $ v_0 $）出发，计算到图中其余所有顶点的最短路径。该算法适用于边权非负的有向图或无向图。

算法核心思想如下：

维护两个集合：
- $ S $：已确定最短路径的顶点集合；
- $ T $：尚未确定最短路径的顶点集合。
初始化时，$ S $ 只包含源点 $ v_0 $，其他顶点均在 $ T $ 中。
每次从 $ T $ 中选择距离源点最近的顶点 $ u $，将其加入 $ S $，并以 $ u $ 为中间点更新 $ T $ 中所有与之相邻顶点的当前最短距离（松弛操作）。
重复此过程，直到所有顶点都被加入 $ S $ 或无法再更新。

根据表 3-1 所示的过程和结果：

终点	最短路径	路径长度
$ v_1 $	无路径	$ \infty $
$ v_2 $	$ v_0 \to v_3 \to v_4 \to v_2 $	60
$ v_3 $	$ v_0 \to v_3 $	30
$ v_4 $	$ v_0 \to v_3 \to v_4 $	50
$ v_5 $	$ v_0 \to v_5 $	10

可以得出以下结论：

$ v_0 \to v_5 $ 直接相连，权值为 10，是最短路径；
$ v_0 \to v_3 $ 权值为 30，是通往多个后续顶点的关键中转点；
$ v_0 \to v_4 $ 需经由 $ v_3 $，路径为 $ v_0 \to v_3 \to v_4 $，总长 50；
$ v_0 \to v_2 $ 的最短路径经过 $ v_3 $ 和 $ v_4 $，累计长度为 60；
$ v_1 $ 与源点之间没有可达路径，因此距离为 $ \infty $。

这说明迪杰斯特拉算法不仅找出最短路径本身，还能识别出哪些目标是不可达的。
迪杰斯特拉算法不能处理带有负权边的图，其根本原因在于该算法采用贪心策略，一旦某个顶点被选入集合 $ S $（即认为已找到从源点到该顶点的最短路径），就不再更新它的最短距离。然而，在存在负权边的情况下，这种“一旦确定不再更改”的假设可能不成立。

详细解释如下：

贪心选择的局限性
迪杰斯特拉算法在每一步都选择当前距离源点最近的未确定顶点 $ u $ 加入集合 $ S $，并认为此时的距离就是最终的最短距离。但在有负权边时，可能存在一条经过更多边但总权值更小（甚至为负）的路径，这条路径会在后续才被发现，从而导致之前“已确定”的距离实际上是错误的。
反例说明
考虑以下简单有向图：
- 顶点：$ v_0, v_1, v_2 $
- 边与权值：
  - $ v_0 \to v_1 $，权值 3
  - $ v_0 \to v_2 $，权值 4
  - $ v_2 \to v_1 $，权值 -2
若使用迪杰斯特拉算法从 $ v_0 $ 出发：
- 初始：$ dist[v_1] = 3, dist[v_2] = 4 $
- 先将 $ v_1 $（距离最小）加入 $ S $，标记其最短距离为 3。
- 然后处理 $ v_2 $，发现 $ v_2 \to v_1 $ 的边，但此时 $ v_1 $ 已经在 $ S $ 中，不再更新。
实际上，路径 $ v_0 \to v_2 \to v_1 $ 的长度是 $ 4 + (-2) = 2 < 3 $，应更优，但由于贪心策略过早地固定了 $ v_1 $ 的距离，导致结果错误。
负权环问题加剧影响
如果图中存在负权回路（负环），则最短路径可能不存在（可以无限绕环降低总权值）。虽然迪杰斯特拉无法检测负环，也无法正确处理一般负权边，而像 Bellman-Ford 或 SPFA 这类算法则能处理这类情况。