扫码加入训练营

牢记核心词

学习得礼盒

41.(10分)带权图(权值非负,表示边连接的两顶点间的距离)的

2021-06-27 07:07:00来源:新东方在线

  【题目】

  41.(10分)带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法:

  ①设最短路径初始时仅包含初始顶点,令当前顶点u为初始顶点;

  ②选择离u最近且尚未在最短路径中的一个顶点v,加入到最短路径中,修改当前顶点u=v;

  ③重复步骤②,直到u是目标顶点时为止。

  请问上述方法能否求得最短路径?若该方法可行,请证明之;否则,请举例说明。

  【答案要点】

  该方法不一定能(或不能)求得最短路径。举例说明如下:

  图a

   图b

  图a中,设初始顶点为1,目标顶点为4,欲求从顶点1到顶点4之间的最短路径。显然, 这两点之间的最短路径长度为2。但利用给定方法求得的路径长度为3,因此这条路径并不是这两点之间的最短路径。

  图b中,设初始顶点为1,目标顶点为3,欲求从顶点1到顶点3之间的最短路径。利用给定的方法,无法求出顶点1到顶点3的路径。


考研公开课小程序

限时免费
资料推荐
更多>>
更多内容

关注新东方在线考研服务号

获得21考研真题及答案解析

1. 打开手机微信【扫一扫】,识别上方二维码;
2.点击【关注公众号】,获取资料大礼包。

考研资料大礼包
近10年考研真题及答案免费下载
更多>>
更多公开课>>
更多>>
更多资料
获取验证码
收不到短信?点此接收语音验证码
电话拨打中...请留意来自125909888237的来电
60秒后可重新获取
《新东方在线注册条款》  、  《隐私权保护政策》  及  《儿童隐私保护政策》
账号密码登录 找回密码
国际手机登录
《新东方在线注册条款》  、  《隐私权保护政策》  及  《儿童隐私保护政策》
手机快速登录 找回密码
获取验证码
收不到短信?点此接收语音验证码
电话拨打中...请留意来自125909888237的来电
60秒后可重新获取
《新东方在线注册条款》  、  《隐私权保护政策》  及  《儿童隐私保护政策》
账号密码登录 找回密码
国际手机登录
《新东方在线注册条款》  、  《隐私权保护政策》  及  《儿童隐私保护政策》
手机快速登录 找回密码
获取验证码
收不到短信?点此接收语音验证码
电话拨打中...请留意来自125909888237的来电
60秒后可重新获取
《新东方在线注册条款》  、  《隐私权保护政策》  及  《儿童隐私保护政策》
账号密码登录 找回密码
国际手机登录
《新东方在线注册条款》  、  《隐私权保护政策》  及  《儿童隐私保护政策》
手机快速登录 找回密码