Dijkstra算法的C语言实现
Dijkstra算法是一种用于在加权图中找到单源最短路径的经典算法,下面我将提供一个完整的C语言实现，包括邻接表表示的图结构、优先队列（最小堆）的实现以及Dijkstra算法本身。
（图片来源网络，侵删）
完整代码实现
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
// 定义最大顶点数
#define MAX_VERTICES 100
// 邻接表节点结构
struct AdjListNode {
int dest;
int weight;
struct AdjListNode* next;
};
// 邻接表结构
struct AdjList {
struct AdjListNode* head;
};
// 图结构
struct Graph {
int V;
struct AdjList* array;
};
// 优先队列节点结构
struct MinHeapNode {
int v;
int dist;
};
// 最小堆结构
struct MinHeap {
int size;
int capacity;
int* pos;
struct MinHeapNode** array;
};
// 创建新的邻接表节点
struct AdjListNode* newAdjListNode(int dest, int weight) {
struct AdjListNode* newNode = (struct AdjListNode*)malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->weight = weight;
newNode->next = NULL;
return newNode;
}
// 创建图
struct Graph* createGraph(int V) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->V = V;
// 创建邻接表数组
graph->array = (struct AdjList*)malloc(V * sizeof(struct AdjList));
// 初始化每个邻接表为空
for (int i = 0; i < V; ++i) {
graph->array[i].head = NULL;
}
return graph;
}
// 添加边到无向图
void addEdge(struct Graph* graph, int src, int dest, int weight) {
// 添加从src到dest的边
struct AdjListNode* newNode = newAdjListNode(dest, weight);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
// 因为是无向图，所以添加反向边
newNode = newAdjListNode(src, weight);
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;
}
// 创建最小堆节点
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("Vertex Distance from Source\n");
for (int i = 0; i < n; ++i)
printf("%d \t\t %d\n", i, dist[i]);
}
// Dijkstra算法主函数
void dijkstra(struct Graph* graph, int src) {
int V = graph->V;
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;
// 遍历所有邻接顶点
struct AdjListNode* pCrawl = graph->array[u].head;
while (pCrawl != NULL) {
int v = pCrawl->dest;
// 如果顶点v在最小堆中且通过u的距离更小
if (isInMinHeap(minHeap, v) && dist[u] != INT_MAX &&
pCrawl->weight + dist[u] < dist[v]) {
dist[v] = dist[u] + pCrawl->weight;
decreaseKey(minHeap, v, dist[v]);
}
pCrawl = pCrawl->next;
}
}
// 打印计算结果
printArr(dist, V);
}
// 主函数
int main() {
// 创建图示例
int V = 9;
struct Graph* graph = createGraph(V);
addEdge(graph, 0, 1, 4);
addEdge(graph, 0, 7, 8);
addEdge(graph, 1, 2, 8);
addEdge(graph, 1, 7, 11);
addEdge(graph, 2, 3, 7);
addEdge(graph, 2, 8, 2);
addEdge(graph, 2, 5, 4);
addEdge(graph, 3, 4, 9);
addEdge(graph, 3, 5, 14);
addEdge(graph, 4, 5, 10);
addEdge(graph, 5, 6, 2);
addEdge(graph, 6, 7, 1);
addEdge(graph, 6, 8, 6);
addEdge(graph, 7, 8, 7);
dijkstra(graph, 0);
return 0;
}
代码说明
-
数据结构:
- 使用邻接表表示图结构
- 使用最小堆（优先队列）来高效获取当前距离最小的顶点
-
主要函数:
createGraph(): 创建图结构addEdge(): 添加边到图中dijkstra(): Dijkstra算法主函数minHeapify(): 维护最小堆性质extractMin(): 提取堆中最小元素decreaseKey(): 减小堆中某个元素的值
-
算法步骤:
- 初始化所有顶点的距离为无穷大,源点距离为0
- 将所有顶点放入最小堆
- 循环直到堆为空:
- 取出堆中距离最小的顶点u
- 遍历u的所有邻接顶点v
- 如果通过u到v的距离比当前已知距离更短,则更新v的距离并调整堆
-
时间复杂度:
（图片来源网络，侵删）- 使用二叉堆实现: O((V + E) log V)
- 使用斐波那契堆实现: O(E + V log V)
示例输出
对于给定的示例图,程序将输出从顶点0到所有其他顶点的最短距离：
Vertex Distance from Source
0 0
1 4
2 12
3 19
4 21
5 11
6 9
7 8
8 14这个实现可以处理带权重的无向图,如果需要处理有向图，只需修改addEdge()函数，去掉添加反向边的部分即可。
（图片来源网络，侵删）
