全部题库 / 计算机 / 试题详情
简答题 计算机
2013-09-26

带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法: 
①设最短路径初始时仅包含初始顶点,令当前顶点u为初始顶点; 
②选择离u最近且尚未在最短路径中的一个顶点v,加入到最短路径中,修改当前顶点u=v; 
③重复步骤②,直到u是目标顶点时为止。 
请问上述方法能否求得最短路径?若该方法可行,请证明之;否则,请举例说明。 

参考答案

暂无

答案解析

该方法求得的路径不一定是最短路径。例如,对于下图所示的带权图,如果按照题中的原则,
从A到C的最短路径为A→B→C,事实上其最短路径为 A→D→C。 

你可能感兴趣的试题