在图论中,Dijkstra算法是一种用于找到图中两个顶点之间最短路径的算法。它由荷兰计算机科学家爱德华·迪科斯彻在1959年发明。Dijkstra算法适用于带权图,并且权值非负。下面,我们将用C语言来实现Dijkstra算法,帮助大家轻松入门图论,快速计算最短路径。
Dijkstra算法的基本原理
Dijkstra算法的基本思想是维护一个集合S,其中包含所有已找到最短路径的顶点。初始时,S为空集,算法逐步扩大S,直到S包含所有顶点。
- 初始化:将源点加入集合S,其他顶点加入集合U(未访问顶点集)。源点到自身的距离为0,其他顶点的距离为无穷大。
- 选择U中的顶点u,使得d(u)最小,将其加入集合S。
- 对于U中未加入S的每个顶点v,如果v在u的邻接点中,则计算d(u) + w(u,v),如果这个值小于d(v),则更新d(v)。
- 重复步骤2和3,直到U为空。
C语言实现Dijkstra算法
下面是一个简单的C语言实现Dijkstra算法的示例:
#include <stdio.h>
#include <limits.h>
#define MAX_VERTICES 10
// 函数声明
void dijkstra(int graph[MAX_VERTICES][MAX_VERTICES], int src, int vertices);
int main() {
int graph[MAX_VERTICES][MAX_VERTICES] = {
{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}
};
int src = 0; // 源点
int vertices = 9; // 顶点数
dijkstra(graph, src, vertices);
return 0;
}
void dijkstra(int graph[MAX_VERTICES][MAX_VERTICES], int src, int vertices) {
int dist[vertices]; // 存储最短路径长度
int visited[vertices]; // 标记顶点是否已访问
// 初始化dist和visited数组
for (int i = 0; i < vertices; i++) {
dist[i] = INT_MAX;
visited[i] = 0;
}
dist[src] = 0; // 源点到自身的距离为0
// 遍历所有顶点
for (int i = 0; i < vertices; i++) {
// 寻找未访问顶点中距离最小的顶点
int min_dist = INT_MAX;
int min_index = -1;
for (int j = 0; j < vertices; j++) {
if (!visited[j] && dist[j] < min_dist) {
min_dist = dist[j];
min_index = j;
}
}
// 将找到的顶点加入集合S
visited[min_index] = 1;
// 更新未访问顶点的距离
for (int j = 0; j < vertices; j++) {
if (!visited[j] && graph[min_index][j] && dist[min_index] != INT_MAX && dist[min_index] + graph[min_index][j] < dist[j]) {
dist[j] = dist[min_index] + graph[min_index][j];
}
}
}
// 打印最短路径长度
for (int i = 0; i < vertices; i++) {
if (i != src) {
printf("源点%d到顶点%d的最短路径长度为:%d\n", src, i, dist[i]);
}
}
}
在上面的代码中,我们定义了一个dijkstra函数,该函数接受图、源点和顶点数作为参数,并计算并打印出从源点到其他所有顶点的最短路径长度。
总结
通过以上内容,我们介绍了Dijkstra算法的基本原理和C语言实现。希望这篇文章能帮助大家轻松入门图论,快速计算最短路径。在实际应用中,Dijkstra算法有着广泛的应用,例如在路由算法、网络优化等方面。
