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

admin2010-01-23 42

问题利用动态规划方法求解每对节点之间的最短路径问题(all pairs shortest path problem)时，设有向图 G=＜V,E＞共有n个节点，节点编号1～n，设C是G的成本邻接矩阵，用D^k(I,j)即为图G中节点i到j并且不经过编号比k还大的节点的最短路径的长度(Dⁿ(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://jikaoti.com/ti/J9a7FFFM

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

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

软考中级

事件可以看成是信息从一个对象到另一个对象的单向传送。因此要确定各事件的发送对象和接收对象。______　用来表示事件、事件的接收对象和发送对象。

应用程序可以通过执行对象的操作来改变对象的属性值，但它必须通过　______　的传递。

Internet是全球最大的、开放的、由众多网络互联而形成的计算机网络，狭义Internet是指由上述提到网络中采用IP协议的网络互联而成的，广义Internet是指狭义Internet加上所有(92)的网络。Internet体系结构具有良好扩充性的主要原

ISO为传输层定义了4种类型的服务原语，由传输服务用户产生的原语是(99)。

SNA(系统网络结构)：它是IBM公司1970年开发的大型，复杂，多功能网络结构，与SNA网的体系结构中的端用户相对应的是OSI的(22)层次。

某项目主要由A～I任务构成，其计划图(如下图所示)展示了各任务之间的前后关系以及每个任务的工期(单位：天)，该项目的关键路径是()。在不延误项目总工期的情况下，任务A最多可以推迟开始的时间是()天。

以下哪种疾病可能会导致CAl25升高

女性，45岁，诊断为巨大结节性甲状腺肿，在颈丛麻醉下行一侧甲状腺全切，另一侧甲状腺大部切除术，术后第2天突然发生窒息，面肌和手足持续性痉挛。进一步的检查是

中医诊断为方宜首选

A、麻疹疫苗B、乙型脑炎疫苗C、脊髓灰质炎疫苗D、百、白、破混合制剂E、乙肝疫苗2个月小儿应接种

计算斐波那契数列第n项的函数定义如下：intfib(intn){if(n==0)return1;elseif(n==1)return2;e

WhatisMartin’soccupation?

SupposingyouareProfessorZhangofauniversity,writealetterinvitingProfessorWangtogivealecturetothestudentsand

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

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

软考中级

事件可以看成是信息从一个对象到另一个对象的单向传送。因此要确定各事件的发送对象和接收对象。______ 用来表示事件、事件的接收对象和发送对象。

应用程序可以通过执行对象的操作来改变对象的属性值，但它必须通过 ______ 的传递。

Internet是全球最大的、开放的、由众多网络互联而形成的计算机网络，狭义Internet是指由上述提到网络中采用IP协议的网络互联而成的，广义Internet是指狭义Internet加上所有(92)的网络。Internet体系结构具有良好扩充性的主要原

ISO为传输层定义了4种类型的服务原语，由传输服务用户产生的原语是(99)。

SNA(系统网络结构)：它是IBM公司1970年开发的大型，复杂，多功能网络结构，与SNA网的体系结构中的端用户相对应的是OSI的(22)层次。

某项目主要由A～I任务构成，其计划图(如下图所示)展示了各任务之间的前后关系以及每个任务的工期(单位：天)，该项目的关键路径是()。在不延误项目总工期的情况下，任务A最多可以推迟开始的时间是()天。

以下哪种疾病可能会导致CAl25升高

女性，45岁，诊断为巨大结节性甲状腺肿，在颈丛麻醉下行一侧甲状腺全切，另一侧甲状腺大部切除术，术后第2天突然发生窒息，面肌和手足持续性痉挛。进一步的检查是

中医诊断为方宜首选

A、麻疹疫苗B、乙型脑炎疫苗C、脊髓灰质炎疫苗D、百、白、破混合制剂E、乙肝疫苗2个月小儿应接种

计算斐波那契数列第n项的函数定义如下：intfib(intn){if(n==0)return1;elseif(n==1)return2;e

WhatisMartin’soccupation?

SupposingyouareProfessorZhangofauniversity,writealetterinvitingProfessorWangtogivealecturetothestudentsand

事件可以看成是信息从一个对象到另一个对象的单向传送。因此要确定各事件的发送对象和接收对象。______　用来表示事件、事件的接收对象和发送对象。

应用程序可以通过执行对象的操作来改变对象的属性值，但它必须通过　______　的传递。