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

admin2009-05-15 68

问题利用动态规划法求解每对节点之间的最短路径问题时，设有向图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)

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

软考中级

信源用户A通过卫星链路向用户B传送帧长为2Kb的数据，链路传播延迟为80ms。若采用后退N帧ARQ协议通信，发送窗口为8，且要求最大链路利用率达到0.95，则数据传输速率至少为(25)kb/s，

某请求分页存储管理系统中，容量为1MB的主存被划分为512块，其页表如表7-1所示。若给定一十进制逻辑地址为7058，其十进制物理地址是(11)。

文件系统采用多重索引结构搜索文件内容。设块长为512字节，每个块号长3字节，如果不考虑逻辑块号在物理块中所占的位置，那么两级索引时可寻址的文件最大长度为(4)。

设某单位路由器建立了以下的路由表，若收到分组的目的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

Traditionalnetworklayerpacketforwardingreliesontheinformationprovidedbynetworklayer(71)protocols，orstaticrouting，

在Linux操作系统中，可以通过iptables命令来配置内核中集成的防火墙。若在配置脚本中添加iptables命令：＄IPT-tnat-APREROUTING-ptop-s0/0-d61.129.3.88--dport80-jDN

哮病中痰哮治法为：表寒里饮之寒哮治宜：

慢性肾小球肾炎晚期的主要病理变化是

下列有关新斯的明的描述，哪一项是错误的

甲享有一项发明，甲与乙签订了该专利申请权的转让合同。合同签订后，乙支付了部分转让费。因乙最后未能取得专利权而发生纠纷。下列表述正确的有：

公路水运检测机构及评价周期内持证的检测人员的信用评价基准分为100分。()

我国《上市公司收购管理办法》规定，通过证券交易所的证券交易，收购人持有一个上市公司的股份达到该公司已发行股份的()时，继续增持股份的，应当采取要约方式进行。

根据票据法律制度的规定，下列各项中，属于票据行为的有()。

Ifsabravemanwhoclaims"geniusinsciencehasbecomeextinct".Butthat’sexactlywhatpsychologistDeanKeithSimontondecl

InnocountryotherthanEngland,ithasbeensaid,onecanexperiencefourseasonsinasingleday!Daymaybreakasanicespr

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

软考中级

信源用户A通过卫星链路向用户B传送帧长为2Kb的数据，链路传播延迟为80ms。若采用后退N帧ARQ协议通信，发送窗口为8，且要求最大链路利用率达到0.95，则数据传输速率至少为(25)kb/s，

某请求分页存储管理系统中，容量为1MB的主存被划分为512块，其页表如表7-1所示。若给定一十进制逻辑地址为7058，其十进制物理地址是(11)。

文件系统采用多重索引结构搜索文件内容。设块长为512字节，每个块号长3字节，如果不考虑逻辑块号在物理块中所占的位置，那么两级索引时可寻址的文件最大长度为(4)。

设某单位路由器建立了以下的路由表，若收到分组的目的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

Traditionalnetworklayerpacketforwardingreliesontheinformationprovidedbynetworklayer(71)protocols，orstaticrouting，

在Linux操作系统中，可以通过iptables命令来配置内核中集成的防火墙。若在配置脚本中添加iptables命令：＄IPT-tnat-APREROUTING-ptop-s0/0-d61.129.3.88--dport80-jDN

哮病中痰哮治法为：表寒里饮之寒哮治宜：

慢性肾小球肾炎晚期的主要病理变化是

下列有关新斯的明的描述，哪一项是错误的

甲享有一项发明，甲与乙签订了该专利申请权的转让合同。合同签订后，乙支付了部分转让费。因乙最后未能取得专利权而发生纠纷。下列表述正确的有：

公路水运检测机构及评价周期内持证的检测人员的信用评价基准分为100分。()

我国《上市公司收购管理办法》规定，通过证券交易所的证券交易，收购人持有一个上市公司的股份达到该公司已发行股份的()时，继续增持股份的，应当采取要约方式进行。

根据票据法律制度的规定，下列各项中，属于票据行为的有()。

Ifsabravemanwhoclaims"geniusinsciencehasbecomeextinct".Butthat’sexactlywhatpsychologistDeanKeithSimontondecl

InnocountryotherthanEngland,ithasbeensaid,onecanexperiencefourseasonsinasingleday!Daymaybreakasanicespr

Networks　can　be　interconnected　by　different　devices　in　the　physical　layer　networks　can　be　connected　by(1)or　hubs.　Which　just　mov