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