试题-(1). 求从指定源点到其余各顶点的迪杰斯特拉（Dijkstra）最短路径算法中弧上权不能为负的原因是在实际应用中无意义；

题目

(1). 求从指定源点到其余各顶点的迪杰斯特拉（Dijkstra）最短路径算法中弧上权不能为负的原因是在实际应用中无意义；

(2). 利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n³ ) ；（图用邻接矩阵表示）

(3). Floyd 求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。

上面不正确的是（）。

A.(1),(2),(3)

B.(1)

C.(1),(2)

D.(2),(3)

上一题 下一题

解答

正确答案是 B

Floyd 可以有负权边是因为它依靠的动态规划，比如a-b权值为1,而a-c权值2,c-b权值为-3，那么根据算法a-b最短路径为-1.Dij算法不能有负权边的原因是它依靠贪心算法，a-b最短路径就为1,实际上是-1

Floyd 不能有负权回路，这个容易理解，a-b，b-c，c-a权值分别为1，-2，-3，那么一直这样回路下去a-b-c-a会一直小，显然算法要在这儿停下，不然就没最短路径这一说。

所以1错，3对。

2的说法用dijkstra算法求两点间，并且是邻接矩阵存储时的时间复杂度是n平方级别的，n个点两两之间的是n立方级别的，是对的。

C 6条回复评论

墨色槐

学习学习学习

发表于 2023-01-07 21:00:00

0 0

琼华

喜欢这个老师的课

发表于 2022-12-21 22:00:00

0 0

浅色回忆

3是对的吗？我怎么感觉有负权回路也可以，举不出例子出来......

发表于 2018-10-13 15:27:37

0 0

子不语

Dijkstra采用了贪心的思想，每次都查找与该点距离最近的点，也因为这样，它不能用来解决存在负权边的图

利用 Dijkstra 求每一对不同顶点之间的最短路径的算法时间是 O(n2 ) （图用邻接矩阵表示）

发表于 2018-10-13 15:27:27

0 0

途安米

（2）是说每一对，在O(n2)的情况下再以每个顶点为起点进行Dijkstra算法，所以整个下来就是O(n3)

发表于 2018-10-13 15:27:15

0 0

碎梦不是梦碎

来记录一下，这道题真的很考察基础了吧。

(1)迪杰斯特拉（Dijkstra）最短路径算法中将所有的顶点分为两部分：已经确定的最短路程的顶点集合 P 和不能确定的最短路径的顶点集合 Q，每一次遍历都能最少确定一个顶点，也就是说每一次遍历至少有一个顶点进入集合P。归入P集合的节点的最短路径及其长度不再变更，如果边上的权值允许为负值，那么有可能出现当与P内某点（记为a）以负边相连的点（记为b）确定其最短路径时，它的最短路径长度加上这条负边的权值结果小于a原先确定的最短路径长度,而此时a在Dijkstra算法下是无法更新的，由此便可能得不到正确的结果.。

(2)求的是一对顶点，时间复杂度跟Floyd算法一样都是O(n^3)，如果求得是一个顶点到其他顶点的最短路径，时间复杂度才为O(n^2)。

(3)功夫再深点再回来补充。

发表于 2018-10-13 15:27:08

0 0

问题信息

分类：数据结构 - 最短路径

难度:

最新校招难题刷题，快来进刷题群吧