按理说迪杰斯特拉算法与普里姆算法不是一类东西，前者是最短路径算法，后者是最小生成树算法，为什么会放在一块呢？因为二者实在是太相似了。不管是从代码结构上以及分析方法上来说。对于我这种小白而言，看一百遍，合上书还是会忘了从哪开始编写代码。好在学了一些动态规划的东西，现在这两个算法从头写到尾是没有问题了。
下面使用的例子（图），出自程杰的《大话数据结构》，之前我也是在用这本书学习数据结构，也是朋友推荐我的，此书比较基础，没有讲到动态规划的东西。
写这两个算法还是比较简单的，这里记录的东西是我个人的推导思路以及想到的比较重要的点。有疑义的地方，可以去看看《大话数据结构》和《算法导论》的相关章节，一起学习进步。
问题：如上图，以V0为起点求V0到各点的最短路径。
（1）动态规划的求解思路是，每次求得的最短路径的点是基于上次求得的最短路径的点，如V0到V2是在V0到V1的基础上得到的，所以每次都要选取V0所到路径最短的点来求解V0到下一个点的最短路径。当然，感觉这就跟没说一样。
（2）思路是这样，代码如何构建呢？首先需要一个邻接矩阵MGraph来存储这张图。
（3）此处是起点V0点，无论起点是哪个都是一样的道理。那么就用起点V0来初始化。创建一个数组ShortPathTable来存储V0到各点的最短路径值，也就是循环ShortPathTable[i]=MGraph[0][i]。一开始，V0只能到V1，V2所以该数组的值就是{0，1,3，INFINITY，INFINITY，INFINITY，INFINITY，INFINITY，INFINITY}，INFINITY为无限大。
（4）基于思路（1），利用循环，从ShortPathTable（因为它存储V0到各点的最短路径值）中找一个路径值最短的点，此处也就是V1。
（5）此时V0通过V1就可到达V2，V3，V4了，从而更新ShortPathTable数组，肯定不能乱更新，要做判断，通过V1就可到达V2，V3，V4的路径值要小于V0到达V2，V3，V4的路径值，如V0到V4为无限大，而现在为5+1=6，就可以更新了。做循环更新这个ShortPathTable数组之后，重复步骤4，找到了V2。
（6）利用V2重复步骤（5），就是这两步反复操作：1，找最小的点；2，比较通过最小点找到的新路径值，如果比以前小就更新。
（7）要循环所有的点（V0初始化是执行过了），所以有（4）（5）外有一个大循环，执行n-1次，n为点的个数。
（8）当然会有几处疑问。
（9）疑问一：比如V1它又找回V0怎么办？设置一个数组fin，到过的点设为1，那么V1在遍历自己边的权值时，判断相邻点在fin数组中的值是否为1，为1就跳过。
（10）疑问二：只有ShortPathTable的话只能求得到V0到该点的最小权值，得不到沿途路径怎么办？再建一个数组Patharc，值为到达改点的前驱结点，在更新ShortPathTable时，同时更新Patharc。
(11)疑问三：如果是下面这张图，修改V1，V2，V4的边权值好像就有点混淆了？
到达V4的最短路径不是由V2决定的，是由V1决定的，因为V0通过V1到V4时ShortPathTable中对应值已更新，V0通过V2到V4时其值大于原值，不更新。不能说明到V4的最短路径值不是由上一个点决定的。应该如下图：
迪杰斯特拉算法：
#define INFINITY 65535 //无穷值 typedef int Patharc[Maxvex];//存储到该结点的前驱结点 typedef int ShortPathTable[Maxvex];//存储路径长度 void ShortestPath_Dijkstra(int v0, int G[Maxvex][Maxvex], Patharc *p, ShortPathTable *s) { int w,k; int fin[Maxvex];//防止重复判断已求出最短路径的点，1为已判断，0为未判断 for (w = 0; w < Maxvex; w++) { (*s)[w] = G[v0][w];//初始化路径 (*p)[w] = 0;//没有前驱结点 fin[w] = 0; } fin[v0] = 1; for (int i = 0; i < Maxvex;i++) { int min = INFINITY; for (w = 0; w < Maxvex;w++) { if (!fin[w]&&(*s)[w]<min) { k = w;//求出当前距离起点最近的点，已充当过的点除外 min = (*s)[w]; } } fin[k] = 1; for (w = 0; w < Maxvex;w++) { if (!fin[w] && (min + G[k][w] < (*s)[w])) { (*s)[w] = min + G[k][w]; (*p)[w] = k;//前往w的前驱是k } } } }打印路径结果，V是起点，e是终点
while (e != v){ cout << e << "<-"; e = p[e]; } cout << v << endl;V0->V8
V0->V5
问题：如上图，求解最小生成树。
（1）分析思路与迪杰斯特拉算法是一样的。首先需要一个邻接矩阵MGraph来存储这张
（2）此处是起点V0点，无论起点是哪个都是一样的道理。那么就用起点V0来初始化。创建一个数组LowCost来存储V0到各点边的最小权值，也就是循环LowCost[i]=MGraph[0][i]。一开始，V0只能到V1，V2所以该数组的值就是{0，10,11，INFINITY，INFINITY，INFINITY，INFINITY，INFINITY，INFINITY}，INFINITY为无限大。
（3）基于思路，利用循环，从LowCost中找一个相邻边权值最短的点，此处也就是V1，此处顺便把V1在LowCost中的值赋值为0，代表此点已经选中，作用就像迪杰斯特拉算法中Fin与ShortPathTable的结合，不用担心0是最小的，可以控制其值不等于0时，再求最小的。
（4）此时V0通过V1就可到达V2，V6，V8了，从而更新LowCost数组，做判断，通过V1就可到达V2，V6，V8的边权值要小于V0到达V2，V6，V8的边权值，如V0到V2为无限大，而现在为18（注意不是做加法了，不需要做加法了，最后求的不是到某一点，而是整个最小生成树的值），就可以更新了。做循环更新这个LowCost数组之后，重复步骤3，找到了V5。
（5）重复步骤，要循环所有的点（V0初始化是执行过了），所以有（3）（4）外有一个大循环，执行n-1次，n为点的个数。
（6）最后几步不一一列举了，直接给出最终图，要注意的是，如V1与V2的边，由于V1，V2对应的LowCost都置为0，所以不会去比较18了，同理V5，V6。
普里姆算法：
void Prim(int M[Maxvex][Maxvex]) { //从0结点开始 int adjvex[Maxvex];//存储对应结点的临结点 int lowcost[Maxvex];//存储对应结点的权值 adjvex[0] = 0; lowcost[0] = 0;//0值代表已经，对该结点已经选中过了 //初始化 int i,j=0,min,k;//k是用来临时存储权值最小点 for (i = 1; i < Maxvex;i++) { lowcost[i] = M[0][i]; adjvex[i] = 0; } //开始计算 for (i = 1; i < Maxvex;i++) { min = INFINITY; j = 1; k = 0; //选出当前结点，相邻结点权值最小点 while (j < Maxvex) { if (lowcost[j]!=0&&lowcost[j]<min) { min = lowcost[j]; k = j; } j++; } //打印 cout << adjvex[k] << " " << k << endl; lowcost[k] = 0;//k被选中 //求k结点相邻的结点的权值，并更新lowcost数组 for (j = 1; j < Maxvex; j++) { if (lowcost[j] != 0 && M[k][j]<lowcost[j]) { lowcost[j] = M[k][j]; adjvex[j] = k;//前往j点的临结点为k } } } }结果第一列是某点前驱，如0,1说明V1的前驱是V0。需要求得最终值的话，就不去置0 LowCost数组，而是也使用Fin数组。
洋洋洒洒终于写完了，花了好几个小时，画图比较费工夫。反正我是又复习了一遍，希望对看到这篇博客的朋友也能有些许帮助吧，那我就很开心了。
这是原项目的下载链接（20和21）：https://github.com/AngryCaveman/C-Struct.git