C++怎么用邻接矩阵实现Dijkstra最短路径算法

Dijkstra算法用于计算图中某个顶点到其他所有顶点的最短路径，核心思路是每次从尚未确定最短路径的顶点中，选择距离源点最近的顶点，标记为已确定，再用该顶点去更新其他顶点的距离。邻接矩阵是用二维数组存储图中边的关系，适合顶点数较少的场景，实现起来逻辑清晰。

Dijkstra算法核心原理

算法执行过程主要分为几个步骤：首先初始化所有顶点到源点的距离为无穷大，源点自身距离为0，同时维护一个标记数组记录顶点是否已经确定最短路径。接着每次循环找到未标记顶点中距离最小的那个，将其标记为已确定，然后遍历该顶点的所有邻接顶点，如果通过当前顶点到达邻接顶点的距离比已有的距离更短，就更新邻接顶点的距离值。重复这个过程直到所有顶点都被标记，最终得到源点到所有顶点的最短距离。

邻接矩阵存储图结构

邻接矩阵的本质是一个二维数组，假设图有n个顶点，那么二维数组的大小为n*n。如果顶点i到顶点j之间有边，且边的权重为w，那么矩阵中第i行第j列的值就设为w；如果没有边，通常设为无穷大，对角线元素设为0表示顶点到自身的距离为0。这里我们用C++的vector来定义邻接矩阵，方便动态指定顶点数量。

邻接矩阵初始化示例

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

// 定义无穷大，用int的最大值表示
const int INF = INT_MAX;

// 初始化邻接矩阵，n为顶点数量
vector<vector<int>> initGraph(int n) {
    // 创建n行n列的二维数组，初始值都为INF
    vector<vector<int>> graph(n, vector<int>(n, INF));
    // 顶点到自身的距离为0
    for (int i = 0; i < n; i++) {
        graph[i][i] = 0;
    }
    return graph;
}

C++实现Dijkstra算法完整代码

下面的代码实现了基于邻接矩阵的Dijkstra算法，包含图的构建、算法执行和结果输出三个部分，代码中加入了详细注释方便理解逻辑。

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

const int INF = INT_MAX;

// Dijkstra算法实现，graph是邻接矩阵，start是源点下标
vector<int> dijkstra(vector<vector<int>>& graph, int start) {
    int n = graph.size();
    // 存储源点到每个顶点的最短距离
    vector<int> dist(n, INF);
    // 标记顶点是否已经确定最短路径
    vector<bool> visited(n, false);
    
    // 源点到自身的距离为0
    dist[start] = 0;
    
    // 循环n次，每次确定一个顶点的最短路径
    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) {
                minDist = dist[j];
                u = j;
            }
        }
        
        // 如果所有未访问顶点距离都是INF，说明剩下的顶点不可达，直接退出
        if (u == -1) {
            break;
        }
        
        // 标记该顶点为已访问
        visited[u] = true;
        
        // 用当前顶点更新其他未访问顶点的距离
        for (int v = 0; v < n; v++) {
            // 如果u到v有边，且通过u到达v的距离更短，就更新dist[v]
            if (graph[u][v] != INF && !visited[v]) {
                if (dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                }
            }
        }
    }
    
    return dist;
}

int main() {
    // 定义图的顶点数量，这里以5个顶点为例
    int n = 5;
    vector<vector<int>> graph = initGraph(n);
    
    // 添加图的边，这里构建无向图，有向图只需要加单边即可
    graph[0][1] = 10;
    graph[0][2] = 3;
    graph[1][2] = 1;
    graph[1][3] = 2;
    graph[2][1] = 4;
    graph[2][3] = 8;
    graph[2][4] = 2;
    graph[3][4] = 7;
    graph[4][3] = 4;
    
    // 以顶点0为源点执行Dijkstra算法
    int start = 0;
    vector<int> shortestDist = dijkstra(graph, start);
    
    // 输出结果
    cout << "源点" << start << "到各顶点的最短距离：" << endl;
    for (int i = 0; i < n; i++) {
        if (shortestDist[i] == INF) {
            cout << "顶点" << i << ": 不可达" << endl;
        } else {
            cout << "顶点" << i << ": " << shortestDist[i] << endl;
        }
    }
    
    return 0;
}

算法复杂度与适用场景

基于邻接矩阵的Dijkstra算法，每次选择最小距离顶点需要遍历所有顶点，更新距离也需要遍历所有顶点，因此总时间复杂度为O(n²)，其中n是图的顶点数量。这种实现方式适合顶点数量在几千以内、边比较密集的场景，如果顶点数量很多且边比较稀疏，邻接矩阵的存储会浪费大量空间，此时更适合用邻接表存储图，再配合优先队列优化Dijkstra算法，时间复杂度可以降到O((n+m)logn)，m是边的数量。

常见实现误区

• 忘记初始化邻接矩阵的对角线为0，会导致顶点到自身的距离计算错误
• 更新距离时没有判断邻接顶点是否已经被标记，虽然不影响结果正确性，但会做无用计算
• 用INT_MAX表示无穷大时，两个无穷大相加会导致整数溢出，因此更新距离前要先判断dist[u]是否为INF
• 混淆有向图和无向图的边添加逻辑，无向图需要添加双向边，有向图只需要添加单向边

C++Dijkstra算法邻接矩阵最短路径图论修改时间：2026-06-27 17:48:31