最短路径算法的编程与实现C语言

最短路径算法是一种常用的算法，可以用来求解两点之间的最短路径。在实际编程中，最短路径算法常用于网络路由、地图导航等领域。下面是用C语言实现最短路径算法的示例代码。

1. Dijkstra算法

Dijkstra算法是一种广泛应用的单源最短路径算法，它的主要思想是贪心算法。下面是Dijkstra算法的C语言实现代码。

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

#define MAX_VERTEX_NUM 100     // 最大顶点数
#define INF INT_MAX            // 定义正无穷

typedef struct {
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];      // 邻接矩阵
    int vexnum, arcnum;                            // 顶点数和边数
    int dist[MAX_VERTEX_NUM];                      // 存储最短路径长度
    int path[MAX_VERTEX_NUM];                      // 存储最短路径上的前驱节点
    int visited[MAX_VERTEX_NUM];                   // 标记节点是否被访问过
} Graph;

void CreateGraph(Graph *G) {
    int i, j, k, w;
    printf("请输入顶点数和边数：\n");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    // 初始化邻接矩阵
    for (i = 0; i < G->vexnum; i++) {
        for (j = 0; j < G->vexnum; j++) {
            G->arcs[i][j] = INF;
        }
    }
    // 构建邻接矩阵
    printf("请输入每条边的起点、终点和权重：\n");
    for (k = 0; k < G->arcnum; k++) {
        scanf("%d%d%d", &i, &j, &w);
        G->arcs[i][j] = w;
    }
}

void Dijkstra(Graph *G, int v0) {
    int i, j, k, min;
    // 初始化
    for (i = 0; i < G->vexnum; i++) {
        G->dist[i] = G->arcs[v0][i];
        G->visited[i] = 0;
        if (G->dist[i] < INF) {
            G->path[i] = v0;
        } else {
            G->path[i] = -1;
        }
    }
    G->dist[v0] = 0;
    G->visited[v0] = 1;
    // 迭代n-1次，每次找到一个最近的节点
    for (i = 1; i < G->vexnum; i++) {
        min = INF;
        for (j = 0; j < G->vexnum; j++) {
            if (!G->visited[j] && G->dist[j] < min) {
                k = j;
                min = G->dist[j];
            }
        }
        G->visited[k] = 1;
        // 更新与当前节点相邻的节点的距离
        for (j = 0; j < G->vexnum; j++) {
            if (!G->visited[j] && G->arcs[k][j] < INF) {
                if (G->dist[k] + G->arcs[k][j] < G->dist[j]) {
                    G->dist[j] = G->dist[k] + G->arcs[k][j];
                    G->path[j] = k;
                }
            }
        }
    }
}

void PrintPath(Graph *G, int v0, int vn) {
    if (v0 == vn) {
        printf("%d", v0);
        return;
    }
    if (G->path[vn] == -1) {
        printf("无法到达");
        return;
    }
    PrintPath(G, v0, G->path[vn]);
    printf("->%d", vn);
}

int main() {
    Graph G;
    int v0, vn;
    CreateGraph(&G);
    printf("请输入起点和终点：\n");
    scanf("%d%d", &v0, &vn);
    Dijkstra(&G, v0);
    printf("从%d到%d的最短路径为：", v0, vn);
    PrintPath(&G, v0, vn);
    printf("\n最短路径长度为：%d\n", G.dist[vn]);
    return 0;
}

2. Floyd算法

Floyd算法是一种动态规划算法，它可以求解任意两点之间的最短路径。下面是Floyd算法的C语言实现代码。

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

#define MAX_VERTEX_NUM 100     // 最大顶点数
#define INF INT_MAX            // 定义正无穷

typedef struct {
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];      // 邻接矩阵
    int vexnum, arcnum;                            // 顶点数和边数
    int dist[MAX_VERTEX_NUM][MAX_VERTEX_NUM];      // 存储最短路径长度
    int path[MAX_VERTEX_NUM][MAX_VERTEX_NUM];      // 存储最短路径上的前驱节点
} Graph;

void CreateGraph(Graph *G) {
    int i, j, k, w;
    printf("请输入顶点数和边数：\n");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    // 初始化邻接矩阵
    for (i = 0; i < G->vexnum; i++) {
        for (j = 0; j < G->vexnum; j++) {
            G->arcs[i][j] = INF;
        }
    }
    // 构建邻接矩阵
    printf("请输入每条边的起点、终点和权重：\n");
    for (k = 0; k < G->arcnum; k++) {
        scanf("%d%d%d", &i, &j, &w);
        G->arcs[i][j] = w;
    }
}

void Floyd(Graph *G) {
    int i, j, k;
    // 初始化
    for (i = 0; i < G->vexnum; i++) {
        for (j = 0; j < G->vexnum; j++) {
            G->dist[i][j] = G->arcs[i][j];
            if (G->arcs[i][j] < INF) {
                G->path[i][j] = i;
            } else {
                G->path[i][j] = -1;
            }
        }
    }
    // 迭代更新
    for (k = 0; k < G->vexnum; k++) {
        for (i = 0; i < G->vexnum; i++) {
            for (j = 0; j < G->vexnum; j++) {
                if (G->dist[i][k] < INF && G->dist[k][j] < INF && G->dist[i][k] + G->dist[k][j] < G->dist[i][j]) {
                    G->dist[i][j] = G->dist[i][k] + G->dist[k][j];
                    G->path[i][j] = G->path[k][j];
                }
            }
        }
    }
}

void PrintPath(Graph *G, int vi, int vj) {
    if (G->path[vi][vj] == -1) {
        printf("无法到达");
        return;
    }
    if (G->path[vi][vj] == vi) {
        printf("%d->%d", vi, vj);
        return;
    }
    PrintPath(G, vi, G->path[vi][vj]);
    printf("->%d", vj);
}

int main() {
    Graph G;
    int vi, vj;
    CreateGraph(&G);
    Floyd(&G);
    printf("请输入起点和终点：\n");
    scanf("%d%d", &vi, &vj);
    printf("从%d到%d的最短路径为：", vi, vj);
    PrintPath(&G, vi, vj);
    printf("\n最短路径长度为：%d\n", G.dist[vi][vj]);
    return 0;
}