`

最短路径查找-prim算法和kruskal算法

 
阅读更多

如坐车网中的最优坐车路线一样,本质就是探寻最短径距.即最小生成树生成问题.

当然坐车网中得出結果后还要进行车辆换乘问题,但这更易了.

 

prim算法

一个V set来存放结点,E set存放边.每次从树中选取V的最近邻,形成的一条边,但条件是与E中的不能有loop.

如此循环,直到 | E | = n - 1,n为顶点数.(如果直接使用数学表达式来表达是非常严谨的,也不容易知道.还是通过例子才容易理解)

 

 特点:

  a.結果不唯一,因为当遇到相同权值时情况;

  b.由于a的出现,使得結果可能陷入局部最小值,即非所谓的'最小'生成树.但事实上这算法是有可能的.

  c.适合于顶点数多的情况

 

kruskal算法

E set中保存选择后的边,S为所有的边集合.

 首先,在S中选择最小权植的边,然后E=E U e(i),S=S-e(i),但前是e(i)与E不构成回路(因为結果是树,树是没有回路的)

 然后,如此循环,直到  | E | = n - 1为止.这点与prim是一样的.

特点:

 a.适合于边较少的R.因为其实每次选择最小权边时需要排序来实现.如果边太多的话会影响效率.

 b.結果不唯一.这也是可能存在相同的加权边引起的.

 c.即使b出现了,最終的图可能不一致.但最小生成树的权和是唯一的.即此算法是稳定的.

 

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics