62 lines
2.2 KiB
C
62 lines
2.2 KiB
C
|
#include <stdio.h>
|
||
|
|
#include <limits.h>
|
||
|
|
#include <stdbool.h>
|
||
|
|
|
||
|
|
void dijkstra(int n, int graph[n][n], int source, int dist[n], int parent[n], bool visited[n]) {
|
||
|
|
for (int i = 0; i < n; i++) {
|
||
|
|
dist[i] = INT_MAX; // 初始距离为无穷大
|
||
|
|
parent[i] = -1; // 前驱节点初始化为 -1
|
||
|
|
visited[i] = false; // 所有节点初始未访问
|
||
|
|
}
|
||
|
|
dist[source] = 0; // 源节点的距离为 0
|
||
|
|
for (int i = 0; i < n - 1; i++) {// 寻找未访问的最小距离节点
|
||
|
|
int u = -1;
|
||
|
|
for (int j = 0; j < n; j++) {
|
||
|
|
if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
|
||
|
|
u = j;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
visited[u] = true;// 标记节点 u 为已访问
|
||
|
|
// 更新与节点 u 相邻的未访问节点的最短路径
|
||
|
|
for (int v = 0; v < n; v++) {
|
||
|
|
if (graph[u][v] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
|
||
|
|
dist[v] = dist[u] + graph[u][v];
|
||
|
|
parent[v] = u; // 更新前驱节点
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
void printPath(int parent[], int node) {
|
||
|
|
if (node == -1) return; // 终止条件
|
||
|
|
printPath(parent, parent[node]); // 递归打印前驱节点
|
||
|
|
printf("%d ", node); // 打印当前节点
|
||
|
|
}
|
||
|
|
// 主函数
|
||
|
|
int main() {
|
||
|
|
int n = 5;
|
||
|
|
int graph[5][5] = { // 邻接矩阵表示图
|
||
|
|
{0, 10, INT_MAX, INT_MAX, 5},
|
||
|
|
{10, 0, 1, INT_MAX, INT_MAX},
|
||
|
|
{INT_MAX, 1, 0, 3, INT_MAX},
|
||
|
|
{INT_MAX, INT_MAX, 3, 0, 8},
|
||
|
|
{5, INT_MAX, INT_MAX, 8, 0}
|
||
|
|
};
|
||
|
|
int source = 0; // 设定源节点为 0
|
||
|
|
int dist[n]; // 存储到每个节点的最短距离
|
||
|
|
int parent[n]; // 存储每个节点的前驱节点
|
||
|
|
bool visited[n]; // 标记节点是否已经访问
|
||
|
|
// 运行 Dijkstra 算法
|
||
|
|
dijkstra(n, graph, source, dist, parent, visited);
|
||
|
|
// 输出最短路径结果
|
||
|
|
for (int i = 1; i < n; i++) {
|
||
|
|
if (dist[i] == INT_MAX) {
|
||
|
|
printf("到点 %d 不可直达.\n", i);
|
||
|
|
} else {
|
||
|
|
printf("源点到%d的最短路径是 %d，路径为: ", i, dist[i]);
|
||
|
|
printPath(parent, i); // 打印路径
|
||
|
|
printf("\n");
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return 0;
|
||
|
|
}
|