最短路径dijkstra算法c++代码

以下是使用C++实现的Dijkstra算法的代码示例：

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

using namespace std;

// 定义图的邻接矩阵表示
const int MAX = 100;
vector<vector<int>> graph(MAX, vector<int>(MAX, 0));

// Dijkstra算法实现
void dijkstra(int start, int n) {
    vector<int> dist(n, INT_MAX); // 存储起始点到各个顶点的最短距离
    vector<bool> visited(n, false); // 记录顶点是否已被访问

    dist[start] = 0; // 起始点到自身的距离为0

    for (int i = 0; i < n - 1; i++) {
        int minDist = INT_MAX;
        int minIndex = -1;

        // 找到当前未访问的顶点中距离起始点最近的顶点
        for (int j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < minDist) {
                minDist = dist[j];
                minIndex = j;
            }
        }

        if (minIndex == -1) {
            break;
        }

        visited[minIndex] = true;

        // 更新最短距离
        for (int j = 0; j < n; j++) {
            if (!visited[j] && graph[minIndex][j] != 0 && dist[minIndex] != INT_MAX &&
                dist[minIndex] + graph[minIndex][j] < dist[j]) {
                dist[j] = dist[minIndex] + graph[minIndex][j];
            }
        }
    }

    // 输出最短距离
    cout << "最短路径长度：" << endl;
    for (int i = 0; i < n; i++) {
        cout << start << " 到 " << i << " 的最短距离为：" << dist[i] << endl;
    }
}

int main() {
    int n = 6; // 图中顶点的数量

    // 初始化图的邻接矩阵
    graph = {
        {0, 2, 0, 1, 0, 0},
        {2, 0, 4, 0, 0, 0},
        {0, 4, 0, 1, 3, 0},
        {1, 0, 1, 0, 2, 0},
        {0, 0, 3, 2, 0, 1},
        {0, 0, 0, 0, 1, 0}
    };

    int start = 0; // 起始点

    dijkstra(start, n);

    return 0;
}