C语言如何输出最短路径
时间: 2024-05-15 12:19:50 浏览: 15
要输出最短路径,首先需要使用图论算法计算出最短路径。常用的图论算法有Dijkstra算法、Bellman-Ford算法和Floyd算法等。
以下是使用Dijkstra算法输出最短路径的C语言代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_VERTICES 1000
#define INFINITY INT_MAX
int graph[MAX_VERTICES][MAX_VERTICES];
int dist[MAX_VERTICES];
int visited[MAX_VERTICES];
int dijkstra(int start, int end, int n) {
int i, u, v, min_dist;
// 初始化
for (i = 0; i < n; i++) {
dist[i] = INFINITY;
visited[i] = 0;
}
dist[start] = 0;
// 计算最短路径
for (i = 0; i < n; i++) {
min_dist = INFINITY;
for (v = 0; v < n; v++) {
if (!visited[v] && dist[v] < min_dist) {
min_dist = dist[v];
u = v;
}
}
if (min_dist == INFINITY) {
break;
}
visited[u] = 1;
for (v = 0; v < n; v++) {
if (!visited[v] && graph[u][v] != INFINITY && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
// 输出最短路径
if (dist[end] == INFINITY) {
return -1; // 无法到达目标节点
} else {
printf("最短路径长度为:%d\n", dist[end]);
printf("路径为:%d", end);
u = end;
while (u != start) {
for (v = 0; v < n; v++) {
if (graph[v][u] < INFINITY && dist[v] + graph[v][u] == dist[u]) {
printf("->%d", v);
u = v;
break;
}
}
}
printf("->%d\n", start);
return dist[end];
}
}
int main() {
int n, m, i, j, u, v, w, start, end;
// 输入图的信息
printf("请输入节点数和边数:\n");
scanf("%d%d", &n, &m);
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
graph[i][j] = INFINITY;
}
}
printf("请输入边的信息(起点,终点,权值):\n");
for (i = 0; i < m; i++) {
scanf("%d%d%d", &u, &v, &w);
graph[u][v] = w;
}
printf("请输入起点和终点:\n");
scanf("%d%d", &start, &end);
// 输出最短路径
dijkstra(start, end, n);
return 0;
}
```