能输入地图,设计实现最短路径Dijkstra的c语言算法
时间: 2023-06-14 18:05:42 浏览: 52
当然可以,下面是一个简单的 Dijkstra 算法实现,用于寻找从起点到终点的最短路径。
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_NODES 1000
int graph[MAX_NODES][MAX_NODES];
int visited[MAX_NODES];
int distance[MAX_NODES];
int path[MAX_NODES];
// 寻找未访问节点中距离最短的节点
int min_distance(int n) {
int min = INT_MAX;
int min_index = -1;
for (int i = 0; i < n; i++) {
if (!visited[i] && distance[i] <= min) {
min = distance[i];
min_index = i;
}
}
return min_index;
}
void dijkstra(int start, int end, int n) {
// 初始化距离数组为无限大
for (int i = 0; i < n; i++) {
distance[i] = INT_MAX;
}
// 起点距离为0
distance[start] = 0;
for (int i = 0; i < n - 1; i++) {
int u = min_distance(n);
visited[u] = 1;
for (int v = 0; v < n; v++) {
if (!visited[v] && graph[u][v] && distance[u] != INT_MAX && distance[u] + graph[u][v] < distance[v]) {
distance[v] = distance[u] + graph[u][v];
path[v] = u;
}
}
}
// 输出最短路径
if (distance[end] != INT_MAX) {
int i = end;
printf("Shortest path from %d to %d: ", start, end);
printf("%d", i);
while (i != start) {
printf(" <- %d", path[i]);
i = path[i];
}
printf("\nDistance: %d\n", distance[end]);
} else {
printf("No path from %d to %d!\n", start, end);
}
}
int main() {
int n, m, u, v, w, start, end;
printf("Enter number of nodes and edges: ");
scanf("%d %d", &n, &m);
// 初始化图
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
graph[i][j] = 0;
}
visited[i] = 0;
distance[i] = INT_MAX;
path[i] = -1;
}
// 读入边
for (int i = 0; i < m; i++) {
printf("Enter edge %d (u v w): ", i + 1);
scanf("%d %d %d", &u, &v, &w);
graph[u][v] = w;
graph[v][u] = w;
}
printf("Enter start node and end node: ");
scanf("%d %d", &start, &end);
dijkstra(start, end, n);
return 0;
}
```
输入格式为:
```
Enter number of nodes and edges: <n> <m>
Enter edge <i> (u v w): <u> <v> <w>
...
Enter start node and end node: <start> <end>
```
其中,`n` 表示节点数,`m` 表示边数,`u`、`v` 和 `w` 分别表示边的起点、终点和权重,`start` 和 `end` 分别表示起点和终点的节点编号。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)