#include stdioh#include stdlibh#include limitsh#define MAX_VERTICES 100#define INF INT_MAXtypedef struct int weight; int visited; Vertex;int minDistanceVertex vertices int n int min = INF m

#include <stdio.h> #include <stdlib.h> #include <limits.h> #define MAX_VERTICES 100 #define INF INT_MAX

typedef struct { int weight; // 顶点的权重 int visited; // 顶点是否被访问过 } Vertex;

int minDistance(Vertex vertices[], int n) { int min = INF, min_index = -1; for (int v = 0; v < n; v++) { // 找到未被访问过的顶点中权重最小的顶点 if (vertices[v].visited == 0 && vertices[v].weight <= min) { min = vertices[v].weight; min_index = v; } } return min_index; }

void dijkstra(int graph[MAX_VERTICES][MAX_VERTICES], int src, int dest, int n) { Vertex vertices[MAX_VERTICES]; int distances[MAX_VERTICES]; // 顶点到源顶点的最短距离 int path[MAX_VERTICES]; // 记录最短路径

for (int v = 0; v < n; v++) {
    vertices[v].weight = INF; // 初始化顶点的权重为无穷大
    vertices[v].visited = 0; // 初始化顶点的访问状态为未访问
    distances[v] = INF; // 初始化顶点到源顶点的最短距离为无穷大
    path[v] = -1; // 初始化最短路径数组为-1
}

vertices[src].weight = 0; // 源顶点的权重为0
distances[src] = 0; // 源顶点到源顶点的最短距离为0

for (int count = 0; count < n - 1; count++) {
    int u = minDistance(vertices, n); // 找到未被访问过的顶点中权重最小的顶点
    vertices[u].visited = 1; // 标记该顶点为已访问
    
    // 更新其他顶点的最短距离和最短路径
    for (int v = 0; v < n; v++) {
        if (vertices[v].visited == 0 && graph[u][v] != INF && vertices[u].weight != INF && vertices[u].weight + graph[u][v] < vertices[v].weight) {
            vertices[v].weight = vertices[u].weight + graph[u][v];
            distances[v] = vertices[v].weight;
            path[v] = u;
        }
    }
}

printf("从顶点 %d 到顶点 %d 的最短路径为：", src, dest);
int i = dest;
printf("%d ", i);
while (path[i] != -1) {
    printf("<- %d ", path[i]);
    i = path[i];
}
printf("\n最短路径长度为：%d\n", distances[dest]);

}

int main() { int n, e, src, dest; printf("请输入顶点数和边数："); scanf("%d%d", &n, &e);

int graph[MAX_VERTICES][MAX_VERTICES];

// 初始化图的邻接矩阵为无穷大
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        graph[i][j] = INF;
    }
}

printf("请输入每条边的起点、终点和权重：\n");
for (int i = 0; i < e; i++) {
    int u, v, weight;
    scanf("%d%d%d", &u, &v, &weight);
    graph[u][v] = weight; // 更新图的邻接矩阵
}

printf("请输入源顶点和目标顶点：");
scanf("%d%d", &src, &dest);

dijkstra(graph, src, dest, n); // 调用Dijkstra算法

return 0;