首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
利用动态规划法求解每对节点之间的最短路径问题时,设有向图G=<V,E>共有n个节点,节点编号1~n,设C是G的成本邻接矩阵,用Dk(i,j)表示从i到j并且不经过编号比k还大的节点的最短路径的长度(Dn(i,j)即为图G中节点i到j的最短路径长度),则求解
利用动态规划法求解每对节点之间的最短路径问题时,设有向图G=<V,E>共有n个节点,节点编号1~n,设C是G的成本邻接矩阵,用Dk(i,j)表示从i到j并且不经过编号比k还大的节点的最短路径的长度(Dn(i,j)即为图G中节点i到j的最短路径长度),则求解
admin
2009-05-15
55
问题
利用动态规划法求解每对节点之间的最短路径问题时,设有向图G=<V,E>共有n个节点,节点编号1~n,设C是G的成本邻接矩阵,用D
k
(i,j)表示从i到j并且不经过编号比k还大的节点的最短路径的长度(D
n
(i,j)即为图G中节点i到j的最短路径长度),则求解该问题的递推关系式为(28)。
选项
A、D
k
(i,j)=D
k
-1(i,j)+C(i,j)
B、D
k
(i,j)=min{D
k
-1(i,j),D
k
-1(i,j)+C(i,j)}
C、D
k
(i,j)=D
k
-1(i,k)+D
k
-1(k,j)
D、D
k
(i,j)=min{D
k
-1(i,j),D
k
-1(i,k)+D
k
-1(k,j)}
答案
D
解析
从“D
k
(i,j)表示从i到j并且不经过编号比k还大的节点的最短路径的长度”中,我们得到一个提示,在求i,j之间最短路径的时候,会考虑它经过哪些节点能缩短原来的路径。在 D
k
(i,j)=min{D
k
-1(i,j),D
k
-1(i,k)+D
k
-1(k,j)}中,D
k
(i,j)表示i到j不经过k的路径长度,而 Dk-1(I,k)+Dk-1(k,j)表示i到j经过k的路径长度,且min()函数用于找最小值,所以此式正确。
转载请注明原文地址:https://kaotiyun.com/show/hwxZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
当网络规模扩大时,适合采用执行最短路径优先算法的IGP协议,每个路由器向网络中的其他路由器发布(52),当路由信息改变后,路由器按照Dijkstra算法更新路由表。
在Linux系统smb.conf文件中,maxdisksize=0语句的作用是(40)。
在UNIX操作系统中,以下Shell程序实现当用户键入的命令参数的个数为1时,执行cat$1命令;若用户键入的命令参数的个数为2时,执行cat>>$2<$1命令。case(36)in1)cat$1;;2)cat
某请求分页存储管理系统中,容量为1MB的主存被划分为512块,其页表如表7-1所示。若给定一十进制逻辑地址为7058,其十进制物理地址是(11)。
TCP是一个面向连接的协议,它提供连接的功能是(31)的,采用(32)来实现可靠数据流的传送。为了提高效率,又引入了滑动窗口协议,协议规定重传(33)的分组,这种分组的数量最多可以(34),TCP协议采用滑动窗口协议解决了(35)。
WhiletheInternetisinherentlyinsecure,businessesstillneedtopreservetheprivacyofdataasittravelsoverthenetwork.
Networkscanbeinterconnectedbydifferentdevices.Inthephysicallayer,networkscanbeconnectedby(66)orHubs,whichjust
Packet-switching wireless networks are preferable(41)when transmissions are(42)because of the way charges are(43)per packet. Cir
Packet-switching wireless networks are preferable(41)when transmissions are(42)because of the way charges are(43)per packet. Cir
Routingprotocolsusedifferenttechniquesforassigning(1)toindividualnetwork.Further,eachroutingprotocolformsametricag
随机试题
在下列间隙感染中.哪一个最常引起颌骨边缘性骨髓炎
以下关于臀位的叙述,哪一项是正确的
被吊销《出口商品质量许可证》的企业,自吊销之日起满一年后方可重新提出申请。( )
下列股权投资基金投资者中,属于合格投资者的是()。
下列关于用人单位招用人员时的义务的表述,不正确的是()。
声音:旋律
两千多年前的《诗经》提出“夙夜在公”,西汉的贾谊提出“国而忘家,公而忘私”,《尚书》也有“以公灭私,民其允怀”的思想,宋代的范仲淹提出“先天下之忧而忧,后天下之乐而乐”,明代的顾炎武提出“天下兴亡,匹夫有责”,清代林则徐提出“苟利国家生死以,岂因祸福避趋之
Passage1
Foraboutthreecenturieswehavebeendoingscience,tryingscienceout,usingsciencefortheconstructionofwhatwecallmod
IntheUnitedStatesthefirstdaynurserywasopenedin1854.Nurserieswereestablishedinvariousareasduringthe【C1】______
最新回复
(
0
)