c语言编程实现无向图求任意两顶点之间的最短路径

实现无向图求任意两顶点之间的最短路径，可以使用Dijkstra算法或者Floyd算法。

Dijkstra算法：
1. 初始化所有顶点的最短路径为无限大，起点的最短路径为0
2. 选择一个当前未确定最短路径的顶点，标记该顶点已经确定最短路径
3. 更新当前顶点的邻接顶点的最短路径，如果经过当前顶点到达邻接顶点的路径更短，则更新邻接顶点的最短路径
4. 重复步骤2和3，直到所有顶点的最短路径都被确定

Floyd算法：
1. 初始化邻接矩阵，如果两个顶点之间有边，则矩阵中该位置的值为边的权重，否则为无限大
2. 对于每一个顶点k，更新所有顶点i和j之间的最短路径，即更新矩阵中i和j位置的值，如下公式所示：
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
3. 重复步骤2，直到所有顶点之间的最短路径都被求出

具体实现可以参考下面的代码示例：

使用Dijkstra算法：

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

#define MAX_VERTICES 100

typedef struct {
    int weight;
    int visited;
} Edge;

typedef struct {
    Edge edges[MAX_VERTICES][MAX_VERTICES];
    int n;
} Graph;

void init_graph(Graph* g, int n) {
    g->n = n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            g->edges[i][j].weight = INT_MAX;
            g->edges[i][j].visited = 0;
        }
    }
}

void add_edge(Graph* g, int u, int v, int weight) {
    g->edges[u][v].weight = weight;
    g->edges[v][u].weight = weight;
}

void dijkstra(Graph* g, int start, int end) {
    int dist[MAX_VERTICES];
    int path[MAX_VERTICES];
    for (int i = 0; i < g->n; i++) {
        dist[i] = g->edges[start][i].weight;
        path[i] = start;
    }
    dist[start] = 0;
    g->edges[start][start].visited = 1;
    for (int i = 0; i < g->n; i++) {
        int min_dist = INT_MAX;
        int u = start;
        for (int j = 0; j < g->n; j++) {
            if (!g->edges[j][j].visited && dist[j] < min_dist) {
                min_dist = dist[j];
                u = j;
            }
        }
        g->edges[u][u].visited = 1;
        if (u == end) {
            break;
        }
        for (int v = 0; v < g->n; v++) {
            if (g->edges[u][v].weight < INT_MAX) {
                int new_dist = dist[u] + g->edges[u][v].weight;
                if (new_dist < dist[v]) {
                    dist[v] = new_dist;
                    path[v] = u;
                }
            }
        }
    }
    printf("Shortest path from %d to %d: %d\n", start, end, dist[end]);
    printf("Path: %d", end);
    int p = path[end];
    while (p != start) {
        printf(" <- %d", p);
        p = path[p];
    }
    printf(" <- %d\n", start);
}

int main() {
    Graph g;
    init_graph(&g, 6);
    add_edge(&g, 0, 1, 5);
    add_edge(&g, 0, 2, 1);
    add_edge(&g, 1, 2, 2);
    add_edge(&g, 1, 3, 4);
    add_edge(&g, 2, 3, 1);
    add_edge(&g, 2, 4, 6);
    add_edge(&g, 3, 4, 1);
    add_edge(&g, 3, 5, 5);
    add_edge(&g, 4, 5, 2);
    dijkstra(&g, 0, 5);
    return 0;
}

使用Floyd算法：

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

#define MAX_VERTICES 100

typedef struct {
    int weight;
} Edge;

typedef struct {
    Edge edges[MAX_VERTICES][MAX_VERTICES];
    int n;
} Graph;

void init_graph(Graph* g, int n) {
    g->n = n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            g->edges[i][j].weight = INT_MAX;
        }
        g->edges[i][i].weight = 0;
    }
}

void add_edge(Graph* g, int u, int v, int weight) {
    g->edges[u][v].weight = weight;
    g->edges[v][u].weight = weight;
}

void floyd(Graph* g) {
    for (int k = 0; k < g->n; k++) {
        for (int i = 0; i < g->n; i++) {
            for (int j = 0; j < g->n; j++) {
                if (g->edges[i][k].weight < INT_MAX && g->edges[k][j].weight < INT_MAX) {
                    int new_weight = g->edges[i][k].weight + g->edges[k][j].weight;
                    if (new_weight < g->edges[i][j].weight) {
                        g->edges[i][j].weight = new_weight;
                    }
                }
            }
        }
    }
}

int main() {
    Graph g;
    init_graph(&g, 6);
    add_edge(&g, 0, 1, 5);
    add_edge(&g, 0, 2, 1);
    add_edge(&g, 1, 2, 2);
    add_edge(&g, 1, 3, 4);
    add_edge(&g, 2, 3, 1);
    add_edge(&g, 2, 4, 6);
    add_edge(&g, 3, 4, 1);
    add_edge(&g, 3, 5, 5);
    add_edge(&g, 4, 5, 2);
    floyd(&g);
    printf("Shortest path from 0 to 5: %d\n", g.edges[0][5].weight);
    return 0;
}