带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短__N诺考研

登录注册上岸

学习人数: 743

正确率: 100%

未通过

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

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

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

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

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

个人笔记

已有2条笔记

加入错题本

登录后提交答案

3 个回答 (点击展开回答)