C# 全点对最短路 · 可复用组件

FloydShortestPath

来自 Unity 工作项目的寻路需求，用预计算支持反复查询距离与路线。

打开交互实验查看源码

技术方向: 图算法 / Unity 组件
设计主张: 用一次预计算，简化反复的距离查询。
关键能力: 全点对最短路
前驱路径还原
无引擎依赖

放大查看

距离矩阵、A → B → C → D 的最短路径与不可达顶点 E。

为实际寻路需求预计算

来自工作中 Unity 游戏项目的实际寻路需求。将经典 Floyd–Warshall 算法实现为轻量 C# 组件，对相对稳定的图一次计算全点对距离，再供业务反复查询距离与还原路线。

技术构成

C#: 计算邻接矩阵对应的距离和前驱。
.NET Standard 2.1: 保持无引擎依赖，方便接入 Unity。
.NET 10 Console: 输出路径矩阵与可运行边界检查。

设计与实现

用预处理换反复查询

距离与路线一起保留: O(V³) 时间、O(V²) 空间预处理后，O(1) 读取距离，O(L) 还原长度为 L 的路线。
为稳定图取舍: 适合规模可控的稳定图、多次查询；路网频繁变化或仅查询少量路径时，应比较按需搜索。

画面与演示说明

截图是原控制台输出的阅读报告；该组件负责图上路径计算，不包含完整的 Unity 导航系统。

快速开始

运行控制台示例

准备 .NET 10 SDK，在仓库根目录运行示例，查看距离矩阵与多跳路径。

dotnet run --project examples/ConsoleDemo

计算一条路径

邻接矩阵对角线为 0，无边为 float.PositiveInfinity；前驱表记录终点的前一个顶点。

float inf = float.PositiveInfinity;
float[,] graph = { { 0, 3, 10 }, { inf, 0, 2 }, { inf, inf, 0 } };
var (predecessors, distances) = FloydShortestPath.Compute(graph);
int[] route = FloydShortestPath.GetPath(predecessors, 0, 2); // 0, 1, 2
float distance = distances[0, 2]; // 5

全部工程