26考研408Floyd算法手算

Floyd算法，用于计算加权图中所有顶点对之间的最短路径，是一种基于动态规划的方法。手算Floyd算法时，应遵循以下步骤，以确保正确计算任意两点间的最短路径：1、初始化 – 创建一个n×n的矩阵D，其中n是顶点的数量。 – D[i][j]的初始值为两顶点i和j之间的直接边权重，如果i和j之间没有直接连接，则设为正无穷大（通常用一个足够大的数表示）。 – 对角线上的元素D[i][i]应为0，表示从一个顶点到自身的距离为0。 – 另外，可以初始化一个辅助矩阵P，用于记录最短路径的前驱节点，这对于之后重建路径非常有用 2. 插入中间点 – 通过三层嵌套循环进行计算，外层循环k遍历所有可能的中间点（0到n-1），中层循环i遍历起始顶点，内层循环j遍历目标顶点。 – 对于每一对(i, j)，检查是否通过插入顶点k能缩短i到j的距离：如果D[i][k] + D[k][j] < D[i][j]，则更新D[i][j]为这个更短的距离，并在P矩阵中记录k作为i到j的最短路径中的前驱节点。 3. 状态转移方程 – 核心更新公式：`if (D[i][j] > D[i][k] + D[k][j]) { D[i][j] = D[i][k] + D[k][j]; P[i][j] = k; }`  4. 手算示例，假设有一个简单的图，你需要手动填写初始邻接矩阵，然后逐步按照k的值（从0到n-1）更新矩阵D，直到完成所有计算。 5. 计算最短路径 – 完成所有迭代后，D矩阵将包含所有顶点对之间的最短路径长度。 – 若要找出实际路径，可以从终点开始，使用P矩阵回溯到起点，找到经过的中间点序列。  6. 注意事项 – 在手算过程中，确保每次更新都检查是否真的通过添加k作为中转点能够减少距离。 – 对于稠密图，Floyd算法效率较高，但对于稀疏图，Dijkstra算法或Bellman-Ford算法可能更合适。  通过以上步骤，可以手动计算出给定图中任意两点间的最短路径长度，并且如果需要，还可以重建这些路径。手算练习时，选择一个小图开始，逐步增加复杂度，以加深理解。

文档的预览图如下，需要完整PDF文件的同学，文末有文档编码，保存后即可直接打印使用。

文档预览：

 

 

📚 408必考算法 | Floyd最短路径手算全攻略 ✨  

📍 Floyd算法核心思想

✅ 动态规划：通过中间点逐步优化所有顶点间的最短路径  

✅ 邻接矩阵：初始化为边的权值（无连接=∞）  

✅ 三重循环：  

plaintext

for k in 顶点:  

    for i in 顶点:  

        for j in 顶点:  

            if D[i][j] > D[i][k] + D[k][j]:  

                更新D[i][j]

🔥 手算四步法（真题例题） 

题目：求有向图的最短路径矩阵（邻接矩阵如下）  

|       | V₁ | V₂ | V₃ | V₄ |  

|——-|—-|—-|—-|—-|  

| V₁| 0  | 5  | ∞  | 7  |  

| V₂| 3  | 0  | 2  | ∞  |  

| V₃ | ∞  | 1  | 0  | 4  |  

| V₄ | ∞  | ∞  | 1  | 0  |  

Step 1：初始化 

直接填写邻接矩阵（对角线为0，无路径为∞）  

Step 2：十字更新法

1️⃣ 选中间点k（如V₁）：画V₁行和V₁列的十字线  

2️⃣ 更新非十字元素：  

   – 计算 D[i][j] vs D[i][k]+D[k][j]

   – 例：D[V₂][V₄] = ∞ > D[V₂][V₁]+D[V₁][V₄] = 3+7=10 → 更新为10  

Step 3：遍历所有中间点

重复Step 2，依次选V₂、V₃、V₄为中间点更新矩阵  

Step 4：最终结果

|       | V₁ | V₂ | V₃ | V₄ |  

|——-|—-|—-|—-|—-|  

| **V₁** | 0  | 5  | 7  | 7  |  

| **V₂** | 3  | 0  | 2  | 6  |  

| **V₃** | 4  | 1  | 0  | 4  |  

| **V₄** | 5  | 2  | 1  | 0  |  

💡 速记技巧  

1️⃣ 十字法：聚焦中间点所在行/列，快速定位需比较的元素  

2️⃣ 更新条件：仅当 D[i][k]+D[k][j] < D[i][j]时更新  

3️⃣ 真题标志：题目出现“所有顶点最短路径”必选Floyd！  

网盘链接：