C语言实现Dijkstra算法

本文目录导读：

1. <"http://#id1" title="Dijkstra算法的基本原理" "">Dijkstra算法的基本原理
2. <"http://#id2" title="C语言实现Dijkstra算法" "">C语言实现Dijkstra算法

Dijkstra算法是一种用于解决最短路径问题的算法，它以荷兰计算机科学家艾兹格·迪杰斯特拉（Edsger Dijkstra）的名字命名，该算法在图形理论、路由、操作系统等领域有着广泛的应用，下面我们将详细介绍如何使用C语言实现Dijkstra算法。

Dijkstra算法的基本原理

Dijkstra算法的基本思想是从源节点开始，逐步向外扩展，找到最短路径，算法的基本步骤如下：

1、初始化：将源节点到自身的距离设为0，将源节点到其他所有节点的距离设为无穷大，将源节点加入已访问**中。

2、选取未访问节点中距离最短的节点，将其加入已访问**中。

3、更新与该节点相邻的未访问节点的距离，如果通过当前节点到达未访问节点的距离小于原来的距离，则更新该距离。

4、重复步骤2和3，直到所有节点都被访问。

C语言实现Dijkstra算法

下面是一个简单的C语言实现Dijkstra算法的代码示例：

#include <stdio.h>
#include <limits.h>
#define V 9  // 顶点数
int minDistance(int dist[], bool sptSet[]) {
    int min = INT_MAX, min_index;
    for (int v = 0; v < V; v++) {
        if (sptSet[v] == false && dist[v] <= min) {
            min = dist[v];
            min_index = v;
        }
    }
    return min_index;
}
void printSolution(int dist[], int n) {
    printf("Vertex \t Distance from Source\n");
    for (int i = 0; i < V; i++) {
        printf("%d \t\t %d\n", i, dist[i]);
    }
}
void dijkstra(int graph[V][V], int src) {
    int dist[V];  // 存储源节点到各个节点的距离
    bool sptSet[V];  // 记录节点是否在已访问**中
    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        sptSet[i] = false;
    }
    dist[src] = 0;  // 源节点到自身的距离为0
    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);  // 选取未访问节点中距离最短的节点
        sptSet[u] = true;  // 将该节点加入已访问**中
        for (int v = 0; v < V; 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];  // 更新距离
            }
        }
    }
    printSolution(dist, V);  // 输出最短路径结果
}

在这个示例中，我们定义了一个9个顶点的图，并使用邻接矩阵来表示图中的边和权重，我们使用一个数组dist来存储源节点到各个节点的距离，使用一个布尔数组sptSet来记录节点是否在已访问**中，在dijkstra()函数中，我们首先初始化dist数组和sptSet数组，然后将源节点到自身的距离设为0，接下来，我们使用minDistance()函数来选取未访问节点中距离最短的节点，并将其加入已访问**中，我们遍历所有节点，更新与当前节点相邻的未访问节点的距离，我们调用printSolution()函数来输出最短路径结果。