求图中两点间最短路径 代码c
时间: 2023-06-25 20:06:16 浏览: 93
这是一个经典的图论问题,可以使用 Dijkstra 算法或者 Floyd 算法来解决。
Dijkstra 算法适用于单源最短路径问题,即求一个节点到其他所有节点的最短路径。具体实现过程如下:
1. 初始化:将起点的距离设为 0,其他节点的距离设为无穷大。
2. 从未确定最短路径的节点中选取距离最小的节点,将其标记为已确定最短路径。
3. 更新与该节点相邻的节点的距离值,如果经过该节点到达相邻节点的距离比已有的距离小,则更新距离值。
4. 重复步骤 2 和 3,直到所有节点都被标记为已确定最短路径,或者没有与起点相连通的节点。
下面是 Dijkstra 算法的 C 代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_N 100
#define INF INT_MAX
int graph[MAX_N][MAX_N]; // 图的邻接矩阵表示
int dist[MAX_N]; // 起点到各个节点的最短距离
int visited[MAX_N]; // 记录节点是否已确定最短路径
int dijkstra(int start, int end, int n) {
// 初始化
for (int i = 0; i < n; i++) {
dist[i] = graph[start][i];
visited[i] = 0;
}
dist[start] = 0;
visited[start] = 1;
// 迭代 n-1 次
for (int i = 1; i < n; i++) {
int min_dist = INF;
int min_index = -1;
// 找到距离起点最近的未确定最短路径的节点
for (int j = 0; j < n; j++) {
if (!visited[j] && dist[j] < min_dist) {
min_dist = dist[j];
min_index = j;
}
}
if (min_index == -1) break; // 没有与起点相连通的节点
visited[min_index] = 1;
// 更新与该节点相邻的节点的距离值
for (int j = 0; j < n; j++) {
if (!visited[j] && graph[min_index][j] != INF &&
dist[min_index] + graph[min_index][j] < dist[j]) {
dist[j] = dist[min_index] + graph[min_index][j];
}
}
}
return dist[end];
}
int main() {
int n, m; // n 个节点,m 条边
scanf("%d%d", &n, &m);
// 初始化邻接矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
graph[i][j] = i == j ? 0 : INF;
}
}
// 读入边信息
for (int i = 0; i < m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
graph[u][v] = graph[v][u] = w;
}
// 求最短路径
int start, end;
scanf("%d%d", &start, &end);
int shortest_path = dijkstra(start, end, n);
printf("Shortest path from %d to %d: %d\n", start, end, shortest_path);
return 0;
}
```
Floyd 算法适用于多源最短路径问题,即求任意两点之间的最短路径。具体实现过程如下:
1. 初始化:将任意两个节点之间的距离设为它们之间的边权,如果不存在边则设为无穷大。
2. 逐步扩展:对于每一个节点 k,计算任意两个节点 i 和 j 通过节点 k 的距离是否比它们原本的距离更短,如果更短则更新距离值。
3. 重复步骤 2,直到所有节点都被当做中间节点扩展过。
下面是 Floyd 算法的 C 代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_N 100
#define INF INT_MAX
int graph[MAX_N][MAX_N]; // 图的邻接矩阵表示
int dist[MAX_N][MAX_N]; // 任意两点之间的最短距离
void floyd(int n) {
// 初始化
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = graph[i][j];
}
}
// 逐步扩展
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][k] != INF && dist[k][j] != INF &&
dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
}
int main() {
int n, m; // n 个节点,m 条边
scanf("%d%d", &n, &m);
// 初始化邻接矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
graph[i][j] = i == j ? 0 : INF;
}
}
// 读入边信息
for (int i = 0; i < m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
graph[u][v] = graph[v][u] = w;
}
// 求最短路径
floyd(n);
int start, end;
scanf("%d%d", &start, &end);
int shortest_path = dist[start][end];
printf("Shortest path from %d to %d: %d\n", start, end, shortest_path);
return 0;
}
```