相似点

• 首先，两个算法都是利用优先队列实现，都是典型的贪心策略算法。

• 其次，都是以一个无向图G，起始定点start，作为参数。

不同点

其算法程序框架几乎一样，不同点如下：

• Dijkstra算法利用节点的dist属性来记录节点到起始节点的最短权重距离

• 而prim算法则利用节点的dist属性来记录节点到已建树节点集合的最小权重代价；

• Dijkstra算法每次从优先队列提取的是到起始节点最短权重距离的节点作为当前节点，

• 而prim算法每次从优先队列提取的是到已建树节点集合最小权重代价的节点作为当前节点；

• Dijkstra算法遍历当前节点的每一个邻接节点，如果当前节点最短权重距离加上邻接边权重，比邻接节点已有的最短权重距离还短，那就更新邻接节点的最短权重距离和前驱；

• prim算法遍历当前节点的每一个安全邻接节点（不在已建树节点集合里），如果当前节点到安全邻接节点的权重，比安全邻接节点已有的最小权重代价还小，那就更新安全邻接节点的最小权重代价和前驱；

• Dijkstra算法执行完毕后，每个节点的dist记录了到起始节点的最短距离，pred记录了最短距离路径的前驱节点；

• prim算法执行完毕后，每个节点的dist记录了到前驱节点的边权重，pred记录了最小生成树路径的前驱节点，把所有dist求和，就是最小生成树的权重代价。

Dijkstra算法代码及测试用例

算法代码

测试用图

测试结果

[u,0,None] [v,2,u] [w,3,y] [x,1,u] [y,2,x] [z,3,y]

prim算法代码及测试用例

算法代码

测试用图

测试结果

[A,0,None] [B,2,A] [C,1,B] [D,1,B] [E,1,D] [F,1,E] [G,1,F] 
[v1,0,None] [v2,5,v3] [v3,1,v1] [v4,2,v6] [v5,3,v2] [v6,4,v3]

文件下载

请点击阅读原文到实验室网页最下方查看和下载算法代码。