C语言实现迪杰斯特拉算法求解最短路径 - 从地点A到地点B的最短路线

#include <stdio.h> #include <stdlib.h> #include <stdbool.h>

#define MAX_SIZE 100 #define INF 9999

// 定义图的结构体 typedef struct { int matrix[MAX_SIZE][MAX_SIZE]; // 邻接矩阵表示图 int vertexNum; // 顶点数量 } Graph;

// 初始化图 void initGraph(Graph* graph, int vertexNum) { graph->vertexNum = vertexNum; for (int i = 0; i < vertexNum; i++) { for (int j = 0; j < vertexNum; j++) { if (i == j) { graph->matrix[i][j] = 0; } else { graph->matrix[i][j] = INF; }
} } }

// 添加边 void addEdge(Graph* graph, int start, int end, int weight) { graph->matrix[start][end] = weight; graph->matrix[end][start] = weight; }

// 迪杰斯特拉算法 void dijkstra(const Graph* graph, int start, int end) { int distance[MAX_SIZE]; // 存储起点到各点的最短距离 bool visited[MAX_SIZE]; // 记录各个顶点是否已访问 int path[MAX_SIZE]; // 存储最短路径的前驱节点

// 初始化
for (int i = 0; i < graph->vertexNum; i++) {
    distance[i] = graph->matrix[start][i];
    visited[i] = false;
    if (distance[i] < INF) {
        path[i] = start;
    } else {
        path[i] = -1;
    }
}

visited[start] = true;

for (int i = 1; i < graph->vertexNum; i++) {
    int minDistance = INF;
    int minIndex = -1;

    // 找到未访问的顶点中距离起点最近的顶点
    for (int j = 0; j < graph->vertexNum; j++) {
        if (!visited[j] && distance[j] < minDistance) {
            minDistance = distance[j];
            minIndex = j;
        }
    }

    if (minIndex == -1) {
        break;
    }

    visited[minIndex] = true;

    // 更新最短距离和路径
    for (int j = 0; j < graph->vertexNum; j++) {
        if (!visited[j] && distance[minIndex] + graph->matrix[minIndex][j] < distance[j]) {
            distance[j] = distance[minIndex] + graph->matrix[minIndex][j];
            path[j] = minIndex;
        }
    }
}

// 输出最短路径和距离
printf('最短路径为：');
int currentNode = end;
int pathStack[MAX_SIZE];
int top = 0;
while (currentNode != start) {
    pathStack[top++] = currentNode;
    currentNode = path[currentNode];
}

printf('地点%d', start);
while (top > 0) {
    printf('->地点%d', pathStack[--top]);
}
printf('

最短距离为：%d ', distance[end]); }

int main() { Graph graph; initGraph(&graph, 9);

// 添加边
addEdge(&graph, 0, 1, 1);
addEdge(&graph, 0, 2, 3);
addEdge(&graph, 1, 3, 5);
addEdge(&graph, 1, 4, 6);
addEdge(&graph, 2, 3, 2);
addEdge(&graph, 2, 5, 7);
addEdge(&graph, 3, 4, 3);
addEdge(&graph, 3, 6, 9);
addEdge(&graph, 4, 6, 2);
addEdge(&graph, 4, 7, 7);
addEdge(&graph, 5, 6, 4);
addEdge(&graph, 5, 8, 6);
addEdge(&graph, 6, 7, 5);
addEdge(&graph, 7, 8, 3);

int start, end;
printf('请输入起点和终点的地点编号（0-8）：');
scanf('%d %d', &start, &end);

dijkstra(&graph, start, end);

return 0;