浅显易懂地解释Prim算法与Dijkastra算法的区别

Prim是用来计算最小生成树的算法，计算的是整一棵树最小的权值总和。比如给n个小村庄修路，怎样铺路才能使得每个村庄都通路并且开销最小。
Dijkastra是用来计算单源最短路径，即源点到某一点的最短路径。比如，A村庄到B村庄，怎么走最短。

prim算法中，找出到树内每一个顶点权值最小的树外顶点，并把它收录进树中，直到图中的每个顶点都被收录进树里。如图中，红线标记的路径为7，这是唯一的最小的开销。

Dijkastra算法中，计算的是源点到某一顶点的最短路径。如图中，从源点到最上端的顶点总路径为6，如果按prim算法来走的话，路径为7，很明显不是最短路径了。
因此在本质上，prim是比较树和树外顶点的距离，而Dijkastra是比较源点到某个顶点路径距离。