日期: 2024-04-06 18:31 查看: 7 次编辑导出本文

最短路径问题

## 最短路径

定义 16 给图的边 $\left(v_i, v_j\right)$ 或 $<v_i, v_j>$ 赋予一个实数 $w_{i j}$, 称 $w_{i j}$ 为该边的权, 每条边附加有权的图称为带权图或赋权图。一条通路的权是指这条通路上各边的权之和。

最短路径问题, 是寻找从 $u$ 到 $v(u \neq v)$ 的具有最小权的通路, 实际上它一定是路径。现已有若干求最短路径的算法。Dijkstra 于 1959 年提出的标号法是公认的好算法, 能求出图的某个结点到其他任一结点的最短路径。首先给 $n$ 阶带权图的每个结点记一个数, 称为标号。标号有两种: 临时标号 ( $T$ 标号) 和固定标号 ( $P$ 标号)。结点 $T$ 标号表示从始点到终点的最短通路的权的上界; $P$ 标号表示从始点到该结点的最短通路的权。算法的每一步把某个结点的 $T$ 标号改变为 $P$ 标号, 并改变其他结点的 $T$ 标号。一旦终点得到 $P$ 标号, 算法就结束。若要求得从始点到其他任一结点的最短路径, 则最多经 $n-1$ 步算法停止, 该算法的具体步骤如下。

#### Dijkstra 算法
第 1 步 给始点 $v_1$ 标上 $P$ 标号 $d\left(v_1\right)=\infty$, 给其他结点标上 $T$ 标号 $d\left(v_j\right)=w_{1 j}, 2 \leq j \leq n$ (设 $w_{i j}$ 是连接结点 $v_i$ 和 $v_j$ 的边的权, 若 $v_i$ 和 $v_j$ 没有边相连, 则令 $w_{i j}=\infty$ 。利用计算机计算时, 可根据具体问题的要求, 取一个足够大的数代替 $\infty$ )。

第 2 步 在所有的 $T$ 标号中取最小者, 设结点 $v_k$ 的 $T$ 标号 $d\left(v_k\right)$ 最小, 则将 $v_k$ 的 $T$ 标号改为 $P$ 标号, 并重新计算具有 $T$ 标号的其他各个结点 $v_j$ 的 $T$ 标号:
新的 $d\left(v_j\right)=\min \left\{\right.$ 旧有的 $\left.d\left(v_j\right), d\left(v_k\right)+w_{k j}\right\} 。$

第 3 步 若终点已具有 $P$ 标号, 则此标号即为所求最短路径的权, 算法停止; 否则转至第 2 步。

若要求始点到其他每一结点的最短路径, 则第 3 步修改为所有结点都已具有 $P$ 标号时算法停止。

有向图的最短路径问题的处理方法与此相同。若带权图的权是代表某种效益、利润等等, 则要求的不是 “最短” 路径而是 “最长” 路径, 这时只要将权改变正负标号, 原来的问题就转化为最短路径问题。Dijkstra 算法只能找出图中某个结点到任一其他结点的最短路径, 如果要用该算法找出图中任意两个结点之间的最短路径, 则算法要执行 $n$ 次。下面介绍 Warshall 给出并经 Floyed 改进的算法, 该算法能方便地求出图中任两结点之间的最短路径。

#### Warshall 算法
第 1 步 令 $W^{(0)}=W=\left[w_{i j}\right]=\left[w_{i j}^{(0)}\right]$
第 2 步从 $W^{(0)}$ 出发, 依次构造 $n$ 阶矩阵 $W^{(1)}, W^{(2)}, \Lambda, W^{(n)}$ 。各个 $W^{(k)}=\left[w_{i j}^{(k)}\right]$ 的定义为: $w_{i j}^{(k)}=\min \left\{w_{i j}^{(k-1)}, w_{i k}^{(k-1)}+w_{k j}^{(k-1)}\right\}, w_{i j}^{(k)}$ 是从 $v_i$ 到 $v_j$ 中间结点仅属于 $\left\{v_1, v_2, \Lambda, v_k\right\}$ 的通路中权最小的通路之权。

最后得到的 $W^{(n)}$ 的元素 $w_{i j}^{(n)}$ 就是结点 $v_i$ 到 $v_j$ 的最短路径的权。

上一篇：图的矩阵表示

下一篇：欧拉图与哈密尔顿图

本文对您是否有用？有用 (0) 无用 (0) 赞助我们

0 篇笔记写笔记

更多笔记