第三章 路径分析算法——基于Floyd算法的路径分析
发布网友
发布时间：2022-11-22 03:47
共1个回答
热心网友
时间：2024-06-03 23:12
Floyd作为一种典型的求多源最短路径问题的算法，是解决任意两个点之间最短路径的算法，它的思想是基于动态规划的思想。
见——第一章 算法基础——基础算法分析类型。
Floyd的核心思想也是基于动态规划的理论，过程也比较简单。
设 表示为i点到j点过程中以(1…k)集合中的节点为中间节点的最短路径长度，则：
（1）若最短路径经过点k，则 = + ;
（2）若最短路径不经过点k，则 = 。
于是 = .
Floyd算法的时间复杂度为 ，空间复杂度为 。
热心网友
时间：2024-06-03 23:12
Floyd作为一种典型的求多源最短路径问题的算法，是解决任意两个点之间最短路径的算法，它的思想是基于动态规划的思想。
见——第一章 算法基础——基础算法分析类型。
Floyd的核心思想也是基于动态规划的理论，过程也比较简单。
设 表示为i点到j点过程中以(1…k)集合中的节点为中间节点的最短路径长度，则：
（1）若最短路径经过点k，则 = + ;
（2）若最短路径不经过点k，则 = 。
于是 = .
Floyd算法的时间复杂度为 ，空间复杂度为 。
