面试题：C语言优化Dijkstra算法性能

1. 数据结构优化

邻接表替代邻接矩阵：对于大规模稀疏图，邻接矩阵会浪费大量空间，因为大部分元素为0。邻接表可以有效减少空间占用，每个节点只存储与其相连的边。
优先队列优化距离存储：在Dijkstra算法中，每次需要找到距离源点最近且未确定最短路径的节点。使用优先队列（如二叉堆）可以将查找最小距离节点的时间复杂度从O(V)优化到O(logV)，其中V是节点数。

2. 算法流程优化

减少重复计算：在更新节点距离时，只有当新的距离小于当前距离时才进行更新，避免不必要的操作。
采用懒惰删除策略：在优先队列中，当一个节点的距离被更新时，不立即删除旧的节点，而是在取出节点时检查其距离是否为最新。这样可以减少优先队列操作的次数。

3. 优化后的C语言代码框架

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define INF 0x3f3f3f3f
#define MAXN 10005 // 假设最大节点数为10005

// 边的结构体
typedef struct Edge {
    int to;
    int w;
    struct Edge *next;
} Edge;

// 邻接表头指针
Edge *head[MAXN];

// 优先队列结构体
typedef struct {
    int id;
    int dist;
} PQNode;

PQNode pq[MAXN];
int pqSize;

// 交换优先队列中的两个元素
void swap(PQNode *a, PQNode *b) {
    PQNode temp = *a;
    *a = *b;
    *b = temp;
}

// 向下调整堆
void downAdjust(int parent) {
    int child = parent * 2 + 1;
    while (child < pqSize) {
        if (child + 1 < pqSize && pq[child + 1].dist < pq[child].dist) {
            child++;
        }
        if (pq[parent].dist <= pq[child].dist) break;
        swap(&pq[parent], &pq[child]);
        parent = child;
        child = parent * 2 + 1;
    }
}

// 向上调整堆
void upAdjust(int child) {
    int parent = (child - 1) / 2;
    while (child > 0 && pq[parent].dist > pq[child].dist) {
        swap(&pq[parent], &pq[child]);
        child = parent;
        parent = (child - 1) / 2;
    }
}

// 添加节点到优先队列
void pushPQ(int id, int dist) {
    pq[pqSize].id = id;
    pq[pqSize].dist = dist;
    upAdjust(pqSize++);
}

// 从优先队列中取出最小距离节点
PQNode popPQ() {
    PQNode top = pq[0];
    pq[0] = pq[--pqSize];
    downAdjust(0);
    return top;
}

// 标记节点是否在优先队列中
int inPQ[MAXN];

// Dijkstra算法
void dijkstra(int start, int n) {
    int dist[MAXN];
    memset(dist, INF, sizeof(dist));
    memset(inPQ, 0, sizeof(inPQ));
    dist[start] = 0;
    pushPQ(start, 0);
    inPQ[start] = 1;

    while (pqSize > 0) {
        PQNode cur = popPQ();
        int u = cur.id;
        inPQ[u] = 0;
        for (Edge *e = head[u]; e != NULL; e = e->next) {
            int v = e->to;
            int w = e->w;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (!inPQ[v]) {
                    pushPQ(v, dist[v]);
                    inPQ[v] = 1;
                }
            }
        }
    }

    // 输出结果
    for (int i = 0; i < n; i++) {
        if (dist[i] == INF) {
            printf("INF ");
        } else {
            printf("%d ", dist[i]);
        }
    }
    printf("\n");
}

// 添加边
void addEdge(int from, int to, int w) {
    Edge *newEdge = (Edge *)malloc(sizeof(Edge));
    newEdge->to = to;
    newEdge->w = w;
    newEdge->next = head[from];
    head[from] = newEdge;
}

int main() {
    int n, m; // n为节点数，m为边数
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int from, to, w;
        scanf("%d %d %d", &from, &to, &w);
        addEdge(from, to, w);
        addEdge(to, from, w); // 如果是无向图
    }
    int start;
    scanf("%d", &start);
    dijkstra(start, n);
    return 0;
}

星途面试题库

面试题：C语言优化Dijkstra算法性能

知识考点

面试题答案

1. 数据结构优化

2. 算法流程优化

3. 优化后的C语言代码框架