搜索
C语言

Dijkstra算法C语言实现如何优化时间复杂度？

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

Dijkstra算法的C语言实现

Dijkstra算法是一种用于在加权图中找到从单个源点到所有其他顶点的最短路径的经典算法,下面我将提供一个完整的C语言实现。

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];     // 存储从src到i的最短距离
    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不在sptSet中
            // 2. 从u到v有边
            // 3. 从src到u的距离加上u到v的距离小于当前src到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}
    };
    // 从顶点0开始计算最短路径
    dijkstra(graph, 0);
    return 0;
}

代码说明

  1. 数据结构：

    • 使用邻接矩阵表示图（graph[V][V]）
    • dist[]数组存储从源点到各顶点的最短距离
    • sptSet[]数组标记顶点是否已包含在最短路径树中

  2. 主要函数：

    • minDistance(): 找到未访问顶点中距离最小的顶点
    • printSolution(): 打印最终结果
    • dijkstra(): 主算法实现

  3. 算法步骤：

    1. 初始化所有距离为无穷大,源点距离为0
    2. 循环V-1次：
      • 选择未访问顶点中距离最小的顶点u
      • 标记u为已访问
      • 更新u的所有相邻顶点的距离值
    3. 打印结果

复杂度分析

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

优化版本（使用优先队列）

上面的实现使用线性搜索找最小距离,可以使用优先队列（最小堆）来优化：

dijkstra 算法 c语言
（图片来源网络，侵删）
#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 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];     // 存储从src到i的最短距离
    // 创建最小堆
    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可以缩短到v的距离
            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]);
            }
        }
    }
    // 打印结果
    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}
    };
    // 从顶点0开始计算最短路径
    dijkstra(graph, 0);
    return 0;
}

这个优化版本的时间复杂度为O(E log V)，其中E是边数，V是顶点数，适用于稀疏图。

dijkstra 算法 c语言
（图片来源网络，侵删）
-- 展开阅读全文 --
头像
main函数参数在C语言中如何使用？
« 上一篇 01-14
dede手机端图片不显示图片
下一篇 » 01-14

相关文章

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

目录[+]