我要招人

去企业版

首页 > 试题广场 >

后续得到的其余各最短路径的目标顶点依次是（）。

[单选题]

对如下有向带权图，若采用迪杰斯特拉（Dijkstra）算法求从源点 a 到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是 b，第二条最短路径的目标顶点是 c，后续得到的其余各最短路径的目标顶点依次是（）。

```
d， e， f
```
```
e， d， f
```
```
f， d， e
```
```
f， e， d
```

查看正确选项

chen尾巴

C.Dijkstra每次选取距离已得到点集最近的点加入集合。

解题思路：

a作为源点，a指向b和c，很明显，a到b距离短为2，加入b；
b指向d和c，b到c距离短为1，加入c；
c指向d和f，e，c到f距离短为1，加入f；
f无指向，加入d；
d指向额e，距离1，加入e；
算法：

a.初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边，则<u,v>正常有权值，若u不是v的出边邻接点，则<u,v>权值为∞。

b.从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。

c.以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。

d.重复步骤b和c直到所有顶点都包含在S中。

Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法算法描述：

a.从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。

b.对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。

发表于 2017-03-14 11:12:24 回复(7)

内存。

“D算法”找最短路径，ａ为源点，所以a找到b，b找到c,c找到f，紧接着由于f没有指向，所以回到c，由c指向d，d指向e.

发表于 2019-12-15 17:41:06 回复(0)

二咩

迪杰斯特拉（Dijkstra）算法：每次选取距离已得到点集最近的点加入集合，CF=1,BD=3,DE=1

发表于 2016-11-28 18:38:29 回复(0)

大大大🍍

以当前的顶点排列组合找到最小的。。。。。。

发表于 2022-10-24 18:05:29 回复(0)

天尊墨宇

选C

Dijkstra每次选取距离已得到点集最近的点加入集合。

解题思路：

a作为源点，a指向b和c，很明显，a到b距离短为2，加入b；

b指向d和c，b到c距离短为1，加入c；

c指向d和f，e，c到f距离短为1，加入f；

f无指向，加入d；

d指向额e，距离1，加入e；

算法：

a.初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边，则<u,v>正常有权值，若u不是v的出边邻接点，则<u,v>权值为∞。

b.从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。

c.以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。

d.重复步骤b和c直到所有顶点都包含在S中。

Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法算法描述：

a.从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。

b.对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。

编辑于 2020-07-13 19:32:25 回复(0)

提交观点

问题信息

图

上传者：城市里的养猫者

难度：

5条回答 275收藏 3550浏览

后续得到的其余各最短路径的目标顶点依次是（）。

问题信息

热门推荐

相关试题

后续得到的其余各最短路径的目标顶点依次是（ ）。

问题信息

热门推荐

相关试题

后续得到的其余各最短路径的目标顶点依次是（）。