游戏算法-Floyd搜索算法知识梳理和通用框架

type

status

date

slug

summary

Floyd搜索算法知识梳理

1. Floyd算法的特点

多源最短路径：一次性计算所有节点之间的最短路径。

动态规划思想：通过逐步优化子问题的解来构建全局解。

负权边处理：能够处理带负权边的图（但不能处理负权环）。

2. Floyd算法的核心思想

Floyd算法基于以下递推关系：设d[i][j]表示从节点i到节点j的最短距离，对于每个中间节点k，检查是否存在通过k的路径比已知路径更短：d[i][j] = min(d[i][j], d[i][k] + d[k][j])。

2.1 Floyd算法步骤

初始化距离矩阵 D，其中 D[i][j] 表示 i 到 j 的直接距离（无边则 ∞）。

对每个中间节点 k，更新所有 (ij) 的距离：D[i][j]=min(D[i][j],D[i][k]+D[k][j])。

检查负权环（可选）：

如果存在 D[i][i]<0，说明节点 i 在一个负权环上。

3. Floyd算法和其他算法对比

特性	Dijkstra算法	*A算法**	Floyd算法
算法类型	单源最短路径	单源最短路径	多源最短路径
启发式使用	无	需要启发函数h(n)	无
数据结构	优先队列	优先队列	邻接矩阵
最优性	保证最优解	保证最优解（h(n)可采纳）	保证最优解
负权边处理	不能处理	不能处理	可以处理（无负权环）
时间复杂度	O((V+E)logV)	O(b^d)	O(V³)
空间复杂度	O(V)	O(b^d)	O(V²)

3.1 各搜索算法典型应用场景

Dijkstra最佳适用：

单次单源最短路径查询
OSPF网络路由协议
权值非负的图结构

A*最佳适用：

已知目标位置的路径规划
游戏AI寻路
地图导航系统
存在良好启发函数的场景

Floyd最佳适用：

需要频繁查询任意两点间最短路径
小型或中等规模图的预计算
包含负权边（无负权环）的图

3.2 Bellman-Ford算法

🐈

Floyd算法和Bellman-Ford算法的本质相同，都是基于动态规划（DP）的最短路径算法，核心思想都是通过逐步松弛（relaxation）来优化路径：Bellman-Ford算法是Floyd算法的单源特例；Floyd算法是Bellman-Ford算法的全源版本。

核心思想

单源最短路径：计算从一个起点到所有其他节点的最短路径。

动态松弛（Relaxation）：通过多次遍历所有边，逐步优化路径估计。

支持负权边：可以处理带负权的图，并能检测负权环（如果存在）。

算法步骤

初始化：起点距离设为 0，其他节点距离设为 ∞。

进行 V−1 次松弛操作（V 是节点数）：

对每条边(uv)，检查是否能通过 u 缩短 v 的距离：d[v] = min(d[v], d[u]+w(u,v))。

检查负权环（可选）：

再进行一次松弛，如果还能优化，说明存在负权环。

时间复杂度

O(VE)（V 是节点数，E 是边数）。

适用场景

单源最短路径（如 RIP 路由协议）。

可以处理负权边，并能检测负权环。

适合分布式计算（如 RIP 协议中路由器只和邻居交换信息）。

Floyd搜索算法通用框架

节点接口

任意类通过继承此接口，成为Floyd算法中的可搜索节点。

关键方法

GetDistance(T otherNode, object nodeMap)

用途：计算到目标节点的实际距离（从地图数据中获取）。

参数：

otherNode - 目标节点
nodeMap - 包含节点连接信息的图结构

返回：两节点间的实际距离

GetSuccessors(object nodeMap)

用途：获取所有直接相连的邻居节点。

参数：nodeMap - 寻路所在的图结构

返回：邻居节点列表

Equals(T other)

用途：判断节点是否相等（用于字典和集合操作）

IFloydNode<T>接口

搜索器

实现Floyd-Warshall算法，用于计算图中所有节点对之间的最短路径。

泛型约束

泛型参数	约束条件	作用
`T_Map`	无	表示搜索空间（地图）。
`T_Node`	`IFloydNode<T_Node>`	表示搜索节点，需实现节点接口。

核心成员

成员	类型	作用
`nodeMap`	`T_Map`	搜索空间（地图）。
`distanceMatrix`	`float[,]`	存储所有节点对之间的最短距离。
`nextMatrix`	`int[,]`	存储路径重建信息。
`nodeList`	`List<T_Node>`	节点列表。
`isCalculated`	`bool`	标记是否已完成计算。

关键方法

CalculateAllPairsShortestPaths()

用途：执行Floyd算法核心计算，填充距离矩阵和路径矩阵；只需调用一次，后续查询直接使用计算结果。

GetShortestDistance(T_Node from, T_Node to)

用途：获取两节点间的最短距离。

参数：

from - 起始节点
to - 目标节点

返回：最短距离，若无路径返回float.PositiveInfinity

GetShortestPath(T_Node from, T_Node to)

用途：获取两节点间的最短路径。

参数：

from - 起始节点
to - 目标节点

返回：路径节点列表（按顺序从起点到终点），若无路径返回空列表

HasNegativeCycle()

用途：检查图中是否存在负权环。

返回：存在负权环返回true

FloydSearcher<T_Map, T_Node>类

框架使用示例

节点（CityNode）

CityNode类实现了IFloydNode<CityNode>接口，并重写了必要的方法。

关键方法实现

方法	说明
`GetDistance`	从图结构中查询两城市间的实际道路距离：1.使用`MyGraph.FindEdge`获取连接道路；2.返回最短道路的距离，若无连接返回`float.PositiveInfinity`
`GetSuccessors`	获取当前城市的所有相邻城市• 使用`MyGraph.GetNeighbor`获取邻居列表
`Equals`	通过城市名称判断节点相等性
`ToString`	返回城市名称便于调试输出

图（MyGraph）

MyGraph<TNode, TEdge>类提供图的存储和基本操作功能。

核心成员

成员	类型	说明
`NodeSet`	`HashSet<TNode>`	存储所有节点
`NeighborList`	`Dictionary<TNode, List<TNode>>`	记录每个节点的邻居
`EdgeList`	`Dictionary<(TNode,TNode), List<TEdge>>`	存储节点间的边

核心方法

方法	时间复杂度	说明
`AddNode`	O(1)	添加节点到图中
`AddEdge`	O(1)	添加边到图中（需先添加节点）
`FindEdge`	O(1)	查询两节点间的所有边
`GetNeighbor`	O(1)	获取节点的所有邻居
`RemoveNode`	O(1)	移除节点（会自动移除相关边）
`RemoveEdge`	O(n)	移除特定边

初始化和搜索

下面是一个使用示例：

创建有向图和节点，把节点加入图中

指定节点的连接关系（添加有向边，示例中是双向连接）

创建搜索器实例并执行计算

示例输出：