最短路问题C语言代码及算法，要求输出路径

最短路问题是计算从起点到终点的最短路径的问题，常见的算法有Dijkstra算法和Floyd算法。下面给出Dijkstra算法的C语言代码及输出路径的实现。

先定义一个图结构体，包括顶点数、边数、邻接矩阵、起点和终点等信息：

#define MAX_VERTEX_NUM 100  // 最大顶点数
#define INF 0x3f3f3f3f  // 表示无穷大

typedef struct {
    int vexNum;  // 顶点数
    int arcNum;  // 边数
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  // 邻接矩阵
    int start;  // 起点
    int end;  // 终点
} Graph;

然后是Dijkstra算法的实现：

void Dijkstra(Graph g, int *dist, int *path) {
    bool visited[MAX_VERTEX_NUM] = { false };  // 标记数组，表示是否访问过
    for (int i = 0; i < g.vexNum; i++) {
        dist[i] = g.arcs[g.start][i];  // 初始化距离数组
        path[i] = -1;  // 初始化路径数组
    }
    visited[g.start] = true;  // 起点已访问
    dist[g.start] = 0;  // 起点到自身的距离为0
    for (int i = 1; i < g.vexNum; i++) {  // 循环n-1次
        int minDist = INF;
        int u = g.start;
        for (int j = 0; j < g.vexNum; j++) {
            if (!visited[j] && dist[j] < minDist) {  // 找到未访问过的距离最短的顶点
                minDist = dist[j];
                u = j;
            }
        }
        visited[u] = true;  // 标记为已访问
        for (int v = 0; v < g.vexNum; v++) {
            if (!visited[v] && g.arcs[u][v] != INF && dist[u] + g.arcs[u][v] < dist[v]) {  // 更新距离和路径
                dist[v] = dist[u] + g.arcs[u][v];
                path[v] = u;
            }
        }
    }
}

最后是输出路径的实现：

void PrintPath(Graph g, int *path) {
    int stack[MAX_VERTEX_NUM], top = 0;
    int p = g.end;
    while (p != -1) {  // 将路径上的顶点压入栈中
        stack[top++] = p;
        p = path[p];
    }
    printf("The shortest path from %d to %d is: ", g.start, g.end);
    while (top > 1) {  // 逆序输出路径上的顶点
        printf("%d -> ", stack[--top]);
    }
    printf("%d\n", stack[--top]);
}

完整代码如下：

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

#define MAX_VERTEX_NUM 100  // 最大顶点数
#define INF 0x3f3f3f3f  // 表示无穷大

typedef struct {
    int vexNum;  // 顶点数
    int arcNum;  // 边数
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  // 邻接矩阵
    int start;  // 起点
    int end;  // 终点
} Graph;

void Dijkstra(Graph g, int *dist, int *path) {
    bool visited[MAX_VERTEX_NUM] = { false };  // 标记数组，表示是否访问过
    for (int i = 0; i < g.vexNum; i++) {
        dist[i] = g.arcs[g.start][i];  // 初始化距离数组
        path[i] = -1;  // 初始化路径数组
    }
    visited[g.start] = true;  // 起点已访问
    dist[g.start] = 0;  // 起点到自身的距离为0
    for (int i = 1; i < g.vexNum; i++) {  // 循环n-1次
        int minDist = INF;
        int u = g.start;
        for (int j = 0; j < g.vexNum; j++) {
            if (!visited[j] && dist[j] < minDist) {  // 找到未访问过的距离最短的顶点
                minDist = dist[j];
                u = j;
            }
        }
        visited[u] = true;  // 标记为已访问
        for (int v = 0; v < g.vexNum; v++) {
            if (!visited[v] && g.arcs[u][v] != INF && dist[u] + g.arcs[u][v] < dist[v]) {  // 更新距离和路径
                dist[v] = dist[u] + g.arcs[u][v];
                path[v] = u;
            }
        }
    }
}

void PrintPath(Graph g, int *path) {
    int stack[MAX_VERTEX_NUM], top = 0;
    int p = g.end;
    while (p != -1) {  // 将路径上的顶点压入栈中
        stack[top++] = p;
        p = path[p];
    }
    printf("The shortest path from %d to %d is: ", g.start, g.end);
    while (top > 1) {  // 逆序输出路径上的顶点
        printf("%d -> ", stack[--top]);
    }
    printf("%d\n", stack[--top]);
}

int main() {
    Graph g;
    scanf("%d %d %d %d", &g.vexNum, &g.arcNum, &g.start, &g.end);
    for (int i = 0; i < g.vexNum; i++) {
        for (int j = 0; j < g.vexNum; j++) {
            g.arcs[i][j] = INF;
        }
    }
    for (int i = 0; i < g.arcNum; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        g.arcs[u][v] = w;
        g.arcs[v][u] = w;  // 无向图
    }
    int dist[MAX_VERTEX_NUM], path[MAX_VERTEX_NUM];
    Dijkstra(g, dist, path);
    printf("The shortest distance from %d to %d is: %d\n", g.start, g.end, dist[g.end]);
    PrintPath(g, path);
    return 0;
}