用c语言实现Dijkstra算法,并且有具体路径输出
时间: 2023-11-12 21:13:04 浏览: 40
好的,我可以为您提供一个简单的C语言实现Dijkstra算法的示例代码,并输出具体路径。请注意,这个示例代码仅为参考,您可以根据具体情况进行修改和优化。
```
#include <stdio.h>
#include <limits.h>
#define V 6 // 顶点数
#define INF INT_MAX // 定义正无穷
int graph[V][V] = { // 邻接矩阵表示图
{0, 2, INF, 1, INF, INF},
{2, 0, 3, 2, INF, INF},
{INF, 3, 0, INF, 4, INF},
{1, 2, INF, 0, 3, 6},
{INF, INF, 4, 3, 0, 1},
{INF, INF, INF, 6, 1, 0}
};
int dijkstra(int graph[V][V], int start, int end) {
int dist[V]; // 存储起点到各个顶点的最短路径长度
int visited[V] = {0}; // 标记顶点是否已被访问
int prev[V] = {0}; // 存储最短路径上每个顶点的前驱顶点
int i, j, min, u;
// 初始化
for (i = 0; i < V; i++) {
dist[i] = graph[start][i];
visited[i] = 0;
if (dist[i] == INF) {
prev[i] = -1;
} else {
prev[i] = start;
}
}
dist[start] = 0;
visited[start] = 1;
// Dijkstra算法主体
for (i = 1; i < V; i++) {
min = INF;
for (j = 0; j < V; j++) {
if (!visited[j] && dist[j] < min) {
min = dist[j];
u = j;
}
}
visited[u] = 1;
for (j = 0; j < V; j++) {
if (!visited[j] && graph[u][j] != INF && dist[u] + graph[u][j] < dist[j]) {
dist[j] = dist[u] + graph[u][j];
prev[j] = u;
}
}
}
// 输出最短路径
int path[V];
int path_count = 0;
int tmp = end;
path[path_count] = tmp;
path_count++;
while (tmp != start) {
path[path_count] = prev[tmp];
path_count++;
tmp = prev[tmp];
}
printf("The shortest path from %d to %d is: ", start, end);
for (i = path_count - 1; i >= 0; i--) {
printf("%d ", path[i]);
}
printf("\n");
return dist[end];
}
int main() {
int start = 0; // 起点
int end = 5; // 终点
int shortest_dist = dijkstra(graph, start, end);
printf("The shortest distance from %d to %d is: %d\n", start, end, shortest_dist);
return 0;
}
```
在这个示例代码中,我们使用邻接矩阵表示图,其中`graph[i][j]`表示顶点i到顶点j的边权重,如果i和j之间没有边,则`graph[i][j]`为正无穷。在`dijkstra`函数中,我们首先初始化起点到各个顶点的最短路径长度和前驱顶点,并标记起点已被访问。然后在每一轮循环中,找到未访问的顶点中距离起点最近的顶点,将其标记为已访问,并更新其相邻顶点的最短路径和前驱顶点。最后,根据前驱顶点数组输出最短路径。
在`main`函数中,我们指定了起点和终点,并调用`dijkstra`函数计算最短路径和距离。最后输出结果。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](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)