Question

Dijkstra算法与Prim算法的异同

Answer 1

Dijkstra算法用于构建 单源点的最短路径树 (MST)——即树中某个点到任何其他点的距离都是最短的。例如，构建地图应用时查找自己的坐标离某个地标的最短距离。可以用于有向图，但是 不能存在负权值 (Bellman-Ford可以处理负权值)。

Prim算法用于构建 最小生成树 ——即树中所有边的权值之和最小。例如，构建电路板，使所有边的和花费最少。只能用于 无向图 。

//无向图G, 权值w, 起始点r
MST(G, w, r) {
for each u in G,V {
//此处做初始化操作，给每个节点u赋键值+∞，设置空为父节点
u.key = +∞
u.parent = NULL
}
//选初始点r，Q是无向图G中所有点V的权值优先队列，key可看作u到下一个节点v的距离
r.key = 0
Q = G,V
while(Q != ∅) ｛
//取出Q中权值最小值的点u
u = extractMin(Q)
//取点u连接的所有节点(即无向图G的邻接表中的第u个链表)
for each v ∈ G.Adj[u] {
if (v ∈ Q) and (w(u, v) < key) {
//若该节点仍在Q中且权值w(w,v)小于其原始权值，则进行松弛操作！
v.parent = u
v.key = w(u, v)
}
}
}
}