说明：本文大部分转自http://blog.chinaunix.net/uid-26548237-id-3834514.html
原创点是自己对该算法的理解，如有错误，请不吝指正，谢谢！
概述
图的最小生成树与最短路径没有太大的关联，只不过在一定程度上应用了贪心算法的思想而已，但二者区别却比较明显。
区别：
最小生成树能够保证首先是树（对于n个顶点的图只有n-1条边），其次保证任意两个顶点之间都可达，再次保证这棵树的边权值之和为最小，但不能保证任意两点之间是最短路径；
最短路径保证从源点S到目地点D的路径最小（有向图中不要求终点能到起点），不保证任意两个顶点都可达;
一个图如果有负权环...路径长可以无穷小 ,因为可以不断的走这个环降低权值，而最小生成树是有限的，它不是你怎么走的问题，而是生成一个两两都可达的最小权值和的树的问题。
最小生成树是用最小代价遍历整个图中所有顶点，所有的权值和最小。而最短路径只是保证出发点到终点的路径和最小，不一定要经过所有顶点；
最小生成树是到一群点（所有点）的路径代价和最小，是一个n-1条边的树，最短路径是从一个点到另一个点的最短路径；
最小生成树
一个连通图的生成树是一个极小的连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。那么我们把构造连通网的最小代价生成树称为最小生成树。
找连通网的最小生成树，经典的有两种算法，普里姆算法和克鲁斯卡尔算法。下面分别介绍两种算法。
一、普里姆（Prim）算法
普里姆算法，图论中的一种算法，可在加权连通图里搜索最小生成树。意即此算法搜索到的边子集所构成的树中，不但包括连通图里的所有顶点，且其所有边的权值之和亦为最小。
1.1 算法描述
从单一顶点开始，普里姆算法按照以下步骤逐步扩大树中所含顶点的数目，直到遍及连通图的所有顶点。
（1）输入：一个加权连通图，其中顶点集合为V，边集合为E；
（2）初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {}；
（3）重复下列操作，直到Vnew = V：
在集合E中选取权值最小的边（u, v），其中u为集合Vnew中的元素，而v则不是（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
将v加入集合Vnew中，将（u, v）加入集合Enew中；
（4）输出：使用集合Vnew和Enew来描述所得到的最小生成树。
1.2 例示
1.3 普里姆算法实现
<strong>//Prim算法最小生成树
void MiniSpanTree_Prime(Graph g)
{
int min, i, j, k;
int adjvex[MAXVEX]; //保存相关顶点下标
int lowcost[MAXVEX]; //保存相关顶点间边的权值
lowcost[0] = 0; //初始化第一个权值为0，即v0加入生成树
adjvex[0] = 0; //初始化第一个顶点下标为0
for(i = 1; i < g.numVertexes; i++)
{
//循环除下标为0外的全部顶点
lowcost[i] = g.arc[0][i]; //将v0顶点与之有边的权值存入数组
adjvex[i] = 0; //初始化都为v0下标
}
for(i = 1; i < g.numVertexes; i++)
{
min = INFINITY; //初始化最小权值为无穷大
j = 1;
k = 0;
while(j < g.numVertexes) //循环全部顶点
{
//如果权值不为0,且权值小于min
if(lowcost[j] != 0 && lowcost[j] < min)
{
min = lowcost[j]; //则让当前权值成为最小值
k = j; //将当前最小值的下标存入k
}
j++;
}
printf("(%d,%d)", adjvex[k], k);//打印当前顶点边中权值最小边
lowcost[k] = 0; //将当前顶点的权值设置为0，表示此顶点已经完成任务
for(j = 1; j < g.numVertexes; j++)//循环所有顶点
{
if(lowcost[j] != 0 && g.arc[k][j] < lowcost[j])
{
//若下标为k的顶点各边权值小于此前这些顶点未被加入的生成树权值
lowcost[j] = g.arc[k][j];
adjvex[j] = k; //将下标为k的顶点存入adjvex
}
}
}
printf("\n");
}
</strong>
由代码实现可知，邻接矩阵实现的Prim算法的时间复杂度为O(n^2)。
二、克鲁斯卡尔（Kruskal）算法
Prim算法是以某顶点为起点，逐步找各顶点上最小权值的边来构建最小生成树的。同样的思路，我们也可以直接就以边来构建生成树也是很自然的想法，只不过构建时要考虑是否会形成环路而已。此时，我们就用到了图的存储结构中的边集数组结构。以下是edge边集数组结构的定义代码：
typedef struct
{
int begin;
int end;
int weight;
}Edge;
我们可以通过程序将邻接矩阵通过程序转化为边集数组，并且对它们的按权值从小到大排序。如下图所示。
于是克鲁斯卡尔算法代码如下，左侧数字为行号。其中MAXEDGE为边数量的最大值，MAXVEX为顶点个数最大值。具体代码如下所示。
//查找连线顶点的尾部
int Find(int *parent, int f)
{
while(parent[f] > 0)
{
f = parent[f];
}
return f;
}
//克鲁斯卡尔算法实现
void MiniSpanTree_Kruskal(Graph g)
{
int i, n, m;
Edge edges[MAXEDGE]; //定义边集数组
int parent[MAXVEX]; //定义一数组用来判断边与边是否形成环
//此处为将邻接矩阵转化为边集数组edges并按权值由小到大排序
Convert(g, edges);
//
for(i = 0; i < g.numVertexes; i++)
{
parent[i] = 0; //初始化数组值为0
}
for(i = 0; i < g.numEdges; i++) //循环每一条边
{
n = Find(parent, edges[i].begin);
m = Find(parent, edges[i].end);
if(n != m) //假如n与m不等，说明此边没有与现有生成树形成环路
{
parent[n] = m; //将此边的结尾顶点放入下标为起点的parent中
//表示此顶点已经在生成树集合中
printf("(%d,%d) %d ", edges[i].begin, edges[i].end, edges[i].weight);
}
}
printf("\n");
}
克鲁斯卡尔算法的Find函数由边数e决定，时间复杂度为O(loge)，而外面有一个for循环e次，所以克鲁斯卡尔算法的时间复杂度为O(eloge)。此处不包括由邻接矩阵转为边集数组。
总结
对比两个算法，克鲁斯尔算法主要是针对边来展开，边数少时效率会非常高，所以对于稀疏图有很大的优势；而普里姆算法对于稠密图，即边数非常多的情况会更好一些。
最短路径
对于网图而言，最短路径就是两顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点是源点，第二个顶点是终点。而非网图可以理解为所有边的权值都为1的网。
一、迪杰斯特拉（Dijkstra）算法
Dijkstra算法是以起始点为中心向外层层扩展，直到扩展到终点为止，按照路径长度递增的顺序产生最短路径的算法。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。
1.算法思想
令G = （V，E）为一个带权有向图，把图中的顶点集合V分成两组，第一组为已求出最短路径的顶点集合S（初始时S中只有源节点，以后每求得一条最短路径，就将它对应的顶点加入到集合S中，直到全部顶点都加入到S中）；第二组是未确定最短路径的顶点集合U。在加入过程中，总保持从源节点v到S中各顶点的最短路径长度不大于从源节点v到U中任何顶点的最短路径长度。
2.算法步骤
（1）初始化时，S只含有源节点；
（2）从U中选取一个距离v最小的顶点k加入S中（该选定的距离就是v到k的最短路径长度）；
（3）以k为新考虑的中间点，修改U中各顶点的距离；若从源节点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值是顶点k的距离加上k到u的距离；
（4）重复步骤（2）和（3），直到所有顶点都包含在S中。
具体图例与算法执行步骤：（就从A开始，到各节点的最短路径）。
/* Dijkstra算法，求有向网g的v0顶点到其余顶点v的最短路径P[v]及带权长度D[v] */
/* P[v]的值为前驱顶点下标,D[v]表示v0到v的最短路径长度和 */
void ShortestPath_Dijkstra(Mgraph g, int v0, Patharc *P, ShortPathTable *D)
{
int v,w,k,min;
int final[MAXVEX]; /* final[w]=1表示求得顶点v0至vw的最短路径 */
/* 初始化数据 */
for(v=0; v<g.numVertexes; v++)
{
final[v] = 0; /* 全部顶点初始化为未知最短路径状态 */
(*D)[v] = g.arc[v0][v]; /* 将与v0点有连线的顶点加上权值 */
(*P)[v] = 0; /* 初始化路径数组P为0 */
}
(*D)[v0] = 0; /* v0至v0路径为0 */
final[v0] = 1; /* v0至v0不需要求路径 */
/* 开始主循环，每次求得v0到某个v顶点的最短路径 */
for(v=1; v<g.numVertexes; v++)
{
min=INFINITY; /* 当前所知离v0顶点的最近距离 */
for(w=0; w<g.numVertexes; w++) /* 寻找离v0最近的顶点 */
{
if(!final[w] && (*D)[w]<min)
{
k=w;
min = (*D)[w]; /* w顶点离v0顶点更近 */
}
}
final[k] = 1; /* 将目前找到的最近的顶点加入S集合中*/
/* 修正当前最短路径及距离 */
for(w=0; w<g.numVertexes; w++)
{
/* 如果经过v顶点的路径比现在这条路径的长度短的话 */
if(!final[w] && (min+g.arc[k][w]<(*D)[w]))
{
/* 说明找到了更短的路径，修改D[w]和P[w] */
(*D)[w] = min + g.arc[k][w]; /* 修改当前路径长度 */
(*P)[w]=k;
}
}
}
}
算法应用到了贪心思想，事实上如果S(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径，k和s是这条路径上的一个中间顶点，那么S(k,s)必定是从k到s的最短路径。这很容易证明，因为S(i,j)=S(i,k)+S(k,s)+S(s,j)，加入S(k,s)不是k到s的最短距离，则必然存在另一条边让i到j距离最短：S'(i,j)=S(i,k)+S'(k,s)+S(s,j)<S(i,j)，矛盾。所以基于这个假设，求i到j的最短路径，实际上把中间过程中的所有最短路径都求了一遍。
仔细比较该算法与最小生成树算法Prim，是不是感觉有点相似？但事实上两者还是有挺大不同，最关键的一点在于Prim更新的是已访问的集合与未访问集合（没有加入最小生成树的顶点）的距离，而Dijkstra算法更新源点v0到未访问集合（没有纳入最短路径的点）距离，比较代码如下：
for(j = 1; j<g.numVertexes; j++)//循环所有顶点
{
if(lowcost[j] != 0 && g.arc[k][j] < lowcost[j])
{
//若下标为k的顶点各边权值小于此前这些顶点未被加入的生成树权值
lowcost[j] = g.arc[k][j];
adjvex[j] = k; //将下标为k的顶点存入adjvex
}
}
for(w=0; w<g.numVertexes; w++)
{
/* 如果经过v顶点的路径比现在这条路径的长度短的话 */
if(!final[w] && (min+g.arc[k][w]<(*D)[w]))
{
/* 说明找到了更短的路径，修改D[w]和P[w] */
(*D)[w] = min + g.arc[k][w]; /* 修改当前路径长度 */
(*P)[w]=k;
}
}
最终输出D数组和P数组，假设D数组为{0,1,4,7,5,8,10,12,16}，P数组为{0,0,1,4,2,4,3,6,7}。D数组说明顶点到各个顶点的的最短距离，比如D[8]=16说明v0到v8最短距离为16，通过P数组能知道这条路径的样子：P[8]=7说明v8顶点前驱是v7，然后P[7]=6···依次类推得到v0->v1->v2->v4->v3->v6->v7->v8；
本算法从嵌套循环可以看出时间复杂度为O(n^2)，如果要求任一顶点到其他所有顶点的最短路径可以分别对n个顶点调用Dijkstra算法，算法复杂度O(n^3)。对此，介绍一个时间复杂度也为O(n^3)的算法--弗洛伊德（Floyd），该算法非常优雅简洁。
二、弗洛伊德（Floyd）算法
为了能讲明白该算法的精妙所在，先来看最简单的案例。下图左部分是一个最简单的3个顶点连通网图。
先定义两个数组D[3][3]和P[3][3]，D代表顶点到顶点的最短路径权值和的矩阵，P代表对应顶点的最小路径的前驱矩阵。在未分析任何顶点之前，我们将D命名为D^-1 ，其实它就是初始的图的邻接矩阵。将P命名为P^-1 ，初始化为图中所示的矩阵。
首先，我们来分析，所有的顶点经过v0后到达另一顶点的最短距离。因为只有三个顶点，因此需要查看v1->v0->v2，得到D^-1 [1][0] + D^-1 [0][2] = 2+1 = 3。D^-1 [1][2]表示的是v1->v2的权值是5，我们发现D^-1 [1][2] > D^-1 [1][0] + D^-1 [0][2]，通俗的讲就是v1->v0->v2比直接v1->v2距离还要近。所以我们就让D^-1 [1][2] = D^-1 [1][0] + D^-1 [0][2]，同样的D^-1 [2][1] = 3，于是就有了D0 的矩阵。因为有了变化，所以P矩阵对应的P-1[1][2]和P-1[2][1]也修改为当前中转的顶点v0的下标0，于是就有了P0。也就是说：
通过这里，我们已经看出了，Floyd算法是一个动态规划算法，为什么说它优雅？
用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题，我们需要为这个目标重新做一个诠释（这个诠释正是动态规划最富创造力的精华所在），floyd算法加入了这个概念
D^k(i,j)：表示从i到j中途不经过索引比k大的点的最短路径。
这个限制的重要之处在于，它将最短路径的概念做了限制，使得该限制有机会满足迭代关系，这个迭代关系就在于研究：假设D^(k-1)(i,j)已知，是否可以借此推导出D^k(i,j)。
假设我现在要得到D^k(i,j)，而此时D^(k-1)(i,j)已知，那么我可以分两种情况来看待问题：1. D^k(i,j)沿途经过点k；2. D^k(i,j)不经过点k。
(1)如果最短路径经过点k，那么很显然，D^k(i,j) = D^(k-1)(i,k) + D^(k-1)(k,j)，为什么是D^(k-1)呢？因为对(i,k)和(k,j)，由于k本身就是源点（或者说终点），加上我们求的是D^k(i,j)，所以满足不经过比k大的点的条件限制
(2)如果最短路径不经过点k时，可以得出D^k(i,j)=D^(k-1)(i,j)。故得出式子：
D^k(i,j) = min(D^(k-1)(i,j) , D^(k-1)(i,k)+D^(k-1)(k,j))；
接下来，其实也就是在D0和P0的基础上，继续处理所有顶点经过v1和v2后到达另一顶点的最短路径，得到D1和P1、D2和P2完成所有顶点到所有顶点的最短路径的计算。
首先我们针对下图的左网图准备两个矩阵D^-1和P^-1，就是网图的邻接矩阵以及初设为P[j][j] = j这样的矩阵，它主要用来存储路径。
具体代码如下，注意是：求所有顶点到所有顶点的最短路径，因此Pathmatirx和ShortPathTable都是二维数组。
/* Floyd算法，求网图G中各顶点v到其余顶点w的最短路径P[v][w]及带权长度D[v][w]。 */
void ShortestPath_Floyd(MGraph G, Patharc *P, ShortPathTable *D)
{
int v,w,k;
for(v=0; v<G.numVertexes; ++v) /* 初始化D与P */
{
for(w=0; w<G.numVertexes; ++w)
{
(*D)[v][w]=G.arc[v][w]; /* D[v][w]值即为对应点间的权值 */
(*P)[v][w]=w; /* 初始化P */
}
}
for(k=0; k<G.numVertexes; ++k)
{
for(v=0; v<G.numVertexes; ++v)
{
for(w=0; w<G.numVertexes; ++w)
{
if ((*D)[v][w]>(*D)[v][k]+(*D)[k][w])
{
/* 如果经过下标为k顶点路径比原两点间路径更短 */
(*D)[v][w]=(*D)[v][k]+(*D)[k][w]; /* 将当前两点间权值设为更小的一个 */
(*P)[v][w]=(*P)[v][k]; /* 路径设置为经过下标为k的顶点 */
}
}
}
}
}
下面介绍下详细的执行过程：
（1）程序开始运行，第4-11行就是初始化了D和P，使得它们成为 上图 的两个矩阵。从矩阵也得到，v0->v1路径权值为1，v0->v2路径权值为5，v0->v3无边连线，所以路径权值为极大值65535。
（2）第12~25行，是算法的主循环，一共三层嵌套，k代表的就是中转顶点的下标。v代表起始顶点，w代表结束顶点。
（3）当k = 0时，也就是所有的顶点都经过v0中转，计算是否有最短路径的变化。可惜结果是，没有任何变化，如下图所示。
（4）当k = 1时，也就是所有的顶点都经过v1中转。此时，当v = 0 时，原本D[0][2] = 5，现在由于D[0][1] + D[1][2] = 4。因此由代码的的第20行，二者取其最小值，得到D[0][2] = 4，同理可得D[0][3] = 8、D[0][4] = 6，当v = 2、3、4时，也修改了一些数据，请看下图左图中虚线框数据。由于这些最小权值的修正，所以在路径矩阵P上，也要做处理，将它们都改为当前的P[v][k]值，见代码第21行。
（5）接下来就是k = 2，一直到8结束，表示针对每个顶点做中转得到的计算结果，当然，我们也要清楚，D^0是以D^-1为基础，D^1是以D^0为基础，......，D^8是以D^7为基础的。最终，当k = 8时，两个矩阵数据如下图所示。
那么如何由P这个路径数组得出具体的最短路径呢？以v0到v8为例，从上图的右图第v8列，P[0][8]= 1，得到要经过顶点v1，然后将1取代0，得到P[1][8] = 2，说明要经过v2，然后2取代1得到P[2][8] = 4，说明要经过v4，然后4取代2，得到P[4][8]= 3，说明要经过3，........，这样很容易就推倒出最终的最短路径值为v0->v1->v2->v4->v3->v6->v7->v8。
求所有顶点之间最短路径的显示代码可以这样写：
for(v=0; v<G.numVertexes; ++v)
{
for(w=v+1; w<G.numVertexes; w++)
{
printf("v%d-v%d weight: %d ",v,w,D[v][w]);
k=P[v][w]; /* 获得第一个路径顶点下标 */
printf(" path: %d",v); /* 打印源点 */
while(k!=w) /* 如果路径顶点下标不是终点 */
{
printf(" -> %d",k); /* 打印路径顶点 */
k=P[k][w]; /* 获得下一个路径顶点下标 */
}
printf(" -> %d\n",w); /* 打印终点 */
}
printf("\n");
}
如果只需要求v0到v8的最短路径，不需要外面两层循环，直接令v=0,w=8即可。
由代码的执行过程可以知道，该算法需要三重循环进行D数组和P数组的修正，因此复杂度O(n^3)。
总结：
求最短路径的两个算法如果针对有向图依然有效，这两者的差异仅仅是邻接矩阵是否对称而已。