在用Dijkstra算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是(①).对于如

在用Dijkstra算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是（①).对于如

图8-42(a)所示的带权有向图，从顶点1到顶点5的最短路径为(②).

在用Dijkstra算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是（①).对于如

A、非零

B、非整

C、非负

D、非正

答案

查看答案

发布时间：2022-05-18

更多“在用Dijkstra算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是(①).对于如”相关的问题

第1题

在用Kruskal算法求解带权连通图的最小生成树时，通常采用一个(①)辅助结构，判断一条边的两个端

在用Kruskal算法求解带权连通图的最小生成树时，通常采用一个（①)辅助结构，判断一条边的两个端

点是否在同一个连通分量上，在该算法中选择权值最小的边的原则是该边不能在图中构成(②)，它主要适用于(③)。

A、稀疏

B、稠密

C、完全

D、不完全

点击查看答案

第2题

设有一个带权有向图G，编写一个算法，用深度优先搜索方法对该图中所有顶点.

点击查看答案

第3题

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

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

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

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

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

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

点击查看答案

第4题

考查某些边的权重不是正数的带权网络。试证明：a)对此类网络仍可以定义最小支撑树——此时，Prim算法是否依然可行？b)若不含负权重环路，则仍可以定义最短路径树——此时，Dijkstra算法是否依然可行？

点击查看答案

第5题

合成数（composite number)法，是消除图算法岐义性的一种通用方法。首先，在顶点的标识之间约定

合成数(composite number)法，是消除图算法岐义性的一种通用方法。首先，在顶点的标识之间约定某一次序。比如，顶点标识为整数或字符时，可直接以整数或字符为序;对于字符串等标识，不妨按字典序排列。于是，若边(v，u)权重为w，则对应的合成数取作向量：(w，min(v，u)，max(v，u))。如此，任何两条边总能明确地依照字典序比较出大小。

试在6.11.5节Prim算法和6.12.2节Dijkstra算法中引入这一方法，以消除其中的歧义性。

点击查看答案

第6题

用Dijkstra算法求图8.67中v₁到v₁₁的最短路径及其长度。