c++如何用邻接矩阵和贪心算法实现dijkstra最短路径

Dijkstra算法核心原理

Dijkstra算法是一种用于求解带权有向图或无向图中单源最短路径的贪心算法，核心思想是从起始节点开始，每次选择当前距离起始节点最近的未访问节点，更新该节点相邻节点的最短距离，直到所有节点都被访问或者找到目标节点的最短路径。

算法执行步骤

• 初始化距离数组，起始节点距离设为0，其余节点距离设为无穷大
• 标记所有节点为未访问状态，每次从未访问节点中选择距离最小的节点作为当前节点
• 遍历当前节点的所有邻接节点，计算通过当前节点到达邻接节点的距离，如果该距离小于邻接节点当前记录的距离，则更新邻接节点的距离
• 将当前节点标记为已访问，重复上述选择、更新、标记的步骤，直到所有节点都被访问

邻接矩阵的图存储方式

邻接矩阵是使用二维数组存储图结构的方式，对于包含n个节点的图，用一个n*n的二维数组adj表示，其中adj[i][j]表示节点i到节点j的边的权重，如果两个节点之间没有直接相连的边，通常用一个很大的值表示无穷大，节点自身到自身的距离设为0。

c++完整实现代码

以下是结合邻接矩阵和贪心思想实现的Dijkstra算法完整c++代码，包含图初始化、最短路径计算、结果输出三个部分。

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

// 定义无穷大值，表示两个节点之间没有直接相连的边
const int INF = INT_MAX / 2;

/**
 * 使用邻接矩阵实现Dijkstra最短路径算法
 * @param adj 邻接矩阵，adj[i][j]表示节点i到节点j的边权重
 * @param start 起始节点索引
 * @return 起始节点到所有其他节点的最短距离数组
 */
vector<int> dijkstra(const vector<vector<int>>& adj, int start) {
    int n = adj.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;
            }
        }
        
        // 如果所有未访问节点的距离都是无穷大，说明剩余节点不可达，直接退出循环
        if (u == -1) break;
        
        // 标记当前节点为已访问
        visited[u] = true;
        
        // 遍历当前节点的所有邻接节点，更新最短距离
        for (int v = 0; v < n; v++) {
            // 如果当前节点到v有边，且通过u到达v的距离更短，则更新dist[v]
            if (adj[u][v] != INF && dist[u] + adj[u][v] < dist[v]) {
                dist[v] = dist[u] + adj[u][v];
            }
        }
    }
    
    return dist;
}

int main() {
    // 示例图的节点数量，这里以4个节点为例
    int n = 4;
    // 初始化邻接矩阵，所有边默认设为无穷大
    vector<vector<int>> adj(n, vector<int>(n, INF));
    
    // 节点自身到自身的距离为0
    for (int i = 0; i < n; i++) {
        adj[i][i] = 0;
    }
    
    // 添加图的边，这里构建一个无向带权图
    // 节点0到节点1的边权重为2
    adj[0][1] = 2;
    adj[1][0] = 2;
    // 节点0到节点2的边权重为4
    adj[0][2] = 4;
    adj[2][0] = 4;
    // 节点1到节点2的边权重为1
    adj[1][2] = 1;
    adj[2][1] = 1;
    // 节点1到节点3的边权重为7
    adj[1][3] = 7;
    adj[3][1] = 7;
    // 节点2到节点3的边权重为3
    adj[2][3] = 3;
    adj[3][2] = 3;
    
    int startNode = 0;
    vector<int> shortestDist = dijkstra(adj, startNode);
    
    // 输出起始节点到所有节点的最短距离
    cout << "起始节点" << startNode << "到各节点的最短距离：" << endl;
    for (int i = 0; i < n; i++) {
        if (shortestDist[i] == INF) {
            cout << "节点" << i << ": 不可达" << endl;
        } else {
            cout << "节点" << i << ": " << shortestDist[i] << endl;
        }
    }
    
    return 0;
}

代码关键点说明

• INF的定义使用INT_MAX / 2是为了避免两个INF相加时出现整数溢出的问题
• 贪心选择步骤中，每次都要遍历所有未访问节点找到距离最小的节点，时间复杂度为O(n²)，适合节点数量不是特别多的场景
• 邻接矩阵的初始化需要先把所有边设为无穷大，再单独设置存在边的权重，避免遗漏无连接边的情况
• 如果图中存在负权边，Dijkstra算法无法正确求解最短路径，这种情况需要使用其他算法比如Bellman-Ford算法

测试结果说明

上述示例代码中，起始节点为0，构建的图结构里，节点0到节点1的最短距离是2，到节点2的最短距离是3（0->1->2），到节点3的最短距离是6（0->1->2->3），运行代码后会输出对应的正确结果。

Dijkstra算法邻接矩阵贪心算法C++修改时间：2026-06-09 09:09:24