别再死记硬背了！用C++邻接矩阵手搓Dijkstra算法，我连路径打印都给你讲明白了

从零实现Dijkstra算法：邻接矩阵实战与路径回溯详解

在计算机科学的世界里，寻找两点之间最短路径的问题就像现代都市中的导航系统——我们需要在错综复杂的道路网络中找到最优解。Dijkstra算法作为解决单源最短路径问题的经典方法，其重要性不亚于建筑师手中的水平仪。本文将带您深入算法的实现细节，从邻接矩阵的构建到路径回溯的完整过程，用C++代码揭开这一经典算法的神秘面纱。

1. 算法核心思想与实现准备

Dijkstra算法的精妙之处在于它的贪心策略——每次选择当前已知的最短路径节点进行扩展。想象一下在陌生城市使用地图APP的情景：系统会优先探索从当前位置出发的最近道路，逐步扩大搜索范围，这与Dijkstra的工作方式如出一辙。

关键数据结构准备：

const int INF = INT_MAX; // 表示无穷大的权值 class Graph { private: vector<vector<int>> adjMatrix; // 邻接矩阵存储图结构 vector<string> vertices; // 顶点名称集合 unordered_map<string, int> vertexIndex; // 顶点到索引的映射 public: // 构造函数、添加边等方法后续实现 };

在开始编码前，我们需要明确几个关键点：

• 邻接矩阵中adjMatrix[i][j]存储顶点i到j的边权值
• 使用INF表示两个顶点间没有直接边相连
• 需要维护顶点名称与矩阵索引的双向映射

提示：在实际项目中，建议将INF定义为类静态常量，避免魔法数字的出现。

2. 图的构建与初始化

构建图的邻接矩阵就像绘制城市交通图，需要准确记录每个交叉路口（顶点）之间的道路（边）及其距离（权值）。

完整的图类实现：

class Graph { // ... 其他成员同上 public: Graph(const vector<string>& nodes) { int n = nodes.size(); vertices = nodes; adjMatrix.resize(n, vector<int>(n, INF)); for(int i=0; i<n; ++i) { vertexIndex[nodes[i]] = i; adjMatrix[i][i] = 0; // 顶点到自身的距离为0 } } void addEdge(const string& from, const string& to, int weight) { int u = vertexIndex[from]; int v = vertexIndex[to]; adjMatrix[u][v] = weight; } int getVertexIndex(const string& node) const { return vertexIndex.at(node); } };

初始化示例：

vector<string> cities = {"北京", "上海", "广州", "深圳"}; Graph cityGraph(cities); cityGraph.addEdge("北京", "上海", 100); cityGraph.addEdge("上海", "广州", 200); cityGraph.addEdge("广州", "深圳", 50);

3. Dijkstra算法核心实现

算法实现如同精心编排的舞蹈，每个步骤都需要精确配合。我们将使用三个关键数组：

• dist: 记录源点到各顶点的最短距离
• visited: 标记顶点是否已确定最短路径
• prev: 记录路径上前驱节点，用于最终路径回溯

完整算法实现：

void Graph::dijkstra(const string& start) { int src = getVertexIndex(start); int n = vertices.size(); vector<int> dist(n, INF); vector<bool> visited(n, false); vector<int> prev(n, -1); dist[src] = 0; for(int i=0; i<n; ++i) { // 找出未访问节点中距离最小的 int u = -1; int minDist = INF; for(int j=0; j<n; ++j) { if(!visited[j] && dist[j] < minDist) { u = j; minDist = dist[j]; } } if(u == -1) break; // 所有可达节点已处理 visited[u] = true; // 更新邻接节点距离 for(int v=0; v<n; ++v) { if(!visited[v] && adjMatrix[u][v] != INF) { int newDist = dist[u] + adjMatrix[u][v]; if(newDist < dist[v]) { dist[v] = newDist; prev[v] = u; } } } } // 存储结果供后续使用 this->distances = dist; this->predecessors = prev; }

时间复杂度分析：

4. 路径回溯与结果展示

获取最短路径就像解开一团毛线——我们需要从终点逆向追溯到起点。以下是路径回溯的实现方法：

路径打印实现：

void Graph::printPath(const string& end) { int target = getVertexIndex(end); if(distances[target] == INF) { cout << "无可达路径" << endl; return; } vector<string> path; for(int v = target; v != -1; v = predecessors[v]) { path.push_back(vertices[v]); } reverse(path.begin(), path.end()); cout << "最短路径: "; for(size_t i=0; i<path.size(); ++i) { if(i != 0) cout << " -> "; cout << path[i]; } cout << "\n总距离: " << distances[target] << endl; }

调试技巧：

1. 在算法关键步骤后插入打印语句，观察数组变化
2. 对小规模图进行手动演算，验证程序输出
3. 使用调试器逐步执行，检查变量状态

// 示例调试输出 cout << "当前处理节点: " << vertices[u] << endl; cout << "距离数组: "; for(int d : dist) cout << (d==INF ? "∞" : to_string(d)) << " "; cout << endl;

5. 算法局限性与实际应用

虽然Dijkstra算法强大，但它并非万能钥匙。当图中存在负权边时，就像交通系统中出现了"付费捷径"，算法可能给出错误结果。

典型应用场景：

• 路由器的网络数据包转发路径计算
• 社交网络中的人际关系距离分析
• 游戏AI中的寻路算法
• 交通导航系统中的最优路线规划

常见问题排查表：

在实际项目中使用Dijkstra算法时，我曾遇到一个有趣的情况：当处理大规模稀疏图时，基础的邻接矩阵实现会导致性能瓶颈。这时改用邻接表配合优先队列的实现方式，执行效率提升了近10倍。这提醒我们，算法实现需要根据具体场景灵活调整。