关于图的常用算法——Dijkstra单源最短路径、Floyd多源最短路径、Prim和Kruskal最小生成树算法

时间:2021-12-20 21:34:36

Dijkstra最短路径算法是计算某一点到其它点的最短距离的算法。

关于图的常用算法——Dijkstra单源最短路径、Floyd多源最短路径、Prim和Kruskal最小生成树算法


Floyd算法是用来计算图中所有点之间的最短距离,它是精妙的动态规划算法,具体可参考:http://developer.51cto.com/art/201403/433874.htm

关于图的常用算法——Dijkstra单源最短路径、Floyd多源最短路径、Prim和Kruskal最小生成树算法

最小生成树(Minimium Spanning Tree)

如果要在N个城市中铺设网络,每个城市之间的网络建设成本不同,如何找到一个建设方案,使得所有城市能够连通,并且总建设成本最低?这就是最小生成树问题。

最小生成树描详见:https://zh.wikipedia.org/wiki/%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91

最小生成树有两个基本算法:Kruskal和Prim算法。

Kruskal算法是不断选取最短的边加入到点集中,最终是点集全连通。

Prim算法有点类似Dijkstra算法(参考http://www.lai18.com/content/1491510.html),从任意一点出发,选取该点最短的一条边,将对端加入到当前点集,然后再当前点集中再选取最短的一条边,将对端加入到当前点集,如此类推直至全部点集加入到当前点集。

关于图的常用算法——Dijkstra单源最短路径、Floyd多源最短路径、Prim和Kruskal最小生成树算法