首页 > 大学本科

网友您好，请在下方输入框内输入要搜索的题目：

请输入或粘贴题目内容搜题

搜题

拍照、语音搜题，请扫码下载APP

题目内容（请给出正确答案）

[主观题]

在求最短路径的算法中，要求所有边上的权值都不能为负值的算法是(①)，虽然允许边上的权值为负值，但不允许在有向回路中出现负值的算法是(②).

在求最短路径的算法中，要求所有边上的权值都不能为负值的算法是（①)，虽然允许边上的权值为负值，但不允许在有向回路中出现负值的算法是（②).

A、Kruskal算法

B、Dijkstra算法

C、Floyd算法

D、Prim算法

答案

查看答案

发布时间：2021-07-20

更多“在求最短路径的算法中，要求所有边上的权值都不能为负值的算法是(①)，虽然允许边上的权值为负值，但不允许在有向回路中出现负值的算法是(②).”相关的问题

第1题

当各边上权值()时，可以使用BFS算法来解决单源最短路径问题。

当各边上权值（)时，可以使用BFS算法来解决单源最短路径问题。

A、都相等

B、都不相等

C、不一定都相等

D、都大于0

点击查看答案

第2题

在以下假设下，重写Djkstra算法：(1)用邻接表表示有向带权图G，其中每个边结点有3个域：邻接顶点v

在以下假设下，重写Djkstra算法：（1)用邻接表表示有向带权图G，其中每个边结点有3个域：邻接顶点v

在以下假设下，重写Djkstra算法：

(1)用邻接表表示有向带权图G，其中每个边结点有3个域：邻接顶点vertex，边上的权值length和边链表的链接指针link

(2)用集合T=V(G)-S代替S(已找到最短路径的顶点集合)，利用链表来表示集合T。

试比较新算法与原来的算法，计算时间是快了还是慢了，给出定量的比较。

点击查看答案

第3题

若用邻接表表示图G，试重写BellmanFord算法。在邻接表的边结点中增加一个记录边上的权值的域len

gth。并以图8-27为例，验证新算法的正确性。

点击查看答案

第4题

如图所示为一个有向网图及其带权邻接矩阵，要求对有向图采用Dijkstra算法，求从V0 到其余各顶点

的最短路径。

点击查看答案

第5题

AOE网络必须是(①)，AOE网络中某边上的权值应是(②)，权值为零的边表示(③).

AOE网络必须是（①)，AOE网络中某边上的权值应是（②)，权值为零的边表示（③).

A、实数

B、正整数

C、正数

D、非负数

点击查看答案

第6题

给定一个连通图G，所有边都没有附加权值。编写一个算法，求从顶点v能到达的最短路径长度为k的所有顶点。(最短路径长度以路径上的边数计算，找到一条即可)

给定一个连通图G，所有边都没有附加权值。编写一个算法，求从顶点v能到达的最短路径长度为k的所有顶点。（最短路径长度以路径上的边数计算，找到一条即可)

点击查看答案

第7题

下面()算法可用于求无向图的所有连通分量。

下面（)算法可用于求无向图的所有连通分量。

A、广度优先遍历

B、拓扑排序

C、求最短路径

D、求关键路径

点击查看答案

第8题

对于n个顶点e条边的有向带权图，可以通过Dijkstra算法求出所有两个顶点之间的最短路径，此时的时间复杂度为()。

A.O(n)

B.O(n²)

C.O(n³)

D.O(n*e)

点击查看答案

第9题

用Kruskal算法求一个连通的带权图的最小代价生成树，在算法执行的某时刻，已选取的边集合TE={(1，2)，(2，3)，(3，5)}要选取下一条权值最小的边，不可能选取的边是()。

A.(3，6)

B.(1，3)

C.(1，4)

D.(2，4)

点击查看答案

第10题

判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用______。

A.求关键路径的方法

B.求最短路径的Dijkstra方法

C.深度优先遍历算法

D.广度优先遍历算法

点击查看答案

账号：尚未登录

登录没有账号？去注册

购买搜题卡

下载APP

关注公众号

TOP