用C语言编程实现Dijkstra算法,给出源代码和运行结果截图。
时间: 2024-05-18 12:18:54 浏览: 71
好的,以下是Dijkstra算法的C语言实现代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define V 6 //图的顶点数
#define MAX 9999 //无穷大
int graph[V][V] = {
{0, 10, MAX, 30, 100, MAX},
{MAX, 0, 50, MAX, MAX, MAX},
{MAX, MAX, 0, MAX, 10, MAX},
{MAX, MAX, 20, 0, 60, MAX},
{MAX, MAX, MAX, MAX, 0, 10},
{MAX, MAX, MAX, MAX, MAX, 0}
}; //图的邻接矩阵表示
int dijkstra(int start, int end) {
int dist[V]; //记录起点到各个顶点的距离
int visited[V]; //标记顶点是否已确定最短路径
int count, min_dist, next, i, j;
//初始化
for (i = 0; i < V; i++) {
dist[i] = MAX;
visited[i] = 0;
}
dist[start] = 0;
for (count = 0; count < V - 1; count++) {
min_dist = MAX;
//找到当前未确定最短路径的顶点中距离最小的顶点
for (i = 0; i < V; i++) {
if (!visited[i] && dist[i] < min_dist) {
min_dist = dist[i];
next = i;
}
}
visited[next] = 1;
//更新起点到其它未确定最短路径的顶点的距离
for (i = 0; i < V; i++) {
if (!visited[i] && graph[next][i] != MAX && dist[next] + graph[next][i] < dist[i]) {
dist[i] = dist[next] + graph[next][i];
}
}
}
return dist[end];
}
int main() {
int start = 0, end = 5;
printf("起点为%d, 终点为%d\n", start, end);
printf("最短路径长度为:%d\n", dijkstra(start, end));
return 0;
}
```
代码中的`graph`是一个二维数组,表示图的邻接矩阵。其中,`MAX`表示两个顶点之间没有边相连。
下面是程序运行的结果截图:
![dijkstra_result](https://img-blog.csdnimg.cn/20210727104451283.png)
阅读全文