迪杰斯特拉算法c语言实现,简单讲述

以下是全部迪杰斯特拉算法的代码以及注释

#include <stdio.h>      // 引入标准输入输出库
#include <limits.h>    // 引入常量定义库，提供 INT_MAX 等常量


// 函数：寻找未处理节点中最小距离的节点
int minDistance(int dist[], int sptSet[],int n) {
    int min = INT_MAX, min_index; // 初始化最小距离和索引

    // 遍历所有节点
    for (int v = 0; v < n; v++) {
        // 如果节点未处理且其距离小于当前最小距离
        if (sptSet[v] == 0 && dist[v] < min) {
            min = dist[v]; // 更新最小距离
            min_index = v; // 记录该节点的索引
        }
    }
    return min_index; // 返回最小距离节点的索引
}

// 函数：执行迪杰斯特拉算法
void dijkstra(int n, int src) {
    int dist[n]; // 存储每个节点到起始节点的最短路径估计值
    int sptSet[n]; // 存储已处理节点的集合
    int graph[n][n];
    for(int i=0;i<n;i++)
    {
    	for(int j=0;j<n;j++)
    	{
    		scanf("%d",&graph[i][j]);
		}
	}
    // 初始化
    for (int i = 0; i < n; i++) {
        dist[i] = INT_MAX; // 所有节点的初始距离设为无穷大
        sptSet[i] = 0; // 所有节点的初始状态设为未处理
    }
    dist[src] = 0; // 起始节点到自身的距离设为 0

    // 主循环：每次找到最小距离节点并更新其邻接节点
    for (int count = 0; count < n - 1; count++) {
        int u = minDistance(dist, sptSet,n); // 选择未处理的最小距离节点

        sptSet[u] = 1; // 标记该节点为已处理

        // 更新邻接节点的距离
        for (int v = 0; v < n; v++) {
            // 如果节点未处理且存在边，且新的距离小于当前已知距离
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v]; // 更新最短路径
            }
        }
    }

    // 打印每个节点到起始节点的最短距离
    for (int i = 0; i < n; i++) {
    	if(i==src)
    	{
    		continue;
		}
		if(dist[i]>=9999)
		{
			dist[i]=-1;
		}
        printf("%d\n", dist[i]);
    }
}

int main() {
    // 定义邻接矩阵，表示图的边权重
    int n,s;
    scanf("%d%d",&n,&s);
    dijkstra(n, s); // 从节点 0 开始执行迪杰斯特拉算法

    return 0; // 程序结束
}

//******************************************************************************************



//https://www.dotcpp.com/oj/problem1708.html原题链接 



//******************************************************************************************

总体来说是找每一个点中离他最近的点并且保存