说明:本文大部分转自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)。
总结:
求最短路径的两个算法如果针对有向图依然有效,这两者的差异仅仅是邻接矩阵是否对称而已。