用c语言写一串代码 【输入形式】 一个正整数n,代表结点的个数,10≤n≤300 【输出形式】 一个正整数,代表结点 1 和结点 n 之间的最短路径长度
时间: 2024-02-28 19:55:01 浏览: 19
以下是使用 Dijkstra 算法求解最短路径的 C 语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_N 300 // 最大结点数
#define INF INT_MAX // 无穷大
// 邻接矩阵存储图
int graph[MAX_N][MAX_N];
// Dijkstra 算法求解最短路径
int dijkstra(int n)
{
int distances[MAX_N];
int visited[MAX_N] = {0};
for (int i = 0; i < n; i++) {
distances[i] = INF;
}
distances[0] = 0;
for (int i = 0; i < n - 1; i++) {
int min_distance = INF;
int min_node = -1;
for (int j = 0; j < n; j++) {
if (!visited[j] && distances[j] < min_distance) {
min_distance = distances[j];
min_node = j;
}
}
if (min_node == -1) {
break;
}
visited[min_node] = 1;
for (int j = 0; j < n; j++) {
if (graph[min_node][j] != INF) {
int distance = min_distance + graph[min_node][j];
if (distance < distances[j]) {
distances[j] = distance;
}
}
}
}
return distances[n - 1];
}
int main()
{
int n;
scanf("%d", &n);
// 初始化邻接矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) {
graph[i][j] = 0;
} else {
graph[i][j] = INF;
}
}
}
// 读入边和边权
int m;
scanf("%d", &m);
for (int i = 0; i < m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
graph[u - 1][v - 1] = w;
graph[v - 1][u - 1] = w;
}
int shortest_path = dijkstra(n);
printf("%d\n", shortest_path);
return 0;
}
```
其中,graph 是一个邻接矩阵,表示图的连接情况;distances 数组表示每个结点到起点的距离;visited 数组表示每个结点是否已经访问过。