比较Dijstra和Prim

Dijstra 和 Prim 算法比较

2018/5/22

引言：Dijstra和Prim算法是图论中两种基础的优化算法。只要与图相关的问题，都有可能会用这两种算法来解决问题。信息专业的人一定是学过这两种算法的，不过不知道别人有没有这种感觉，我常常会分不清这两种算法，总觉得这两种算法非常的相似，甚至有时候有的人会把这两种算法混淆着用。为了彻底摆脱这一困惑，决定写篇文章，来区分Dijstra和Prim。

应用场景不同：

Dijstra 和 Prim都是优化算法，但是他们的应用场景不一样。Dijstra是最短路径算法，用来解决在一个图上寻找一个起点到一个终点的最短路径这样的问题；Prim是最小生成树算法，即对于一个图，寻找一个能够包含所有顶点且边的权值和最小的树。

算法步骤不同：

因为解决的问题不同，这两种算法的具体实现方法也就存在差别。

\textcolordarkblueDijstra$\text{textcolor}darkblueDijstra$

• 基本思想：最短路径的求解过程中，图中的顶点分属两个集合：指定出发点的顶点为一个集合V，其余顶点为一个集合W。从W中选择一个离V中顶点最近的一个顶点加入到V中，求出了长度最短的一条最短路径，并把刚选择加入最短路径的顶点作为中间点，对其它顶点到源点的路径长度进行修改，求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止。

• 实现步骤：

  ​ （1）集合S$S$和T=V−S$T=V-S$，S$S$中存放已找到最短路径的顶点，T$T$存放当前还未找到最短路径的顶点。初态，S$S$中只包含源点v0$v_0$ 。

  ​ （2）不断从T$T$中选取到顶点v0$v_0$路径长度最短的顶点u$u$加入到S$S$中，S$S$每加入一个新的顶点u$u$，都要修改顶点v0$v_0$到T$T$中剩余顶点的最短路径的长度，T$T$中各顶点新的最短路径长度值为原来的最短路径长度值与顶点u$u$的最短路径长度值加上u$u$到该顶点的路径长度值中的较小值。

  ​ （3）重复（2），直到T$T$的顶点全部加入到S$S$中为止。

\textcolordarkbluePrim$\text{textcolor}darkbluePrim$

• **基本思想：**Prim算法是在由n 个顶点组成的无向连通图中，取图中任意一个顶点V作为生成树的根，之后向生成树上添加新的顶点W。在添加的顶点W和已经在生成树上的顶点V之间必定存在一条边，并且该边的权值在所有连通顶点V和W之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有n个顶点为止。

• 实现步骤：

  G=（V，E）$G=（V，E）$是连通网，TE$TE$是G$G$上最小生成树中边的集合。
  　　初态：U={u0|u0∈V}$U=\{u_0|u_0\in V\}$，TE={}$TE=\{\}$开始，重复执行下述操作：
  　　（1）在所有u∈U$u\in U$，v∈V−U$v\in V-U$的边（u，v）∈E$（u，v）\in E$中找一条带权最小的边（u0，v0）$（u_0，v_0）$并入集合TE，v0$TE，v_0$并入U$U$。
  　　（2）重复（1）直至U=V$U=V$为止。此时TE$TE$中必有n−1$n-1$条边，则T=（V，TE）$T=（V，TE）$为N$N$的最小生成树。

  示意图比较

  该部分引用自参考资料中的论文。

假设给定下面的图 2.1.1 和 2.2.1 两个 图，图 2.2.1 是用普里姆（Prim）算法构造最小生成 树，其最小生成树的过程如下表 2.1.1 到表 2.1.6 和 图 2.1.1 到图 2.1.6 所示；图 2.2.1 用迪杰斯特拉 （Dijkstra）算法求单源最短路径，其求单源最短路径 的过程如下表 2.2.1 到表 2.2.6 所示。

下面是论文中总结的两种算法的区别：

参考资料：

杨智明，普里姆（Prim）与迪杰斯特拉（Dijkstra） 算法对比分析 ，保山师专学报，2009年9月.