Dijkstra算法 vs Prim算法

两种算法伪代码结构高度相似，都使用优先队列进行贪心选择，但解决不同问题且key的更新规则有本质区别

共同点

都使用贪心策略 + 优先队列（最小堆）的算法框架
伪代码结构几乎完全相同：初始化 → while循环(EXTRACT-MIN) → 遍历邻接顶点 → 更新key
时间复杂度相同：二叉堆 $O (E l g V)$ ，斐波那契堆 $O (V l g V + E)$
都从一个起始顶点出发，逐步扩展已确定顶点集合
都不适用于含负权边的场景（Dijkstra明确不能，Prim的MST问题通常定义在无负权环的图中）

关键区别

维度	Dijkstra算法	Prim算法
目标	单源最短路径	最小生成树
解决的问题	从源点到所有顶点的最短路径	连接所有顶点的最小权边集
key 含义	从源点到该顶点的最短路径估计	连接到当前生成树的最小边权
更新规则	$d [v] = min (d [v], d [u] + w (u, v))$	$key [v] = min (key [v], w (u, v))$
松弛条件	$d [v] > d [u] + w (u, v)$	$w (u, v) < key [v]$
是否累加	是——累加从源点出发的路径总权	否——只看直接边权
集合 $S$ 的含义	已确定最短路径的顶点	已加入MST的顶点
起始顶点	源点 $s$ （有特定含义）	任意顶点 $r$ （无特定含义）
适用图类型	有向/无向图，边权非负	无向连通图
正确性依据	三角不等式 + 边权非负	割性质（安全边定理）
key 的信息范围	全局——与源点的累计距离	局部——只与父节点有关

深层联系

两种算法的结构相似性源于它们都采用了”每次选最小key的顶点，更新其邻居”的贪心框架，但key的语义不同导致了本质区别：

Dijkstra的key是路径距离（累加的），需要加上 $d [u]$ （从源点到 $u$ 的累计距离），因此要求边权非负以保证贪心选择的正确性。
Prim的key是边权（非累加的），只看 $w (u, v)$ （直接边权），不依赖边权正负。

直观记忆：Prim在”长树”（找最小的边把新节点连进树），Dijkstra在”找路”（找从源点出发的最短路径）。Prim的key是局部信息，Dijkstra的key是全局信息。

参见