Dijkstra、Prim、Kruskal

Dijkstra算法用于解决单源最短路径问题，用到贪心算法。常用于稠密图，不能用于负权边。用于稀疏图时，可考虑使用优先队列（二叉堆或斐波那契堆）。

Prim和Kruskal算法用于最小生成树。

Prim算法的执行非常类似于寻找图的最短通路的Dijkstra算法。Prim算法的特点是集合A中的边总是只形成单棵树。如图5所示，阴影覆盖的边属于正在生成的树，树中的结点为黑色。在算法的每一步，树中的结点确定了图的一个割，并且通过该割的轻边被加进树中。树从任意根结点r开始形成并逐渐生长直至该树跨越了V中的所有结点。在每一步，连接A中某结点到V-A中某结点的轻边被加入到树中，由推论2，该规则仅加大对A安全的边，因此当算法终止时，A中的边就成为一棵最小生成树。因为每次添加到树中的边都是使树的权尽可能小的边，因此上述策略也是贪心的。

有效实现Prim算法的关键是设法较容易地选择一条新的边添加到由A的边所形成的树中，在下面的伪代码中，算法的输入是连通图G和将生成的最小生成树的根r。在算法执行过程中，不在树中的所有结点都驻留于优先级基于key域的队列Q中。对每个结点v，key[v]是连接v到树中结点的边所具有的最小权值；按常规，若不存在这样的边则key[v]=∞。域p[v]说明树中v的“父母”。在算法执行中，GENERIC-MST的集合A隐含地满足：

A={(v,p[v])|vÎV-{r}-Q}

当算法终止时，优先队列Q为空，因此G的最小生成树A满足:

A={(v,p[v])|vÎ V-{r}}

MST-PRIM(G,w,r)
1. Q←V[G]
2. for 每个uÎQ
3.   do key[u]←∞
4. key[r]←0
5. p[r]←NIL
6. while Q≠Æ
7.   do u←EXTRACT-MIN(Q)
8.      for 每个vÎAdj[u]
9.        do if vÎQ and w(u,v)<key[v]
10.            then p[v]←u
11.                 key[v]←w(u,v)


Kruskal算法：连续的按照最小的权选择边，并且当所选的边不产生圈时就把它作为取定的边。形式上是在处理一个森林。算法实际上是要决定边（u，v）应该添加还是放弃。需要判断顶点u，v是否在同一集合中。在算法实施的任一时刻，两个顶点属于同一个集合当且仅当它们在当前的生成森林中连通。


  Dijkstra算法                                                         Prim算法

1.寻找与源点相连的最近的点V并标记                   1.寻找距生成树最近的点V

2.用点V来对剩余未标记的点经行松弛操作            2.将点V加入生成树

3.重复1、2直至所有点都被标记                           3.重复1、2直至所有点加入生成树中