开源中文网

您的位置: 首页 > 算法 > 正文

通信网络规划的最短路径(最小生成树的2种算法介绍)

来源: imsz5460的博客  作者: imsz5460

《大话数据结构》中在“图”的那一章节有这样一个实例:假设你是电信实施工程师,需要为一个镇的九个村庄架设通信网络做设计。村庄位置大致如下图,之间连线的数字表示村与村间的可通达直线距离(个别如v0与v6,v6与v8,v5与v7未测算距离是因为有高山或湖泊,不予考虑)。你们领导要求你必须用最小的成本完成这次任务。你说怎么办?

我之前在某家设计院也是做网络规划设计的,而且觉得很有实际意义,所以拿出来给大家分享一下。其实这个案例就是查找连通网的最小生成树。这术语不懂也没关系,我们不管它叫什么。

有人说,这还不简单嘛,我凭着直觉就能做出来。不排除你有这种能力,有时候人类的“直觉”真的是强大,也不知道人类是如何进化到这么聪慧的。

有人说,把所有可能的方案罗列出来,再一一比对,找到最短路径的那个方案,就行了。这确实是个好办法,实际上我们也是这样做的。那么怎么去罗列所有的方案呢?。

为了便于描述上面的图,我们构造图的邻接矩阵。如下图所示:

在单纯的计算或者有规律的运算方面,我们很容易想到借助计算机来帮忙解决。 刚刚我提到人类的直觉是很强大的,比如有的人答题的时候直接省略了步骤得出了结果,而要他写详细的步骤可能他也说不太清。计算机是没有直觉的,某些我们认为很简单的东西她可能要运算很多次,而且你还得教她怎样按照她自己“有限的能力”去执行,可是往往我们不知道怎么去教计算机,也就是具体的怎样写代码。

这里介绍两种思路,也就是两个算法:

一、一种思路是这样的:

从v0(可以任意选定一点,这里选v0)开始,找到与其相连的最短的路径,定义两个一维数组a,b。a存储相关顶点的权值(边长度),b存储对应的顶点。路径(b[i],i)的权值为a[i].i为0至8的整数,v0为起点至各点的权值如下所示(实际中我们用65535来代表无穷大)。

求a数组中的最小值,为10,对应的i为1,标记边(v0,v1)并让ai置为0,代表vi已经纳入生成路径了(此时i为1)。

然后从v1开始,排除a[i]=0对应的顶点vi,当(v1,vi)的权值小于此时a[i]的值,将前者替换掉后者,更新a数组的值。

求a数组中的最小值,为11,对应的i为5,标记边(v0,v5)并让a5置为0,代表v5已经纳入生成路径了。

然后从v5开始,排除a[i]=0对应的顶点vi,当(v5,vi)的权值小于此时a[i]的值,将前者替换掉后者,更新a数组的值。

 

下面的步骤依此类推,以表格表述。

上面这个一步步找到最优路径的方法其实就是普里姆算法。是不是很巧妙呢?我猜是一个叫普里姆的人发明的方法。具体的代码实现如下(从《大话数据结构》拷贝的):

二、一种思路是这样的:

将各边所对应的起始点及权值(边长)按权值排序,整理成下表所示:

这种方法就是以边为核心,每次搜索相关的最短边,排除掉形成闭环的边。

第一次找到的边为(v4,v7)

第二次找到的边为(v2,v8)

第三次找到的边为(v0,v1)

第四次找到的边为(v0,v5)

第五次找到的边为(v1,v8)

第六次找到的边为(v3,v7)

第七次找到的边为(v1,v6)

第八次找到的边为:这次按边长排序轮到(v5,v6),但是此时与上面所找到这些边形成了环路。过滤掉!

第九次找到的边为:这次按边长排序轮到(v1,v2),但是此时与上面所找到这些边形成了环路。过滤掉!

第十次找到的边为(v6,v7)

此后的边均构成环路,过滤掉。

过程是很明晰的,但是算法的具体实现却很精妙。也是用数组的模型,占位更新的思想去实现。每次确定了一条边就在数组中相应位置用相关值做上标记。判断是否形成环路的方法也是很巧妙的,桥接起了边与起始点的关系:形成一个环路就是起始点首尾依次连接,最后回到起点。

下面贴上代码及分析:

最终最小生成树就是如下图标黑所示:

 

对比两个算法,克鲁斯算法边数少时,效率会非常高;而普里姆算法对于边数非常多的情况会更好一些。

关于这两个算法相信大家都大概了解了。或许有人会对上面算法的正确性存疑,可以在网上搜索一下相关证明或者验证,我这边提供一个链接作为参考http://www.cnblogs.com/biyeymyhjob/archive/2012/07/30/2615542.html

Tags:通信网络 算法
关于开源中文网 - 联系我们 - 广告服务 - 网站地图 - 版权声明