图中某节点到其他结点的最短路径c语言
时间: 2023-11-26 20:03:01 浏览: 38
要计算一个节点到其他节点的最短路径,可以使用 Dijkstra 算法,以下是使用 C 语言实现的示例代码:
```c
#include <stdio.h>
#include <limits.h>
#define SIZE 5 // 节点个数
// 计算源节点到其他节点的最短路径
void dijkstra(int graph[SIZE][SIZE], int src, int dist[]) {
int visited[SIZE] = { 0 }; // 标记节点是否被访问过
for (int i = 0; i < SIZE; i++) {
dist[i] = INT_MAX; // 初始化距离为无穷大
}
dist[src] = 0; // 源节点到自己的距离为0
for (int i = 0; i < SIZE - 1; i++) {
int u = -1;
for (int j = 0; j < SIZE; j++) {
if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
u = j; // 找到未访问的距离源节点最近的节点
}
}
visited[u] = 1;
for (int v = 0; v < SIZE; v++) {
if (graph[u][v] && !visited[v]) {
int newdist = dist[u] + graph[u][v];
if (newdist < dist[v]) { // 更新距离
dist[v] = newdist;
}
}
}
}
}
// 测试
int main() {
int graph[SIZE][SIZE] = {
{0, 10, 0, 30, 100},
{10, 0, 50, 0, 0},
{0, 50, 0, 20, 10},
{30, 0, 20, 0, 60},
{100, 0, 10, 60, 0}
};
int dist[SIZE];
dijkstra(graph, 0, dist);
for (int i = 0; i < SIZE; i++) {
printf("最短距离:0 -> %d = %d\n", i, dist[i]);
}
return 0;
}
```
以上代码实现了 Dijkstra 算法,使用邻接矩阵来表示图,其中 `graph[i][j]` 表示第 i 个节点到第 j 个节点的距离,如果两个节点之间没有边相连,则距离为 0。 `dijkstra()` 函数接受一个邻接矩阵,一个源节点和一个数组,用来存储源节点到其他节点的最短距离。在函数内部,首先初始化距离数组为无穷大,表示源节点到其他节点的距离都是未知的。然后,从源节点开始,每次找到距离源节点最近的未访问节点,并更新与该节点相邻的节点的距离。最后,距离数组中存储的就是源节点到其他节点的最短距离。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![ppt](https://img-home.csdnimg.cn/images/20210720083527.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)