最后更新: 2025-01-22 09:28 查看: 24 次反馈刷题

最短路

设 $G=(V, E, \omega)$ 是一个带权连通简单图，$\omega$ 是从 $E$ 到正实数集的函数。边 $\{i, j\}$ 带的权记为 $\omega(i, j)$ ，当无边 $\{i, j\}$ 时，令 $\omega(i, j)=+\infty$ 。

定义8．29（长度／距离）在 $G=(V, E, \omega)$ 中，路 $p$ 上所有边带的权之和称为路 $p$ 的长度，记为 $\omega(p)$ 。顶点 $u$ 和 $v$ 之间的最短路长度称为 $u$ 和 $v$ 之间的距离，记为 $d(u, v)$ ，即：

$$
d(u, v)= \begin{cases}0 & u=v \\ \min _p\{\omega(p) \mid u \text { 和 } v \text { 之间的路 } p\} & u \text { 与 } v \text { 连通 }\end{cases}
$$

本节主要讨论的问题是在带权连通简单图 $G=(V, E, \omega)$ 中找一条从顶点 $v_1$ 到另一个顶点之间的最短路及其距离。

下面介绍得克特拉（E．W．Dijkstra）在 1959 年提出的一个算法，这一算法称为Dijkstra算法，至今仍是解这个问题的最好算法，对于带权连通简单图，它可以逐点求出顶点 $v_1$ 到其他各点的最短路及其距离。对于没有回路的带权连通简单有向图也可用Dijkstra算法。

设图 $G=(V, E, \omega), V=\left\{v_1, v_2, \cdots, v_n\right\}, \omega>0$ ，若 $\left\{v_i, v_j\right\}$ 不是 $G$ 中的边，则 $w\left(v_i, v_j\right)=+\infty$ 。令 $S$

表示已求出最短路径的顶点集合，$v_1 \in S, T=V-S 。$ Dijkstra算法基于最短路的任一段子路也是最短路这一思想，构造顶点子集 $S$ ，使得从 $v_1$ 到 $S$ 中任何顶点的最短路上的顶点都在 $S$ 中。 Dijkstra算法过程如下。

$$
\begin{aligned}
& L\left(v_1\right)=0 ; \\
& \text { for }(i=2 ; i \leqslant n ; i++) L\left(v_i\right)=w\left(v_1, v_i\right) ; \\
& S=\left\{v_1\right\} ; T=\left\{v_2, \cdots, v_n\right\} ; \\
& \text { for }(k=2 ; k \leqslant n ; k++)
\end{aligned}
$$

\｛设 $u$ 是 $T$ 中 $L(u)$ 最小的一个顶点；

$$
S=S \cup\{u\} ; T=T-\{u\} ;
$$

for $T$ 中所有顶点 $v$
```
                L(v)=min}{L(v),L(u)+\omega(u,v)}
}
```

Dijkstra算法结束时，数组 $L$ 给出 $v_1$ 到其他顶点的距离。
定理8．25 若 $\min _{v \in T}\{L(v)\}=L\left(v^{\prime}\right)$ ，则从 $v_1$ 到 $v^{\prime}$ 的最短路长度（即距离）为 $L\left(v^{\prime}\right)$ 。
证明：假设从 $v_1$ 到 $v^{\prime}$ 存在一条路 $p$ ，它的长度小于 $L\left(v^{\prime}\right)$ ，则路 $p$ 必定经过 $T-\left\{v^{\prime}\right\}$ 中的其他顶点，沿着从 $v_1$ 到 $v^{\prime}$ 的路 $p$ 行走，首先遇到 $T-\left\{v^{\prime}\right\}$ 中的顶点 $v^{\prime \prime}$ ，在 $v_1$ 到 $v^{\prime \prime}$ 的这段路 $p$ 的子路上不包含 $T$ 中其他任何顶点，由此得出 $L\left(v^{\prime \prime}\right)<L\left(v^{\prime}\right)$ ，与假设矛盾。

定理8．26 证明 Dijkstra 算法中的步骤。
for $T$ 中所有顶点 $v$

$$
L(v)=\min \{L(v), L(u)+\omega(u, v)\}
$$

![图片](/uploads/2025-01/43505c.jpg)
  ![图片](/uploads/2025-01/3ea057.jpg)

刷题

做题，是检验是否掌握数学的唯一真理

上一篇：哈密顿有向图

下一篇：图论模型初步

本文对您是否有用？有用 (0) 无用 (0)