最短路径问题

xuchaokyle

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

Sorehead

不可行，反例很简单，楼主自己想想吧。
建议楼主看看数据结构，里面有求最短路径的算法。

duanjigang

原帖由 xuchaokyle 于 2009-1-12 21:53 发表
带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：
1）设最短路径初始时仅包 ...

呵呵，这个好说吧，比如a到U的距离小于b到U的距离，但是却没法保证a到终点的距离一定小于b到终点的距离
附件是我做得一个例子，按照题目中的算法，得到的最短路径为红线，实际的最短路径却是兰线。
迪杰斯特拉算法的问题。