图的四种最短路径算法的Matlab源码「肥波猫」

本文总结了图的几种最短路径算法的实现：深度或广度优先搜索算法，弗洛伊德算法，迪杰斯特拉算法，Bellman-Ford算法。

1）深度或广度优先搜索算法（解决单源最短路径）

从起始结点开始访问所有的深度遍历路径或广度优先路径，则到达终点结点的路径有多条，取其中路径权值最短的一条则为最短路径。

2）弗洛伊德算法（解决多源最短路径）：时间复杂度O(n^3),空间复杂度O(n^2)

基本思想：最开始只允许经过1号顶点进行中转，接下来只允许经过1号和2号顶点进行中转......允许经过1~n号所有顶点进行中转，来不断动态更新任意两点之间的最短路程。即求从i号顶点到j号顶点只经过前k号点的最短路程。

3）迪杰斯特拉算法（解决单源最短路径）

基本思想：每次找到离源点（如1号结点）最近的一个顶点，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径。

4）Bellman-Ford算法(解决负权边，解决单源最短路径，前几种方法不能求含负权边的图)：：时间复杂度O(nm),空间复杂度O(m)

相关文章为

基于遗传算法求解函数的最大最小值的Matlab源码「肥波猫」

基于蚁群算法求解函数的最大最小值的Matlab源码「肥波猫」

%%欢迎与【肥波猫feibomao@qq.com】%一起免费讨论matlab相关的知识

%如需类似完整源码，请私信头条号肥波猫

%如需系统学习matlab编程，推荐下面这本经典书籍。