图论（四）

2024-07-09 16:19| 来源: 网络整理| 查看: 265

一、最短路

概念：从某个点 A 到另一个点B的最短距离（或路径）。从点 A 到 B 可能有多条路线，多种距离，求其中最短的距离和相应路径。

最短路径分类：

单源最短路：图中的一个点到其余各点的最短路径

多源最短路：图中任意两点的最短路径

框架图解：

二、朴素Dijkstra算法

算法思想（仅限于非负权重值）：从起始点开始，使用贪心的策略，通过加点的方法，每次遍历到起始点距离最近且未被访问过的邻接节点 t ，将 t 加入到集合 S 中，直到访问过所有节点。

通过 N 次循环确定 n 个点到起点的最短路距离

时间复杂度为 $O(n^{2})$

1.在没有确定最短路中的所有点（集合 S 以外）找出距离起点最近的点 t

2.对 t 进行标记，加入到集合中

3.用 t 更新其他点的最短路距离

集合 S ：已经确定最短路的点（被访问过的点）

定义数组 dis：从起始点到某点 ( 3 号节点 ) 的最短距离（ dis[3] ）

定义二维数组add：

$add[u][v]$ 表示从节点 u 到节点 v 的距离（区分单向与双向，双向则 $add[v][u]=add[u][v]$ ）

初始化： $dis[1]=0 \, \, \, \, \, \, \, \, \, dis[x]=+\bowtie \, \, \, \, \, \, \, \, \, 2\leq x\leq n$ （以节点 1 为起始点）

若节点 u 与节点 v 之间没有路径，初始化为 $add[u][v]=+\Join$

核心代码：

for(int i=1;idis[u]+w) { dis[v]=dis[u]+w; q.push(make_pair(-dis[v],v)); // 将路径以负数保存，优先队列默认大根堆 } } } }

关于dijkstra算法的正确性证明，参考博文：

Dijkstra贪心算法的准确性证明_为什么这种方法求下来的路径一定是最短?试分析一下它的正确性-CSDN博客

四、dijkstra算法不能用于有负权边的图

通过上述dijkstra思想可以得出，每次松弛操作就是通过当前离起始点最近的点来更新其他点的距离，下面举例说明。

当此时通过节点 4 更新其他节点， dijkstra 思想已经确定 dis [ 4 ] 为起始点到节点 4 的最短路，显然错误。

【本文地址】

公司简介

联系我们