首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
利用动态规划法求解每对节点之间的最短路径问题时,设有向图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
75
问题
利用动态规划法求解每对节点之间的最短路径问题时,设有向图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
软件设计师上午基础知识考试
软考中级
相关试题推荐
在配置命令frame-relaymapip192.168.1.1dlci101broadcast中,数字101的含义是(50)。
设某单位路由器建立了以下的路由表,若收到分组的目的IP地址为128.96.37.151,则转发的端口是(63),若收到分组的目的IP是128.96.35.151,则转发的端口是(64),若该路由器是该单位与Internet连接的路由器,则该单位分得的IP地
设某单位路由器建立了以下的路由表,若收到分组的目的IP地址为128.96.37.151,则转发的端口是(63),若收到分组的目的IP是128.96.35.151,则转发的端口是(64),若该路由器是该单位与Internet连接的路由器,则该单位分得的IP地
Networkscanbeinterconnectedbydifferentdevices.Inthephysicallayer,networkscanbeconnectedby(66)orHubs,whichjust
Networks can be interconnected by different devices in the physical layer networks can be connected by(1)or hubs. Which just mov
BorderGatewayProtocol(BGP)isinter-autonomoussystem(71)protoc01.BGPisbasedonaroutingmethodcalledpathvectorrouting
Traditionalnetworklayerpacketforwardingreliesontheinformationprovidedbynetworklayer(71)protocols,orstaticrouting,
Traditionalnetworklayerpacketforwardingreliesontheinformationprovidedbynetworklayer(71)protocols,orstaticrouting,
随机试题
阅读下面语段,回答问题:【端正好】碧云天,黄花地,西风紧,北雁南飞。晓来谁染霜林醉?总是离人泪。【滚绣球】恨相见得迟,怨归去得疾。柳丝长玉骢难系,恨不得倩疏林挂住斜晖。马儿迍迍的行,车儿快快的随,却告了相思回避,破题儿又早别离。听得道一
微丸剂的制备方法常用如下哪种方法
下列关于抽样误差的论述错误的是
广义的城市市政公用设施分为()两大类。
最常见的利率违规行为是()。
百里油菜花海所在地,且是北方小油菜发源地的是下列的()。
学生是人,是教育的对象,因而他们()。
Musiccomesinmanyforms;mostcountrieshaveastyleoftheirown【C1】______theturnofthecenturywhenjazzwasborn,America
A.printedB.somewhatC.sourceD.gatherE.competitionF.failsG.purposeH.influenceI.originJ.spreadK.innova
A、Naturaldisasters.B、Largechemicalfactories.C、Exhaustfromvehicles.D、Largeamountsofhouseholdgarbage.B男士说汽车尾气给环境造成很大的
最新回复
(
0
)