题7
题目
Q:下列关于图的最短路径的相关叙述中, 正确的是 ( ).
A. 最短路径一定是简单路径
B. Dijkstra 算法不适合求有回路的带权图的最短路径
C. Dijkstra 算法不适合求任意两个顶点的最短路径
D. Floyd 算法求两个顶点的最短路径时,
分析
A:dj算法、bf算法，floyd算法，这三者在对于负权回路上的处理的区别在于，dj算法不能处理负权回路，bf算法可以处理负权回路，floyd算法可以处理负权回路。
dj算法只能求单源最短路径，bf算法可以求任意两点之间的最短路径，floyd算法也可以求任意两点之间的最短路径。
和题8对比起来看
解
A 正确, 见严蔚敏撰写的教材《数据结构》。Dijkstra 算法适合求解有回路的带权图的最短路径, 也可以求任意两个顶点的最短路径, 不适合求带负权值的最短路径问题。
在用 Floyd 算法求两个顶点的最短路径时,当最短路径发生更改时,
| Heap-Dijkstra | Floyd | ||
|---|---|---|---|
| 最短路类型 | 单源 | 单源 | 一全源 |
| 建图 | 邻接表 | 邻接表 | 邻接矩阵 |
| 算法 | 贪心，松弛 | 贪心，松弛 | 动态规划 (插点法 |
| 优化 | 优先队列 | 队列 | |
| 负边权 | 不能 | 能 | 能 |
| 判负环 | 不能 | 能 | 能 |
| 时间复杂度 | 0(mlogm) | ||
| 图的大小 | 大/中 | 中/小 n= 1 |
| 暴力 Dijkstra | Heap-Dijkstra | Bellman-Ford | ||
|---|---|---|---|---|
| 最短路类型 | 单源 | 单源 | 单源 | 单源 |
| 数据维护 | e[u], d[u], vis[u] 优先队列 距离优先 | e[u] , d[u] | ||
| 算法 | 贪心、松弛，出圈 | 贪心、松弛、入队、出队 | 所有边松弛 | 出队点的出边松弛 |
| 负边权 | 不能 | 不能 | 能 | 能 |
| 判负环 | 不能 | 不能 | 能 | 能 |
| 时间复杂度 | ||||
| 图的大小 | 中/小 n= 1 | 大/中 n= 1 | 中/小 n= 1 | 中/小 n= 1 |