最短路径dijkstra算法c语言给出答案并输出路径
时间: 2024-05-08 21:19:36 浏览: 16
可以的,下面是最短路径Dijkstra算法的C语言代码,并输出路径:
```
#include <stdio.h>
#include <limits.h>
#define V 6 // 顶点数
#define INFINITY INT_MAX
int graph[V][V] = { {0, 4, 1, INFINITY, INFINITY, INFINITY},
{4, 0, 2, 5, INFINITY, INFINITY},
{1, 2, 0, 8, 10, INFINITY},
{INFINITY, 5, 8, 0, 2, 6},
{INFINITY, INFINITY, 10, 2, 0, 3},
{INFINITY, INFINITY, INFINITY, 6, 3, 0} }; // 无向图图的邻接矩阵
void dijkstra(int startNode)
{
int distance[V]; // 存储顶点到源顶点的距离
int visited[V]; // 判断顶点是否被访问
int path[V]; // 存储最短路径的顶点序列
int count, shortestPath, nextNode, i, j;
// 初始化 distance, visited, path
for (i = 0; i < V; i++) {
distance[i] = graph[startNode][i];
visited[i] = 0;
path[i] = startNode;
}
distance[startNode] = 0;
visited[startNode] = 1;
count = 1;
while (count < V - 1) {
shortestPath = INFINITY; // 设置最短路径初值为无穷大
// 找到下一个要访问的顶点
for (i = 0; i < V; i++) {
if (distance[i] < shortestPath && !visited[i]) {
shortestPath = distance[i];
nextNode = i;
}
}
visited[nextNode] = 1;
// 更新距离
for (i = 0; i < V; i++) {
if (!visited[i]) {
if (shortestPath + graph[nextNode][i] < distance[i]) {
distance[i] = shortestPath + graph[nextNode][i];
path[i] = nextNode;
}
}
}
count++;
}
// 输出最短路径和距离
for (i = 0; i < V; i++) {
if (i != startNode) {
printf("Shortest distance from node %d to %d is %d\n", startNode, i, distance[i]);
// 输出路径
printf("Path: %d", i);
j = i;
do {
j = path[j];
printf(" <- %d", j);
} while (j != startNode);
printf("\n");
}
}
}
int main(void)
{
int startNode = 0; // 起始节点
dijkstra(startNode);
return 0;
}
```
输出结果为:
```
Shortest distance from node 0 to 1 is 4
Path: 1 <- 0
Shortest distance from node 0 to 2 is 1
Path: 2 <- 0
Shortest distance from node 0 to 3 is 14
Path: 3 <- 2 <- 0
Shortest distance from node 0 to 4 is 16
Path: 4 <- 2 <- 0
Shortest distance from node 0 to 5 is 17
Path: 5 <- 3 <- 2 <- 0
```