搜索
C语言

Dijkstra算法C语言实现，如何求最短路径？

99ANYc3cd6
99ANYc3cd6 / / 0 评论 / 5 阅读
作者有点忙，还没来得及写简介......
预计阅读时长 28 分钟
位置： 首页 › C语言 › 正文

Dijkstra算法的C语言实现

Dijkstra算法是一种用于在加权图中找到从单个源点到所有其他顶点的最短路径的经典算法,以下是使用C语言实现的Dijkstra算法：

最短路径dijkstra算法c语言
（图片来源网络，侵删）
#include <stdio.h>
#include <limits.h>
#include <stdbool.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[]) {
    printf("顶点\t距离\n");
    for (int i = 0; i < V; i++) {
        printf("%d \t %d\n", i, dist[i]);
    }
}
// Dijkstra算法实现
void dijkstra(int graph[V][V], int src) {
    int dist[V];     // 存储源点到每个顶点的最短距离
    bool sptSet[V];  // sptSet[i]为true表示顶点i在最短路径树中
    // 初始化所有距离为无穷大，sptSet[]为false
    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        sptSet[i] = false;
    }
    // 源点到自身的距离为0
    dist[src] = 0;
    // 找到源点到所有顶点的最短路径
    for (int count = 0; count < V - 1; count++) {
        // 从未处理的顶点中选择距离最小的顶点
        int u = minDistance(dist, sptSet);
        // 将选定的顶点标记为已处理
        sptSet[u] = true;
        // 更新相邻顶点的距离值
        for (int v = 0; v < V; v++) {
            // 更新条件：
            // 1. 顶点v尚未处理
            // 2. 存在从u到v的边
            // 3. 源点到u的距离加上u到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);
}
int main() {
    // 示例图 (邻接矩阵表示)
    int graph[V][V] = {
        {0, 4, 0, 0, 0, 0, 0, 8, 0},
        {4, 0, 8, 0, 0, 0, 0, 11, 0},
        {0, 8, 0, 7, 0, 4, 0, 0, 2},
        {0, 0, 7, 0, 9, 14, 0, 0, 0},
        {0, 0, 0, 9, 0, 10, 0, 0, 0},
        {0, 0, 4, 14, 10, 0, 2, 0, 0},
        {0, 0, 0, 0, 0, 2, 0, 1, 6},
        {8, 11, 0, 0, 0, 0, 1, 0, 7},
        {0, 0, 2, 0, 0, 0, 6, 7, 0}
    };
    dijkstra(graph, 0);  // 从顶点0开始计算
    return 0;
}

算法说明

  1. 输入：图的邻接矩阵表示和源顶点
  2. 输出：从源顶点到图中所有其他顶点的最短距离
  3. 主要步骤：
    • 初始化距离数组为无穷大,源点距离为0
    • 每次从未访问顶点中选择距离最小的顶点
    • 更新该顶点所有相邻顶点的距离值
    • 重复上述过程直到所有顶点都被处理

复杂度分析

  • 时间复杂度：O(V²)，其中V是顶点数量
  • 空间复杂度：O(V)

优化版本

对于稀疏图,可以使用优先队列(最小堆)来优化时间复杂度到O(E + V log V)，其中E是边数量：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define V 9
// 优先队列中的节点结构
struct MinHeapNode {
    int v;
    int dist;
};
// 最小堆结构
struct MinHeap {
    int size;
    int capacity;
    int *pos;
    struct MinHeapNode **array;
};
// 创建新的最小堆节点
struct MinHeapNode* newMinHeapNode(int v, int dist) {
    struct MinHeapNode* minHeapNode = 
        (struct MinHeapNode*)malloc(sizeof(struct MinHeapNode));
    minHeapNode->v = v;
    minHeapNode->dist = dist;
    return minHeapNode;
}
// 创建最小堆
struct MinHeap* createMinHeap(int capacity) {
    struct MinHeap* minHeap = 
        (struct MinHeap*)malloc(sizeof(struct MinHeap));
    minHeap->pos = (int*)malloc(capacity * sizeof(int));
    minHeap->size = 0;
    minHeap->capacity = capacity;
    minHeap->array = 
        (struct MinHeapNode**)malloc(capacity * sizeof(struct MinHeapNode*));
    return minHeap;
}
// 交换两个堆节点
void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b) {
    struct MinHeapNode* t = *a;
    *a = *b;
    *b = t;
}
// 调整堆
void minHeapify(struct MinHeap* minHeap, int idx) {
    int smallest, left, right;
    smallest = idx;
    left = 2 * idx + 1;
    right = 2 * idx + 2;
    if (left < minHeap->size && 
        minHeap->array[left]->dist < minHeap->array[smallest]->dist)
        smallest = left;
    if (right < minHeap->size && 
        minHeap->array[right]->dist < minHeap->array[smallest]->dist)
        smallest = right;
    if (smallest != idx) {
        // 交换节点
        MinHeapNode *smallestNode = minHeap->array[smallest];
        MinHeapNode *idxNode = minHeap->array[idx];
        // 交换位置
        minHeap->pos[smallestNode->v] = idx;
        minHeap->pos[idxNode->v] = smallest;
        // 交换节点
        swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]);
        minHeapify(minHeap, smallest);
    }
}
// 检查堆是否为空
int isEmpty(struct MinHeap* minHeap) {
    return minHeap->size == 0;
}
// 提取最小节点
struct MinHeapNode* extractMin(struct MinHeap* minHeap) {
    if (isEmpty(minHeap))
        return NULL;
    // 存储根节点
    struct MinHeapNode* root = minHeap->array[0];
    // 用最后一个节点替换根节点
    struct MinHeapNode* lastNode = minHeap->array[minHeap->size - 1];
    minHeap->array[0] = lastNode;
    // 更新位置
    minHeap->pos[root->v] = minHeap->size - 1;
    minHeap->pos[lastNode->v] = 0;
    // 减小堆大小并调整
    --minHeap->size;
    minHeapify(minHeap, 0);
    return root;
}
// 减小某个顶点的距离
void decreaseKey(struct MinHeap* minHeap, int v, int dist) {
    int i = minHeap->pos[v];
    minHeap->array[i]->dist = dist;
    // 向上调整堆
    while (i && minHeap->array[i]->dist < minHeap->array[(i - 1) / 2]->dist) {
        // 交换节点及其位置
        minHeap->pos[minHeap->array[i]->v] = (i - 1) / 2;
        minHeap->pos[minHeap->array[(i - 1) / 2]->v] = i;
        swapMinHeapNode(&minHeap->array[i], &minHeap->array[(i - 1) / 2]);
        // 移动到父节点
        i = (i - 1) / 2;
    }
}
// 检查顶点是否在最小堆中
bool isInMinHeap(struct MinHeap *minHeap, int v) {
    if (minHeap->pos[v] < minHeap->size)
        return true;
    return false;
}
// 打印结果
void printArr(int dist[], int n) {
    printf("顶点\t距离\n");
    for (int i = 0; i < n; ++i)
        printf("%d \t %d\n", i, dist[i]);
}
// 使用优先队列的Dijkstra算法
void dijkstra(int graph[V][V], int src) {
    int dist[V];      // 存储最短距离
    // 创建最小堆
    struct MinHeap* minHeap = createMinHeap(V);
    // 初始化距离和堆
    for (int v = 0; v < V; ++v) {
        dist[v] = INT_MAX;
        minHeap->array[v] = newMinHeapNode(v, dist[v]);
        minHeap->pos[v] = v;
    }
    // 源点距离设为0
    dist[src] = 0;
    decreaseKey(minHeap, src, dist[src]);
    // 初始堆大小为V
    minHeap->size = V;
    // 处理堆直到为空
    while (!isEmpty(minHeap)) {
        // 提取最小距离顶点
        struct MinHeapNode* minHeapNode = extractMin(minHeap);
        int u = minHeapNode->v; // 存储顶点编号
        // 遍历所有相邻顶点
        for (int v = 0; v < V; ++v) {
            // 如果顶点v在堆中，存在边u-v，且通过u的路径更短
            if (isInMinHeap(minHeap, v) && graph[u][v] && 
                dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
                decreaseKey(minHeap, v, dist[v]);
            }
        }
    }
    // 打印结果
    printArr(dist, V);
}
int main() {
    int graph[V][V] = {
        {0, 4, 0, 0, 0, 0, 0, 8, 0},
        {4, 0, 8, 0, 0, 0, 0, 11, 0},
        {0, 8, 0, 7, 0, 4, 0, 0, 2},
        {0, 0, 7, 0, 9, 14, 0, 0, 0},
        {0, 0, 0, 9, 0, 10, 0, 0, 0},
        {0, 0, 4, 14, 10, 0, 2, 0, 0},
        {0, 0, 0, 0, 0, 2, 0, 1, 6},
        {8, 11, 0, 0, 0, 0, 1, 0, 7},
        {0, 0, 2, 0, 0, 0, 6, 7, 0}
    };
    dijkstra(graph, 0);
    return 0;
}

这个优化版本使用最小堆来提高性能,特别适合处理稀疏图。

最短路径dijkstra算法c语言
（图片来源网络，侵删）
-- 展开阅读全文 --
头像
dede list分页multi如何正确配置使用？
« 上一篇 2025-12-12
C语言中char类型数据到底占多少字节？
下一篇 » 2025-12-12

相关文章

取消
微信二维码
支付宝二维码

目录[+]