写一个c语言的代码输入形式】 一个正整数n,代表结点的个数,10≤n≤300 【输出形式】 一个正整数,代表结点 1 和结点 n 之间的最短路径长度。
时间: 2024-02-28 13:54:50 浏览: 55
好的,以下是使用Dijkstra算法的C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define INF 1000000 // 定义无穷大
int dist[305]; // 存储源点到各个点的距离
bool visited[305]; // 存储各个点是否已访问过
int graph[305][305]; // 存储图的邻接矩阵
void dijkstra(int n) {
// 初始化
for (int i = 1; i <= n; i++) {
dist[i] = INF;
visited[i] = false;
}
dist[1] = 0;
// 进行n-1次循环
for (int i = 1; i < n; i++) {
// 找到距离源点最近的未访问过的点u
int u = 0, min_dist = INF;
for (int j = 1; j <= n; j++) {
if (!visited[j] && dist[j] < min_dist) {
u = j;
min_dist = dist[j];
}
}
visited[u] = true;
// 更新与u相邻的点v的距离
for (int v = 1; v <= n; v++) {
if (!visited[v] && graph[u][v] != INF) {
if (dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
}
}
int main() {
int n;
scanf("%d", &n);
// 初始化图的邻接矩阵
for (int i = 1; i <= n; i++) {
for (int j = 1; 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][v] = w;
graph[v][u] = w; // 如果是无向图,需要将两个方向都赋值
}
// 运行Dijkstra算法
dijkstra(n);
printf("%d\n", dist[n]);
return 0;
}
```
其中,输入参数n表示结点个数,输入参数m表示边的数量,输入格式为:
```
n
m
u1 v1 w1
u2 v2 w2
...
```
其中,每行表示一条边,ui、vi为边的端点,wi为边权。输出为结点1到结点n的最短路径长度。
阅读全文