题目

带权图(权值非负，表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：

① 设最短路径初始时仅包含初始顶点，令当前顶点 u 为初始顶点；

② 选择离 u 最近且尚未在最短路径中的一个顶点 v，加入到最短路径中，修改当前顶点 u=v；

③ 重复步骤 ②，直到 u 是目标顶点时为止。

请问上述方法能否求得最短路径？若该方法可行，请证明之；否则，请举例说明。

解析

答案

该方法不能保证求出最短路径——它是一种"近视贪心"，可用反例否定。

反例

构造一个 4 顶点带权图：

边权：S→A = 1，A→T = 10，S→B = 3，B→T = 1。

按题面方法（从当前顶点选最近邻居）：

步	当前 u	"离 u 最近且未在路径中"的顶点	加入路径
起	S	S→A=1（比 S→B=3 短）	A
2	A	A→T=10（A 唯一未访问邻居）	T

得到的"最短路径" S → A → T，长度 1 + 10 = 11。

但实际最短路径是 S → B → T，长度 3 + 1 = 4。

显然 4 < 11——题面方法错过了真正的最短路径。

错在哪里

题面算法的本质缺陷是只看"当前顶点 u 的邻居"中谁最近，而不是所有已遍历顶点到起点的距离中谁最小。它一旦选错下一个顶点（被局部短边诱惑），就再也回不去了——典型的近视贪心。

正确做法是 Dijkstra 算法：维护"已知最短距离集合 V_T"，每轮扩张时从所有"V_T 一端在内、一端在外"的边里选起点累计距离 + 边权最小的一端加入，而不是只看当前顶点 u 的最近邻。两者的关键区别：

项目	题面方法（错）	Dijkstra（对）
候选	仅当前 u 的邻居	所有 V_T 内顶点的邻居
选谁	离 u 最近的	离起点累计距离最小的
全局视野	无	有

编者注（生僻术语）：题面这种"每步从当前位置选最近"的算法在算法领域有时被称为「最近邻启发式（Nearest-Neighbor Heuristic）」，常用于近似求解 TSP（旅行商问题），但不能用于求最短路径——它根本不是 Dijkstra。考研学生最容易把这两者搞混，看到"贪心选最近"就以为对，其实差之毫厘谬以千里。