首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
利用动态规划方法求解每对结点之间的最短路径问题(a11 pairs shortest path problem)时,设有向图G=<V,E>共有n个结点,结点编号1~n,设C是G的成本邻接矩阵,用Dk(i,j)表示从i到j并且不经过编号比众还大的结点的最短路
利用动态规划方法求解每对结点之间的最短路径问题(a11 pairs shortest path problem)时,设有向图G=<V,E>共有n个结点,结点编号1~n,设C是G的成本邻接矩阵,用Dk(i,j)表示从i到j并且不经过编号比众还大的结点的最短路
admin
2021-01-13
40
问题
利用动态规划方法求解每对结点之间的最短路径问题(a11 pairs shortest path problem)时,设有向图G=<V,E>共有n个结点,结点编号1~n,设C是G的成本邻接矩阵,用D
k
(i,j)表示从i到j并且不经过编号比众还大的结点的最短路径的长度(D
n
(i,j即为图G中结点i到j的最短路径长度),则求解该问题的递推关系式为(56)。
选项
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
(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)。
转载请注明原文地址:https://kaotiyun.com/show/53CZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
阅读下列说明和图,回答问题1至问题4,将解答填入答题纸的对应栏内。【说明】某大型企业的数据中心为了集中管理、控制用户对数据的访问并支持大量的连接需求,欲构建数据管理中间件,其主要功能如下:(1)数据管理员可通过中间件进行用户管理、操作管理和权限管理。
阅读下列说明和图,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】Pay&Drive系统(开多少付多少)能够根据驾驶里程自动计算应付的费用。系统中存储了特定区域道路交通网的信息。道路交通网由若干个路段(RoadSeg
(2012年上半年下午试题二)阅读下列说明,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某医院拟开发一套住院病人信息管理系统,以方便对住院病人、医生、护士和手术等信息进行管理。【需求分析】(1)系统登记每
(2013年上半年下午试题二)阅读下列说明,回答问题1至问题3,将解答填入答题纸的对应栏内。【说明】某电视台拟开发一套信息管理系统,以方便对全台的员工、栏目、广告和演播厅等进行管理。【需求分析】(1)系统需要维护全台
在UML提供的图中,(31)用于描述系统与外部系统及用户之间的交互;(32)用于按时间顺序描述对象间的交互。
在常用的描述二叉排序树的存储结构中,关键字值最大的结点(48)。
某一确定有限自动机(DFA)的状态转换图如下图所示,该DFA接受的字符串集是(28),与之等价的正规式是(29)。
软件测试是软件质量保证的主要手段之一,测试的费用已超过(10)的30%以上。因此提高测试的有效性非常重要。“高产”的测试是指(11)。根据国家标准GB8566-88计算机软件开发规范的规定,软件的开发和维护分为8个阶段,其中单元测试是在(12)阶段完成的;
The most accurate and most boring way to(66)Java is that it is a new computer programming language developed by Sun Microsystems
ATM协议的(25)层将从其他网络接收到数据进行重组。
随机试题
Youhavealreadygrownup.It’stimeyou________howtobehaveproperly.
设函数z(x,y)由方程=0所确定,证明:=z—xy.
引起血尿的部位,初血尿病变部位在(1),终末血尿在(2),全程血尿在(3)。
口腔念珠茵病可分为
铸造支托凹制备时,其宽度应为前磨牙面颊舌径的()。
从中国传统法文化的角度,解释下面这段文字的真实含义。“本其事而原其志。志善而违于法者,免;志恶而合于法者,诛。”
Forthepastfiveyears,Dr.StephenPosthasbeenfundingresearchprojectsthattesthowaltruism(selflessness),compassion,
系统出现死锁的原因是
A、 B、 C、 C[A]是drum,[B]是horn,[C]是violin。
Readthetextbelowaboutabusinessletterwrittentothesolesupplier.Inmostofthelines(41-52)thereisoneextraword
最新回复
(
0
)