dijkstra、kruskal 算法区别是什么？

dijkstra跟kruscal完全不一样，dijkstra跟prim算法倒是有几分相似之处。

dijkstra求单源最短路径

floyd求任意一对结点的最短路径

prim、kruscal求最小生成树

bellman求有负环的单源最短路径

prim算法以点为中心往四周扩散，每个结点只访问一次，往四周扩散时，贪心地选择容易去的结点，但是不会去那些已经被“组织”招安了的结点（都是内部成员了，就没必要再发展了）。星星之火，可以燎原，最终产生一个最小生成树。prim创建的是一个人人平等的社会。

dijkstra算法以点为中心往四周扩散，一个结点可能会访问多次，往四周扩散时，贪心选择那些容易去的结点，但是会去那些已经被“组织”招安了的结点，因为那些人虽然已经被组织招安了，但实际上“领导”（单源结点）对他的控制力不够强（领导到它的距离太远了），所以需要巩固，所以可以更新该点到“领导”的最短路径。dijkstra创建的是一个有“领导”的社会。

kruscal算法就比较简单了。kruscal每次都选图中最短的那条边（只要这条边能够不和已选边产生环即可）。kruscal就像群雄并起，各地爆发了规模不一的起义一样，群雄逐鹿。在整个起义过程中，起义军不断融合，最终组成了一支横跨整个图的军队。

prim算法注重点，kruscal注重边。

prim算法适用于点少边多（稠密）的情况，kruscal适用于点多边少（稀疏）的情况。

实现上，prim算法常常使用优先队列，kruscal常常用到并查集。