JsPlumb面试内容整理-状态持久化与数据导出/导入

### Floyd算法概述 Floyd算法，亦被称为插点法，采用动态规划的思想，在给定的加权图中找到多个源点之间的最短路径[^1]。此算法适用于解决任意两点间的最短路径问题（All Pairs Shortest Path），尤其适合稠密图。 ### 算法步骤解析 #### 初始化阶段 创建两个二维数组`map`和`path`用于存储各顶点间距离以及构建最短路径所需的中间节点信息。对于不存在直接连接的情况，默认设置极大值表示不可达状态；而对于自身到自身的距离则初始化为0[^4]。 ```python INF = float('inf') map = [ [0, 3, INF, 7], [8, 0, 2, INF], [5, INF, 0, 1], [2, INF, INF, 0] ] path = [ [-1, -1, -1, -1], [-1, -1, -1, -1], [-1, -1, -1, -1], [-1, -1, -1, -1] ] ``` #### 动态规划过程 遍历每一个可能作为中介点的顶点`k`，再依次考虑每一对起点`i`与终点`j`。如果通过当前考察的中介点`k`能够使从`i`到达`j`的距离变得更短，则更新两者之间的最小距离，并记录下此时所经过的新中介点编号至`path[i][j]`处。 ```python for k in range(len(map)): for i in range(len(map)): for j in range(len(map)): if map[i][j] > map[i][k] + map[k][j]: map[i][j] = map[i][k] + map[k][j] path[i][j] = k ``` 最终形成的`map`矩阵即代表了各个顶点两两之间最短路径长度的结果集，而借助辅助构造出来的`path`表可以帮助追踪具体走过的路线。 ### 流程示意 由于无法直接提供图形化展示，以下是文字描述版本： 1. **输入**：带权重的邻接矩阵形式表达的有向/无向图； 2. **处理**： - 设立初始条件——设定好起始状态下所有结点对之间的估计成本； - 进行迭代优化——尝试引入新的转接站以降低现有已知的最佳行程费用； 3. **输出**：完成后的邻接矩阵包含了所有成对顶点间的最低耗费通路详情。 上述过程中涉及到的具体操作已经在前文中给出Python代码片段予以说明。