C++实现Dijkstra算法

Dijkstra算法是一种单源最短路径算法，用于求解某一点到其它所有点的最短路径。以下是C++实现Dijkstra算法的示例代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int INF = 0x3f3f3f3f; // 定义无穷大
const int MAXN = 1000; // 最大点数

int n, m; // n为点数，m为边数
int dis[MAXN]; // dis[i]表示源点到i点的最短距离
bool vis[MAXN]; // vis[i]记录i点是否已被访问
int map[MAXN][MAXN]; // 存储图的邻接矩阵

void dijkstra(int start) {
    memset(vis, false, sizeof(vis));
    memset(dis, INF, sizeof(dis));
    dis[start] = 0;
    for (int i = 0; i < n; i++) {
        int x, m = INF;
        for (int j = 0; j < n; j++) { // 找到未访问的最近点
            if (!vis[j] && dis[j] < m) {
                m = dis[j];
                x = j;
            }
        }
        vis[x] = true;
        for (int j = 0; j < n; j++) { // 更新距离
            if (!vis[j] && dis[j] > dis[x] + map[x][j]) {
                dis[j] = dis[x] + map[x][j];
            }
        }
    }
}

int main() {
    // 输入图的点数和边数
    cin >> n >> m;

    // 初始化邻接矩阵
    memset(map, INF, sizeof(map));
    for (int i = 0; i < n; i++) {
        map[i][i] = 0;
    }

    // 输入边的信息
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        map[u][v] = map[v][u] = w; // 无向图
    }

    // 求解最短路径
    dijkstra(0);

    // 输出最短路径
    for (int i = 0; i < n; i++) {
        cout << dis[i] << " ";
    }
    cout << endl;

    return 0;
}

在上述代码中，我们首先定义了一个邻接矩阵来存储图的信息。接着，我们通过输入点数和边数以及边的信息来初始化邻接矩阵。然后，我们定义了一个dis数组来记录源点到其它点的最短距离，以及一个vis数组来记录每个点是否已被访问。接着，我们实现了Dijkstra算法的核心部分，即在未访问的点中找到离源点最近的点，并更新其它点的最短距离。最后，我们输出了源点到其它点的最短路径。