返回主页
已有1条笔记
[数据结构 P2010] 带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短
未通过
带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：
① 设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点；
② 选择离u最近且尚未在最短路径中的一个顶点v，加入到最短路径中，修改当前顶点u=v；
③ 重复步骤②，直到u是目标顶点时为止。
请问上述方法能否求得最短路径？若该方法可行，请证明之；否则，请举例说明。
加入错题本
个人笔记
解答：
该方法不一定能（或不...
用户登录可进行刷题及查看答案
解答：
该方法不一定能（或不能）求得最短路径。
例如，对于下图所示的带权图，如果按照题中的原则，从 A 到 C 的最短路径是 A->B->C，事实上其最短路
径是 A->D->C。
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后提交答案