最后更新: 2025-01-22 09:28 查看: 86 次纠错评论(0) 课件开VIP

最短路

设 $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)

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：哈密顿有向图

下一篇：图论模型初步

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