本文共 1251 字，大约阅读时间需要 4 分钟。

Dijkstra算法实现

Dijkstra算法是一种广泛使用的最短路径算法，适用于图中从单一起始点到所有其他点的最短路径计算。以下是该算法的实现思路和步骤：

生成初始化数组

算法步骤

代码实现

int pre[n]; // 存储当前点的最短路径权值
int p[n][n]; // 邻接矩阵
void djex(int x, int n) {
    int i, j, k, min;
    int final[1005]; // 标记已访问点
    for (i = 1; i <= n; ++i) {
        pre[i] = p[x][i]; // 初始化权值数组
        final[i] = 0;     // 初始化标记
    }
    pre[x] = 0;        // 起始点自身权值为0
    final[x] = 1;       // 标记为已访问
    for (i = 1; i < n; ++i) {
        min = INF;
        k = x;
        for (j = 1; j <= n; ++j) {
            if (!final[j] && pre[j] < min) {
                k = j;
                min = pre[j];
            }
        }
        if (min == INF) break; // 无路可走
        final[k] = 1; // 标记当前点为已访问
        for (j = 1; j <= n; ++j) {
            if (!final[j] && pre[k] + p[k][j] < pre[j]) {
                pre[j] = pre[k] + p[k][j];
            }
        }
    }
    printf("%d", pre[n]);
}

代码解释

这个实现通过Dijkstra算法高效地计算了从起始点到所有其他点的最短路径，适用于大规模图的最短路径问题。