利用动态规划方法求解每对节点之间的最短路径问题(all pairs shortest path problem)时，设有向图 G=＜V,E＞共有n个节点，节点编号1～n，设C是G的成本邻接矩阵，用Dk(I,j)即为图G中节点i到j并且不经过编号比k还大的节

admin2010-01-23 63

问题利用动态规划方法求解每对节点之间的最短路径问题(all pairs shortest path problem)时，设有向图 G=＜V,E＞共有n个节点，节点编号1～n，设C是G的成本邻接矩阵，用D^k(I,j)即为图G中节点i到j并且不经过编号比k还大的节点的最短路径的长度(Dⁿ(i,j)即为图G中节点i到j的最短路径长度)，则求解该问题的递推关系式为(62)。

选项 A、D^k(I,j)=D^k-1(I,j)+C(I,j)
B、D^k(I,j)=D^k-1(I,k)+D^k-1(k,j)
C、D^k(I,j)=min{D^k-1(I,j),D^k-1(I,j)+C(I,j)}
D、D^k(I,j)=min{D^k-1(I,j),D^k-1(I,K)+D^k-1(k,j)}

答案D

解析设P^k(I,j)表示从i到j并且不经过编号比k还大的节点的最短路径，那么P^k(I,j)有以下两种可能：
①P^k(I,j)经过编号为k的节点，此时P^k(I,j)可以分为从i到k和从k到j的两段，易知P^k(I,j)的长度为D^k-1(I,k)+D^k-1(k,j)；
②P^k(I,j)不经过编号为k的节点，此时P^k(I,j)的长度为D^k-1(I,j)。
因此，求解该问题的递推关系式为：D^k(I,j)=min{D^k-1(I,j),D^k-1(I,k)+D^k-1(k,j)}。

转载请注明原文地址:https://jikaoti.com/ti/J9a7FFFM

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

利用动态规划方法求解每对节点之间的最短路径问题(all pairs shortest path problem)时，设有向图 G=＜V,E＞共有n个节点，节点编号1～n，设C是G的成本邻接矩阵，用Dk(I,j)即为图G中节点i到j并且不经过编号比k还大的节

软件设计师上午基础知识考试

软考中级

通常VLAN有静态和动态两种实现方式，这两种方式分别是如何实现的?各有什么特点?Switch1采用的是哪种实现方式?填充VLAN信息表(表2.3)。

在OSI网络参考模型中，对等实体之间传送的信息单位称为(134)，它包括(135)两部分。上下邻层实体之间的接口称为服务访问点(SAP)，网络层的服务访问点也称为(136)，通常分为(137)两部分。

请列举IEEE802.11b的两种工作模式。提高WLAN的安全性有哪些措施。

根据我国相关法律的规定，实用新型专利和外观设计专利的保护期为(20)年，单位软件产品的著作权保护期为(21)年。

以科学、技术和实践经验的综合成果为基础，对重复性事物和概念所做的统一规定，经有关方面协商一致，由一个公认机构或主管机构批准，以特定形式发布作为共同遵守的准则和依据，这是对(1)的描述。

PPP使用(38)协议。相对于OSI模型，它提供(39)服务。对于PPP，远程服务器可以为本地客户提供一个(40)IP地址。

网络配置如下图所示：其中某设备路由表信息如下：C192．168．1．0／24isdirectlyconnected，FastEthemet0／0R192．168．3．0／24[120／1]via192．168．65．2，00：00：

化工危险品的包装要严密、坚固，包装要符合有关()标准。

Zn与浓硫酸反应的主要产物是ZnSO4和No。()

唇、舌、耳、鼻及眼睑断裂伤，离体组织尚完好，应尽量将离体组织缝回原处，但一般不宜超过

A、气短或呼吸困难B、进行性加重的呼吸困难C、吸气性呼吸困难D、呼气性呼吸困难E、夜间阵发性呼吸困难慢性阻塞性肺疾病常见的表现是

A．头孢氨苄B．头孢克洛C．头孢呋辛D．硫酸头孢匹罗E．头孢曲松C-3位含有酸性较强的杂环，可通过血脑屏障，用于脑部感染治疗的药物是()。

将叶轮与电动机的转子直联成一体，浸没在被输送液体中的泵为()。

合同变更的定义()。

WISC-CR的IQ值在50～69之间者，约占智力迟滞总数的（）。

DVDrentalkiosks(售货亭)fromRedboxandBlockbusterseemtobepoppinguponeverycornerthesedays,buthome-videomarketanalys