一连通无向图，边非负权值，问用 Dijkstra 最短路径算法能否给出一棵生成树，该树是 否一定是最小生成树?说明理由。

[tag_link]

参考答案

Dijkstra 算法能给出一棵以源点为根的最短路径树，但这棵树不一定是最小生成树。

原因是两种贪心目标不同：Dijkstra 每次固定“从源点到某顶点的当前最短距离”，而 Prim 每次选择“已入树顶点集合到树外的最轻边”。前者优化每个顶点到源点的路径，后者优化整棵树的边权总和。

反例：无向图有边 a-b=5、a-c=5、a-d=5、b-d=1、c-d=1。从 a 出发执行 Dijkstra，在三个距离同为 5 的顶点中先固定 d 时，a-b 和 a-c 仍分别比绕经 d 的距离 6 更短，因此可得到边集 {a-b,a-c,a-d}，总权值为 15。最小生成树则可取 {a-d,b-d,c-d}，总权值为 7。

所以“能生成树”正确，“一定是最小生成树”错误。