深入理解 Dijkstra 算法：如何追踪并打印最短路径

2026-02-08 15:09:21 0条评论 1次阅读 0人点赞

在图论的广阔天地中，Dijkstra 算法无疑是一颗璀璨的明珠，它帮助我们高效地解决从一个起点到其他所有节点的最短路径问题。在之前的探索中，你可能已经学会了如何计算这些最短距离的数值——也就是那个代表了“权值之和”的数字。然而，在实际的软件开发和工程实践中，仅仅知道“距离”往往是不够的。

想象一下，你正在为地图导航应用编写核心逻辑。用户不仅想知道从家到公司需要“15公里”，他们更迫切需要知道的是具体的路线：“先左转，再直走，经过第三个红绿灯…”。同样，在网络路由协议中，路由器也需要知道数据包应该转发到下一个节点是谁。

在这篇文章中，我们将不仅回顾经典算法，更重要的是，我们将一起深入探讨如何追踪并打印出从源点到图中每个顶点的具体最短路径。我们将通过通俗易懂的分析、详细的代码实现以及实际应用场景的探讨，让你彻底掌握这一技术。

1. 核心思路：引入“父节点”的概念

标准的 Dijkstra 算法使用一个 INLINECODEde56c8b9 数组来存储从源点到各个点的最短距离。为了能够还原出路径，我们需要引入一个新的数组，我们称之为 INLINECODE9b84e208（父节点数组）。

它的作用是什么？

对于图中的任意一个顶点 INLINECODE62a5ce2a（除了源点本身），INLINECODE27ee7535 存储的是在最短路径树中，v 的前驱节点（即它是从哪个节点走过来的）。这就好比我们要还原一个人回家的路，只需要问他：“你上一站在哪？”然后不断向前追问，直到问到起点（源点）为止。

具体操作流程：

  • 初始化：在算法开始时，我们将所有顶点的父节点设为 -1（表示未连接或未知）。源点的父节点通常保持为 -1，因为它就是起点。
  • 松弛操作时更新：这是最关键的一步。在标准的 Dijkstra 算法中，当我们尝试通过顶点 INLINECODE59753df8 去更新顶点 INLINECODE703d6213 的距离时（即 INLINECODEaa745bab），如果我们发现了一条更短的路径，我们不仅更新 INLINECODEa913a591，还要将 INLINECODE4b97bcaf 设置为 INLINECODEadad032d。这意味着“目前看来，到达 INLINECODE03dff10a 的最好方式是经过 INLINECODE9c4b18d8”。

2. 递归回溯：从终点走到起点

当我们完成了 Dijkstra 算法的计算，INLINECODEdfd37b27 数组就已经构建出了一棵“最短路径树”。现在，如果我们想打印从源点 INLINECODE8c3e61bf 到目标点 v 的路径，该怎么办呢？

虽然路径是从 INLINECODEa2857577 走到 INLINECODE6690bc1d，但在数据结构中，INLINECODE583447fa 只记录了它的上一站。因此，我们需要使用递归的方法，从 INLINECODE3a8ba2c6 开始反向回溯到 s，然后在回溯返回的过程中打印节点，这样就能得到正序的路径。

#### 示例：打印路径的递归函数

让我们先看一段核心的 C++ 代码，它展示了如何利用父节点数组打印路径：

// 这是一个递归辅助函数，用于打印从源点到 currentVertex 的路径
// parents 数组存储了路径信息
void printPath(int currentVertex, vector parents) {
    // 基准情况：如果当前节点没有父节点（即为源点），停止递归
    // NO_PARENT 通常定义为 -1
    if (currentVertex == NO_PARENT) {
        return;
    }
    
    // 递归调用：先去打印父节点的路径
    // 这会一直回溯到源点
    printPath(parents[currentVertex], parents);
    
    // 在递归返回时打印当前节点
    // 利用递归栈的后进先出特性，保证打印顺序是从源点到目标点
    cout << currentVertex << " ";
}

原理解析：

假设路径是 INLINECODE0eeb6894。INLINECODEa9d46dbd, INLINECODEebc2063d, INLINECODE8326f603。

  • 调用 printPath(2)：
  • 发现 INLINECODE7bd48412 是 1，递归调用 INLINECODE220a92c0。
  • 发现 INLINECODE0f020a16 是 0，递归调用 INLINECODEbb22ce06。
  • 发现 parent[0] 是 -1，触发基准情况，返回。
  • 回到 INLINECODEa2c1e972 的层级，打印 INLINECODE90bc8b5f。
  • 回到 INLINECODEb6e8dea5 的层级，打印 INLINECODEfb01950b。
  • 回到 INLINECODEddbd7902 的层级，打印 INLINECODEe574ac1a。
  • 最终输出：0 1 2。完美！

3. 完整实现：Dijkstra 算法与路径打印

为了让你能够直接运行并理解，下面提供了一个完整的 C++ 实现。为了方便你阅读，我在代码中添加了详细的中文注释。这个程序使用邻接矩阵来表示图，因为对于稠密图或者教学示例来说，矩阵形式非常直观。

#### 完整代码示例

#include 
#include 
#include 
#include  // 用于格式化输出

using namespace std;

// 定义一个常量表示没有父节点，即源点的标识
int NO_PARENT = -1;

// 函数声明：打印路径的递归函数
void printPath(int currentVertex, vector parents);

// 辅助函数：打印完整的解决方案（距离和路径）
// startVertex: 源点索引
// distances: 存储最短距离的数组
// parents: 存储父节点的数组
void printSolution(int startVertex, vector distances,
                   vector parents) {
    int nVertices = distances.size();
    
    // 打印表头
    cout << "顶点\t 距离\t\t路径";
    cout << "
----------------------------------------" << endl;

    for (int vertexIndex = 0; vertexIndex < nVertices; vertexIndex++) {
        // 只打印除源点外的其他顶点信息
        if (vertexIndex != startVertex) {
            cout << "
" << startVertex < ";
            cout << vertexIndex << " \t\t ";
            cout << distances[vertexIndex] << "\t\t";
            
            // 调用递归函数打印具体路径
            printPath(vertexIndex, parents);
            cout << endl;
        }
    }
}

// 核心函数：实现 Dijkstra 算法
// adjacencyMatrix: 图的邻接矩阵表示
// startVertex: 开始的顶点
void dijkstra(vector<vector > adjacencyMatrix, int startVertex) {
    int nVertices = adjacencyMatrix[0].size();

    // shortestDistances[i] 将保存从源点到 i 的最短距离
    vector shortestDistances(nVertices);

    // added[i] 为 true 表示顶点 i 已经被处理过（即最短距离已确定）
    vector added(nVertices);

    // 初始化所有距离为无限大（INT_MAX），状态为未处理
    for (int vertexIndex = 0; vertexIndex < nVertices; vertexIndex++) {
        shortestDistances[vertexIndex] = INT_MAX;
        added[vertexIndex] = false;
    }

    // 源点到自身的距离总是 0
    shortestDistances[startVertex] = 0;

    // 父节点数组，用于存储路径结构
    vector parents(nVertices);

    // 源点没有父节点
    parents[startVertex] = NO_PARENT;

    // 主循环：寻找所有 nVertices 个顶点的最短路径
    // 注意：循环实际上只需要执行 nVertices - 1 次，因为最后一次没有未处理的节点了
    for (int i = 1; i < nVertices; i++) {
        
        // 步骤 A：从未处理的顶点中选出距离源点最近的一个
        int nearestVertex = -1;
        int shortestDistance = INT_MAX;
        
        for (int vertexIndex = 0; vertexIndex < nVertices; vertexIndex++) {
            // 如果顶点未处理 且 距离比当前记录的更短
            if (!added[vertexIndex] && 
                shortestDistances[vertexIndex] < shortestDistance) {
                nearestVertex = vertexIndex;
                shortestDistance = shortestDistances[vertexIndex];
            }
        }

        // 将选中的最近顶点标记为已处理
        added[nearestVertex] = true;

        // 步骤 B：更新邻接顶点的距离值（松弛操作）
        // 遍历所有顶点，检查它们是否是 nearestVertex 的邻居
        for (int vertexIndex = 0; vertexIndex  0)
            // 2. 目标顶点未处理 (!added[vertexIndex])
            // 3. 新路径更短 (distance[nearest] + edge  0 && 
                ((shortestDistance + edgeDistance) < shortestDistances[vertexIndex])) {
                
                // 更新距离
                shortestDistances[vertexIndex] = shortestDistance + edgeDistance;
                
                // 【关键点】更新父节点，记录路径来源
                parents[vertexIndex] = nearestVertex;
            }
        }
    }

    // 循环结束后，打印最终结果
    printSolution(startVertex, shortestDistances, parents);
}

// 递归函数实现
void printPath(int currentVertex, vector parents) {
    // 基准情况：如果回溯到了源点（无父节点），则停止
    if (currentVertex == NO_PARENT) {
        return;
    }
    
    // 不断深入查找父节点
    printPath(parents[currentVertex], parents);
    
    // 打印当前节点
    cout << currentVertex << " ";
}

// 主函数：构建图并测试算法
int main() {
    // 示例图的邻接矩阵
    // 0 表示无边，其他数字表示边的权重
    /*
       图示：
          (0)---4---(1)
           | \        |
          1   8       1
           |     \    |
          (7)    11  (2)
           |      \    |
           8      2   7
           |       \  |
          (6)---1---(5)
           |       /   |
           6     7     2
           |   /       |
          (8)---2---(3)
                |
                4
               (4)
    */
    vector<vector > adjacencyMatrix = {
        {0, 4, 0, 0, 0, 0, 0, 8, 0},
        {4, 0, 8, 0, 0, 0, 0, 11, 0},
        {0, 8, 0, 7, 0, 4, 0, 0, 2},
        {0, 0, 7, 0, 9, 14, 0, 0, 0},
        {0, 0, 0, 9, 0, 10, 0, 0, 0},
        {0, 0, 4, 14, 10, 0, 2, 0, 0},
        {0, 0, 0, 0, 0, 2, 0, 1, 6},
        {8, 11, 0, 0, 0, 0, 1, 0, 7},
        {0, 0, 2, 0, 0, 0, 6, 7, 0}
    };

    cout << "正在计算从源点 0 到所有其他顶点的最短路径..." << endl;
    // 以顶点 0 为源点调用 Dijkstra 算法
    dijkstra(adjacencyMatrix, 0);

    return 0;
}

4. 深入解析与实战建议

作为开发者，仅仅会写代码是不够的，我们需要理解算法背后的权衡和潜在的陷阱。

#### 4.1 为什么使用优先队列优化？

在上面的 C++ 示例中，为了逻辑清晰，我们简单地遍历数组来寻找当前距离最小的顶点。这导致总的时间复杂度为 $O(V^2)$，其中 $V$ 是顶点数。这对于小规模数据完全没有问题。但是，当你处理拥有数万个甚至更多节点的网络拓扑图时，这个开销会变得非常巨大。

优化建议： 我们可以使用最小堆或 C++ STL 中的 std::priority_queue 来优化寻找最近顶点的过程。这样做可以将提取最小值的操作降低到 $O(\log V)$。如果使用邻接表存储图，总的时间复杂度可以优化到 $O((V + E) \log V)$，其中 $E$ 是边数。

#### 4.2 如何处理路径中不存在的节点？

在实际应用中，图可能不是完全连通的。如果目标顶点 INLINECODEbec0b3f5 无法从源点 INLINECODE2ebbbd12 到达，INLINECODE0ffe41da 将会保持为 INLINECODE71aabda5（无穷大）。在打印路径时，我们需要检查这种情况。

代码健壮性改进：

在 printSolution 函数中，你可以添加一个检查：

if (distances[vertexIndex] == INT_MAX) {
    cout << "不可达" << endl;
} else {
    // 打印路径
}

#### 4.3 负权边的警告

请务必记住：Dijkstra 算法不能处理带有负权边的图。 这是一个经常在面试中被问到的经典问题。算法基于贪心策略，假设一旦一个节点被标记为“已处理”，其最短距离就已经确定。但如果存在负权边，之前未处理的节点可能通过一条包含负权边的路径，使得已处理节点的距离变得更短，从而破坏了算法的前提。

如果图中可能存在负权边，你需要使用 Bellman-Ford 算法 或 SPFA 算法。

5. 更多应用场景

除了地图导航，掌握 Dijkstra 算法的路径打印还能帮助你解决很多实际问题：

  • 网络路由：OSPF（开放式最短路径优先）协议使用 Dijkstra 的变体来计算数据包在路由器之间的转发路径。
  • 游戏开发：在 RTS（即时战略）或 RPG 游戏中，计算角色自动寻路的路线。
  • 航空调度：计算飞机从城市 A 到城市 B 的最便宜（或最快）的中转路线。

6. 总结

在这篇文章中，我们不仅学习了如何计算最短距离，更掌握了如何利用 parent 数组和递归来精确地重现路径。我们通过一个完整的 C++ 示例，从初始化、松弛操作到最终的递归打印，覆盖了所有的细节。

记住，数据结构是工具，而算法是逻辑。将两者结合，并在适当的场景下进行优化（比如使用优先队列），是成为优秀工程师的关键。希望这篇文章能帮助你更好地理解并应用这一强大的算法。下次当你需要“导航”时，你知道该如何编写代码了！

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。如需转载，请注明文章出处豆丁博客和来源网址。https://shluqu.cn/36307.html
点赞
0.00 平均评分 (0% 分数) - 0 票

相关文章美国1G带宽/1T流量高速vps $17.99/年