MENU

Prim算法(1)

一:背景

假设要在n个城市之间通信联络网,则连通n个城市只需要n-1条线路。这时,自然会考虑这样一个问题,如何在最节省经费的前提下建立这个通信网。

上面的这个问题,就是最小生成树的问题。这篇文章就来介绍下解决这一问题的Prim算法(普里姆算法),该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克发现,并在1957年由美国计算机科学家罗伯特·普里姆独立发现,1959年,艾兹格·迪科斯彻再次发现了该算法。因此,在某些场合,普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆-亚尔尼克算法。

阅读全文

单源最短路径(3):SPFA算法

系列文章目录

单源最短路径(1):Dijkstra算法
单源最短路径(2):Bellman_Ford算法
单源最短路径(3):SPFA算法
单源最短路径(4):总结

一:背景

SPFA(Shortest Path Faster Algorithm)算法,是西南交通大学段凡丁于1994年发表的,其在Bellman-ford算法的基础上加上一个队列优化,减少了冗余的松弛操作,是一种高效的最短路算法。




阅读全文

单源最短路径(2):Bellman-Ford算法

系列文章目录

单源最短路径(1):Dijkstra算法
单源最短路径(2):Bellman_Ford算法
单源最短路径(3):SPFA算法
单源最短路径(4):总结

一:背景

Dijkstra算法是处理单源最短路径的有效算法,但它对存在负权回路的图就会失效。这时候,就需要使用其他的算法来应对这个问题,Bellman-Ford(中文名:贝尔曼-福特)算法就是其中一个。

Bellman-Ford算法不仅可以求出最短路径,也可以检测负权回路的问题。该算法由美国数学家理查德•贝尔曼(Richard Bellman, 动态规划的提出者)和小莱斯特•福特(Lester Ford)发明。




阅读全文

单源最短路径(1):Dijkstra算法

系列文章目录

单源最短路径(1):Dijkstra算法
单源最短路径(2):Bellman_Ford算法
单源最短路径(3):SPFA算法
单源最短路径(4):总结

一:背景

Dijkstra算法(中文名:迪杰斯特拉算法)是由荷兰计算机科学家Edsger Wybe Dijkstra提出。该算法常用于路由算法或者作为其他图算法的一个子模块。举例来说,如果图中的顶点表示城市,而边上的权重表示城市间开车行经的距离,该算法可以用来找到两个城市之间的最短路径。




阅读全文

Title - Artist
0:00