用C语言写一个dijkstra算法程序
时间: 2023-10-12 09:05:04 浏览: 44
以下是一个C语言实现的Dijkstra算法程序,用于求解带权图的最短路径。
```
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_VERTICES 1000
int graph[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵表示法
int dist[MAX_VERTICES]; // 存储最短距离
int visited[MAX_VERTICES]; // 标记已访问的节点
int dijkstra(int start, int end, int n) {
int i, j, u, min_dist;
// 初始化
for (i = 0; i < n; i++) {
dist[i] = graph[start][i];
visited[i] = 0;
}
visited[start] = 1;
// 迭代
for (i = 0; i < n - 1; i++) {
min_dist = INT_MAX;
for (j = 0; j < n; j++) {
if (!visited[j] && dist[j] < min_dist) {
u = j;
min_dist = dist[j];
}
}
visited[u] = 1;
for (j = 0; j < n; j++) {
if (!visited[j] && graph[u][j] != INT_MAX && dist[u] + graph[u][j] < dist[j]) {
dist[j] = dist[u] + graph[u][j];
}
}
}
return dist[end];
}
int main() {
int n, m, i, j, u, v, w, start, end;
// 读入图的信息
printf("请输入图的节点数和边数:");
scanf("%d%d", &n, &m);
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
graph[i][j] = INT_MAX;
}
}
printf("请输入每条边的起点、终点和权值:\n");
for (i = 0; i < m; i++) {
scanf("%d%d%d", &u, &v, &w);
graph[u][v] = w;
}
printf("请输入起点和终点:");
scanf("%d%d", &start, &end);
// 调用Dijkstra算法求解最短路径
int shortest_dist = dijkstra(start, end, n);
printf("起点到终点的最短距离为:%d\n", shortest_dist);
return 0;
}
```