用C++手把手实现Dijkstra算法：从邻接矩阵到最短路径的完整代码解析
用C++手把手实现Dijkstra算法：从邻接矩阵到最短路径的完整代码解析
当你第一次在地图应用中输入起点和终点，瞬间计算出最优路线时，背后很可能就运行着Dijkstra算法。这个诞生于1956年的经典算法，至今仍是解决单源最短路径问题的黄金标准。本文将带你从零开始，用C++完整实现一个带邻接矩阵的Dijkstra算法，不仅理解其原理，更能亲手写出工业级可运行的代码。
1. 邻接矩阵：图的数字化表达
邻接矩阵是图论中最直观的存储方式之一。假设我们有一个包含4个城市（A、B、C、D）的交通网，用矩阵表示如下：
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 3 | ∞ | 7 |
| B | 3 | 0 | 2 | ∞ |
| C | ∞ | 2 | 0 | 1 |
| D | 7 | ∞ | 1 | 0 |
在C++中，我们可以用二维数组来实现这个结构。先定义图的基本框架：
#define MAX_VERTEX 100 // 最大顶点数 #define INF 0x3f3f3f3f // 表示无穷大 struct Graph { char vertex[MAX_VERTEX]; // 顶点集合 int matrix[MAX_VERTEX][MAX_VERTEX]; // 邻接矩阵 int vertexNum, edgeNum; // 当前顶点数和边数 };初始化矩阵时，需要特别注意对角线和不可达边的处理：
void initGraph(Graph &G) { for(int i=0; i<MAX_VERTEX; ++i) { for(int j=0; j<MAX_VERTEX; ++j) { G.matrix[i][j] = (i == j) ? 0 : INF; } } }2. Dijkstra算法的核心实现
Dijkstra算法的精妙之处在于它如何逐步"探索"图中的节点。想象你是一位城市规划师，正在逐步绘制从市中心到各区域的最短路线图。
2.1 关键数据结构
算法需要维护三个核心数组：
- dist[]：记录源点到各顶点的当前最短距离
- visited[]：标记顶点是否已确定最短路径
- path[]：记录路径上的前驱节点
void dijkstra(const Graph &G, int src) { int dist[MAX_VERTEX]; bool visited[MAX_VERTEX] = {false}; int path[MAX_VERTEX]; // 初始化 for(int i=0; i<G.vertexNum; ++i) { dist[i] = G.matrix[src][i]; path[i] = (dist[i] != INF) ? src : -1; } visited[src] = true; dist[src] = 0; // 主循环 for(int i=1; i<G.vertexNum; ++i) { int minDist = INF; int u = src; // 找出未访问节点中的最近节点 for(int j=0; j<G.vertexNum; ++j) { if(!visited[j] && dist[j] < minDist) { minDist = dist[j]; u = j; } } visited[u] = true; // 松弛操作 for(int v=0; v<G.vertexNum; ++v) { if(!visited[v] && G.matrix[u][v] != INF) { if(dist[u] + G.matrix[u][v] < dist[v]) { dist[v] = dist[u] + G.matrix[u][v]; path[v] = u; } } } } }2.2 算法复杂度分析
Dijkstra算法的时间复杂度主要取决于如何实现最小距离节点的查找：
| 实现方式 | 时间复杂度 | 适用场景 |
|---|---|---|
| 数组遍历 | O(V²) | 稠密图 |
| 最小堆 | O(E + VlogV) | 稀疏图 |
| 斐波那契堆 | O(E + VlogV) | 理论最优 |
我们的实现采用了最简单的数组遍历方式，适合教学目的。在实际工程中，根据图的特点可以选择更高效的实现。
3. 路径重建与输出
计算出最短距离后，我们还需要展示具体的路径。这需要用到之前记录的path数组：
void printPath(const Graph &G, const int path[], int dest) { if(path[dest] == -1) { cout << G.vertex[dest]; return; } printPath(G, path, path[dest]); cout << " -> " << G.vertex[dest]; }这个递归函数会从终点回溯到起点，然后正向输出路径。例如对于路径A→B→C→D，实际存储是：
path[D] = C path[C] = B path[B] = A4. 完整可运行示例
让我们用一个实际的交通网络测试我们的实现。假设有以下城市和路线：
城市：A B C D E 路线： A B 5 A C 2 B D 4 C B 1 C D 6 D E 3完整的主函数实现如下：
int main() { Graph G; initGraph(G); cout << "输入顶点数和边数："; cin >> G.vertexNum >> G.edgeNum; cout << "输入顶点名称："; for(int i=0; i<G.vertexNum; ++i) { cin >> G.vertex[i]; } cout << "输入边（起点 终点 权重）：" << endl; for(int i=0; i<G.edgeNum; ++i) { char u, v; int w; cin >> u >> v >> w; int ui = findVertexIndex(G, u); int vi = findVertexIndex(G, v); G.matrix[ui][vi] = w; } cout << "输入起点："; char start; cin >> start; int src = findVertexIndex(G, start); dijkstra(G, src); cout << "最短路径结果：" << endl; for(int i=0; i<G.vertexNum; ++i) { if(i != src) { cout << start << "到" << G.vertex[i] << "的最短距离：" << dist[i]; cout << "，路径："; printPath(G, path, i); cout << endl; } } return 0; }运行这个程序，输入上述测试数据，你将得到类似如下的输出：
A到B的最短距离：3，路径：A -> C -> B A到C的最短距离：2，路径：A -> C A到D的最短距离：7，路径：A -> C -> B -> D A到E的最短距离：10，路径：A -> C -> B -> D -> E5. 常见问题与优化技巧
在实际编码过程中，你可能会遇到以下典型问题：
负权边处理：Dijkstra算法不能处理含负权边的图。如果图中存在负权边，应该改用Bellman-Ford算法。
堆优化实现：当图的规模较大时，可以使用优先队列来优化查找最小距离节点的过程：
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; pq.push({0, src}); while(!pq.empty()) { auto [dist_u, u] = pq.top(); pq.pop(); if(visited[u]) continue; visited[u] = true; for(int v=0; v<G.vertexNum; ++v) { if(G.matrix[u][v] != INF) { if(dist[u] + G.matrix[u][v] < dist[v]) { dist[v] = dist[u] + G.matrix[u][v]; path[v] = u; pq.push({dist[v], v}); } } } }路径记录优化：当只需要计算特定两点间的最短路径时，可以在确定目标节点的最短路径后提前终止算法。
内存优化：对于超大图，邻接矩阵可能占用过多内存，此时可考虑改用邻接表存储结构。