用堆排序优化邻接表存储的Dijkstra算法

Dijkstra算法是一种用于解决单源最短路径问题的算法，可以用来计算从给定源节点到所有其他节点的最短路径。在邻接表存储图的情况下，Dijkstra算法的时间复杂度为O((E+V)logV)，其中E和V分别为边数和节点数。

当图比较稠密时，邻接表存储图的空间复杂度会比邻接矩阵低，但是在Dijkstra算法中，由于需要频繁地访问和更新距离数组，邻接表可能会导致大量的缓存不命中，从而降低算法的效率。

为了优化Dijkstra算法在邻接表存储图下的性能，可以使用堆排序来维护节点的距离值，并且在每次更新节点距离值时，将新的节点插入堆中。这样就可以保证堆中的节点总是按照距离值从小到大排列，从而使得访问和更新距离数组的次数最小化。

具体地，可以使用一个小根堆来维护节点的距离值。首先将源节点的距离值设置为0，并将其插入堆中。然后，重复执行以下步骤，直到堆为空：

1.从堆中取出距离值最小的节点u；

2.遍历节点u的所有邻居节点v，如果从源节点到节点v的距离值可以通过节点u进行更新，则更新节点v的距离值，并将节点v插入堆中；

3.重复执行步骤1和步骤2，直到堆为空或者找到了目标节点。

在这个过程中，每个节点最多被插入堆一次，因此时间复杂度为O((E+V)logV)。

使用堆排序优化邻接表存储的Dijkstra算法可以显著提高算法的效率，特别是在处理稠密图的情况下。

相关问题

用堆排序优化邻接表存储的Dijkstra算法的C语言代码

以下是用堆排序优化邻接表存储的Dijkstra算法的C语言代码：

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

#define MAX_VERTEX_NUM 10000
#define INF INT_MAX

typedef struct EdgeNode {
    int adjvex;         // 邻接点编号
    int weight;         // 权值
    struct EdgeNode *next;  // 下一个邻接点
} EdgeNode;

typedef struct VertexNode {
    int data;           // 顶点编号
    EdgeNode *firstEdge;    // 第一个邻接点
} VertexNode;

typedef struct Graph {
    int vexnum, arcnum;     // 顶点数，边数
    VertexNode vertex[MAX_VERTEX_NUM];  // 顶点数组
} Graph;

typedef struct HeapNode {
    int vex;            // 顶点编号
    int dist;           // 最短路径长度
} HeapNode;

typedef struct Heap {
    int size;           // 堆大小
    HeapNode elem[MAX_VERTEX_NUM];      // 堆数组
} Heap;

void createGraph(Graph *G) {
    scanf("%d%d", &G->vexnum, &G->arcnum);
    for (int i = 1; i <= G->vexnum; i++) {
        G->vertex[i].data = i;
        G->vertex[i].firstEdge = NULL;
    }
    for (int i = 1; i <= G->arcnum; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        EdgeNode *e = (EdgeNode *) malloc(sizeof(EdgeNode));
        e->adjvex = v;
        e->weight = w;
        e->next = G->vertex[u].firstEdge;
        G->vertex[u].firstEdge = e;
    }
}

void initDist(int dist[], int v, int start) {
    for (int i = 1; i <= v; i++)
        dist[i] = INF;
    dist[start] = 0;
}

void initHeap(Heap *H, int dist[], int v, int start) {
    H->size = 0;
    for (int i = 1; i <= v; i++) {
        if (i != start) {
            H->elem[++H->size].vex = i;
            H->elem[H->size].dist = dist[i];
        }
    }
}

void swap(HeapNode *a, HeapNode *b) {
    HeapNode tmp = *a;
    *a = *b;
    *b = tmp;
}

void siftDown(Heap *H, int i) {
    int flag = 0;
    while (i * 2 <= H->size && !flag) {
        int minChild;
        if (i * 2 == H->size || H->elem[i * 2].dist < H->elem[i * 2 + 1].dist)
            minChild = i * 2;
        else
            minChild = i * 2 + 1;
        if (H->elem[i].dist > H->elem[minChild].dist) {
            swap(&H->elem[i], &H->elem[minChild]);
            i = minChild;
        } else
            flag = 1;
    }
}

void siftUp(Heap *H, int i) {
    int flag = 0;
    while (i > 1 && !flag) {
        if (H->elem[i].dist < H->elem[i / 2].dist) {
            swap(&H->elem[i], &H->elem[i / 2]);
            i /= 2;
        } else
            flag = 1;
    }
}

void insert(Heap *H, int vex, int dist[]) {
    H->elem[++H->size].vex = vex;
    H->elem[H->size].dist = dist[vex];
    siftUp(H, H->size);
}

int deleteMin(Heap *H, int dist[]) {
    int minVex = H->elem[1].vex;
    H->elem[1] = H->elem[H->size--];
    siftDown(H, 1);
    return minVex;
}

void dijkstra(Graph *G, int dist[], int start) {
    Heap H;
    EdgeNode *e;
    initDist(dist, G->vexnum, start);
    initHeap(&H, dist, G->vexnum, start);
    while (H.size > 0) {
        int u = deleteMin(&H, dist);
        e = G->vertex[u].firstEdge;
        while (e) {
            int v = e->adjvex;
            if (dist[v] > dist[u] + e->weight) {
                dist[v] = dist[u] + e->weight;
                for (int i = 1; i <= H.size; i++) {
                    if (H.elem[i].vex == v) {
                        H.elem[i].dist = dist[v];
                        siftUp(&H, i);
                        break;
                    }
                }
            }
            e = e->next;
        }
    }
}

int main() {
    Graph G;
    createGraph(&G);
    int dist[MAX_VERTEX_NUM];
    dijkstra(&G, dist, 1);
    for (int i = 1; i <= G.vexnum; i++)
        printf("%d ", dist[i]);
    return 0;
}

其中，`Heap`结构体表示堆，`HeapNode`结构体表示堆中的元素，`createGraph()`函数创建邻接表存储的图，`initDist()`函数初始化距离数组，`initHeap()`函数初始化堆，`swap()`函数交换两个元素的值，`siftDown()`函数下滤操作，`siftUp()`函数上滤操作，`insert()`函数向堆中插入一个元素，`deleteMin()`函数删除堆中的最小元素，`dijkstra()`函数实现Dijkstra算法。

c语言代码邻接表实现dijkstra算法求单源最短路径

以下是使用邻接表实现Dijkstra算法求单源最短路径的C语言代码：

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

#define MAX_VERTICES 1000

typedef struct Edge {
    int dest;
    int weight;
    struct Edge* next;
} Edge;

typedef struct Node {
    Edge* head;
} Node;

typedef struct Graph {
    int num_vertices;
    Node nodes[MAX_VERTICES];
} Graph;

Graph* create_graph(int num_vertices) {
    Graph* graph = (Graph*) malloc(sizeof(Graph));
    graph->num_vertices = num_vertices;
    for (int i = 0; i < num_vertices; i++)
        graph->nodes[i].head = NULL;
    return graph;
}

Edge* create_edge(int dest, int weight) {
    Edge* edge = (Edge*) malloc(sizeof(Edge));
    edge->dest = dest;
    edge->weight = weight;
    edge->next = NULL;
    return edge;
}

void add_edge(Graph* graph, int src, int dest, int weight) {
    Edge* edge = create_edge(dest, weight);
    edge->next = graph->nodes[src].head;
    graph->nodes[src].head = edge;
}

int min_distance(int dist[], int visited[], int num_vertices) {
    int min_dist = INT_MAX, min_vertex;
    for (int i = 0; i < num_vertices; i++) {
        if (!visited[i] && dist[i] < min_dist) {
            min_dist = dist[i];
            min_vertex = i;
        }
    }
    return min_vertex;
}

void print_solution(int dist[], int num_vertices) {
    printf("Vertex\tDistance from Source\n");
    for (int i = 0; i < num_vertices; i++)
        printf("%d\t%d\n", i, dist[i]);
}

void dijkstra(Graph* graph, int src) {
    int dist[MAX_VERTICES];
    int visited[MAX_VERTICES];
    for (int i = 0; i < graph->num_vertices; i++) {
        dist[i] = INT_MAX;
        visited[i] = 0;
    }
    dist[src] = 0;
    for (int i = 0; i < graph->num_vertices - 1; i++) {
        int u = min_distance(dist, visited, graph->num_vertices);
        visited[u] = 1;
        for (Edge* edge = graph->nodes[u].head; edge != NULL; edge = edge->next) {
            int v = edge->dest;
            int weight = edge->weight;
            if (!visited[v] && dist[u] != INT_MAX && dist[u] + weight < dist[v])
                dist[v] = dist[u] + weight;
        }
    }
    print_solution(dist, graph->num_vertices);
}

int main() {
    int num_vertices = 5;
    Graph* graph = create_graph(num_vertices);
    add_edge(graph, 0, 1, 10);
    add_edge(graph, 0, 4, 5);
    add_edge(graph, 1, 2, 1);
    add_edge(graph, 1, 4, 2);
    add_edge(graph, 2, 3, 4);
    add_edge(graph, 3, 2, 6);
    add_edge(graph, 3, 0, 7);
    add_edge(graph, 4, 1, 3);
    add_edge(graph, 4, 2, 9);
    dijkstra(graph, 0);
    return 0;
}

这里实现的Dijkstra算法使用了邻接表来表示图，使用了堆排序的思想来寻找当前距离源点最近的未访问过的节点，以提高算法效率。