首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
利用动态规划方法求解每对节点之间的最短路径问题(all pairs shortest path problem)时,设有向图 G=<V,E>共有n个节点,节点编号1~n,设C是G的成本邻接矩阵,用Dk(I,j)即为图G中节点i到j并且不经过编号比k还大的节
利用动态规划方法求解每对节点之间的最短路径问题(all pairs shortest path problem)时,设有向图 G=<V,E>共有n个节点,节点编号1~n,设C是G的成本邻接矩阵,用Dk(I,j)即为图G中节点i到j并且不经过编号比k还大的节
admin
2010-01-23
80
问题
利用动态规划方法求解每对节点之间的最短路径问题(all pairs shortest path problem)时,设有向图 G=<V,E>共有n个节点,节点编号1~n,设C是G的成本邻接矩阵,用D
k
(I,j)即为图G中节点i到j并且不经过编号比k还大的节点的最短路径的长度(D
n
(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://kaotiyun.com/show/LvxZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
计算机网络和分布系统中互相通信的(303)间交换信息时必须遵守的规则的集合称之为网络协议。其中,(304)是数据和控制信息的结构或格式;(305)是用于协调和进行差错处理的控制信息;定时是对事件实现顺序的详细说明,而网络体系结构则是(306)。
在OSI网络参考模型中,对等实体之间传送的信息单位称为(134),它包括(135)两部分。上下邻层实体之间的接口称为服务访问点(SAP),网络层的服务访问点也称为(136),通常分为(137)两部分。
阅读以下说明,回答下面问题。【说明】A公司用一台Web服务器和一台应用服务器来管理销售信息。销售人员在办公室时通过PC机来访问应用服务器,若在公司以外,则通过具有数据显示功能的移动电话或PDA(Personal-DigitalAssist
以下技术中,(127)不属于中间件技术。
RSA是一种基于(43)原理的公钥加密算法。网络上广泛使用的PGP协议采用RSA和IDEA两种加密算法组成链式加密体系,这种方案的优点是(44)。POP还可以对电子邮件进行认证,认证机制是用MD5算法产生(45)位的报文摘要,发送方用自己的RSA私钥对
对一路信号进行频移键控(FSK)调制时,若载波频率为fc,调制后的信号频率分别为f1和f2(f1<f2),则三者的关系是(17)。当对多路信号进行调制时,调制后各信号的频谱(18)。信号到达接收端后通过(19)分离各路信号。WDM与FDM工作方式很相似,
I/O系统主要有三种方式来与主机交换数据,它们是(6)、(7)和(8)。其中(6)主要用软件方法来实现,CPU的效率低;(7)要有硬件和软件两部分来实现,它利用专门的电路向CPU中的控制器发出I/O服务请求,控制器则(9)转入执行相应的服务程序;(8)主要
对欲访问特定信息的发起者的身份或者对传送的报文完整性进行合法性审查或核实的行为称为(50)。在日常生活中,我们可以用手写签名来防止否认的发生。在计算机通信中,要解决这类问题,可采用的方法是(51)。关于客户/服务器应用模式,说法正确的是(52)。在理论上,
下面关于ARP木马的描述中,错误的是()。
下列关于Microsoft管理控制台(MMC)的说法中,错误的是()。
随机试题
Youwillseethisproduct______whereveryougo.
正常人卵磷脂小体
患者,男,42岁,皮肤斑疹较多,呈点滴状,基底鲜红色,表面覆有银白色鳞屑,瘙痒较甚,经医师诊断为血热风燥型白庀,宜选用的药物为()。
下列各项中,不符合客户开户实名制的是()。
被认为是中国现代童话现实主义精神开篇之作的是()。
基本归因错误,是指人们经常把他人的行为归因于人格或态度等内在特质上,而忽视他们所处情境的重要性。下列属于基本归因错误的是()。
简述隋唐时期私学的发展。
Ayoungconsultant’slifeistiring.A【C1】______weekstartsbeforedawnonMonday,witharushtotheairportanda【C2】______to
规定输入的字符串中只包含字母和*号。请编写函数fun,其功能是:使字符串中尾部的*号不多于n个,若多于n个,则删除多余的*号;若少于或等于n个,则不做任何操作,字符串中间和前面的*号不删除。例如,字符串中的内容为“****A*BC*DEF*G**
HowmuchdoestheTVcostnow?
最新回复
(
0
)