01

60 秒回答模板

Dijkstra 和 Prim 表面上都像每次选一个最小代价节点，但解决的问题不同。Dijkstra 求从源点到其他点的最短路径，dist[v] 表示源点到 v 的当前最短距离，要求边权非负；Prim 求连通无向图的最小生成树，key[v] 表示把 v 接入当前生成树的最小边权。Dijkstra 更新的是路径距离 dist[u] + w，Prim 更新的是接入边权 w。前者输出最短路径树，后者输出总权重最小且连接所有点的生成树。

考点 最短路径
难度 真实面经题
回答目标 讲清方法、边界和追问
02

深入解析

01

问题目标不同

Dijkstra 关注从一个源点到各点的最短距离；Prim 关注用最小总边权把所有节点连成一棵树，不关心从某个源点到每个点的路径最短。

02

状态含义不同

Dijkstra 的 dist 是源点到节点的路径长度。Prim 的 key 是当前生成树外节点接入树的最小边权，两者虽然都取最小，但语义完全不同。

03

松弛公式不同

Dijkstra 用 dist[u] + weight(u, v) 更新 dist[v]；Prim 只比较 weight(u, v) 是否能提供更便宜的接入边。

04

适用图和边权

Dijkstra 要求非负边权，否则贪心确定的最短距离可能被后续负边推翻。Prim 用于连通无向图的最小生成树，边权可以为负。

05

输出结果不同

Dijkstra 输出距离数组和最短路径前驱；Prim 输出生成树边集合和最小总权重。面试中要把结果形态说清楚。

03

易错点

  • 不要只说它们都是贪心算法，必须区分求解目标。
  • 不要把 Prim 的 key 当成源点距离。
  • 不要忘记 Dijkstra 的非负边权前提。
04

面试官追问

Dijkstra 为什么不能处理负权边？

因为已确定节点的最短距离可能被后续负权路径改小，破坏贪心选择的正确性。

Prim 和 Kruskal 有什么区别？

Prim 从一个连通分量逐步扩展，Kruskal 按边权排序并用并查集避免成环。

两者复杂度如何优化？

邻接表加优先队列通常可做到 O(E log V)，稠密图也可用邻接矩阵 O(V^2) 实现。