问答题 带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径,假设从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法:①设最短路径初始时仅包含初始顶点,令当前顶点“为初始顶点;②选择离u最近且尚未在最短路径中的一个顶点v,加入到最短路径中,修改当前顶点u=v;③重复步骤②,直到u是目标顶点时为止。请问上述方法能否求得最短路径?若该方法可行,请证明之,否则,请举例说明。【2009年全国试题41(10分)】
【正确答案】正确答案:上述方法不能求得最短路径。离u最近未必离初始顶点最近。例如,下图求v 0 到v 1 的最短路径,按题目所给方法得45(v 0 一v 2 一v 3 一v 1 ),并非最短路径。详细证明请参照Dijkstra或Floyd算法。
【答案解析】