第三章 路径分析算法——基于Floyd算法的路径分析
2019-10-18 本文已影响0人
文颜
3.2 基于Floyd算法的路径分析
Floyd算法是一种用于在已知给定的加权图中求多源点之间最短路径的算法。它于Diskstra算法类似，不同点在于Diskstra计算的是单源点之间的最短路径。Floyd算法是在数学建模领域和日常工作中使用频率较高的路径分析算法。
3.2.1 应用示例：任意两个城市之间的最短路径
3.2.2 Floyd原理
Floyd作为一种典型的求多源最短路径问题的算法，是解决任意两个点之间最短路径的算法，它的思想是基于动态规划的思想。
1. 动态规划应用
见——第一章 算法基础——基础算法分析类型。
2. Floyd思想
Floyd的核心思想也是基于动态规划的理论，过程也比较简单。
设表示为i点到j点过程中以(1…k)集合中的节点为中间节点的最短路径长度，则：
（1）若最短路径经过点k，则=
+
;
（2）若最短路径不经过点k，则=
。
于是=
.
Floyd算法的时间复杂度为，空间复杂度为
。
