如何用C语言编写一个程序来计算基于邻接矩阵表示的图中最短路径算法？

在C语言中，我们可以使用Dijkstra算法或者Floyd-Warshall算法来计算基于邻接矩阵表示的图的最短路径。这里我们以Dijkstra算法为例，它更适合于单源最短路径问题。

首先，需要包含必要的头文件并定义一些辅助函数：

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

// 辅助函数，用于检查数组值是否为无穷大
int isInfinity(int dist[], int V) {
    return dist[V] == INT_MAX;
}

// 辅助函数，用于更新最短距离
void relaxDistances(int graph[][V], int dist[], int src, int i, int V) {
    if (dist[i] > dist[src] + graph[src][i]) {
        dist[i] = dist[src] + graph[src][i];
    }
}

接下来，是主的Dijkstra算法实现：

void dijkstra(int graph[][V], int src, int V, int dist[]) {
    // 初始化所有顶点到源的距离为无穷大，除了源本身
    for (int v = 0; v < V; ++v) {
        dist[v] = (v == src) ? 0 : INT_MAX;
    }

    // 遍历所有顶点，直到找到最短路径
    for (int count = 0; count < V -1;
        for (int v = 0; v < V; ++v)
            if (!isInfinity(dist, v) && (u == -1 || dist[u] > dist[v])) {
                u = v;
            }

        // 更新u的所有邻居
        for (int v = 0; v < V; ++v)
            relaxDistances(graph, dist, src, u, v);
    }
}

// 主函数入口
int main() {
    // 假设V是顶点数，graph[V][V]存储邻接矩阵
    int V, src;
    printf("Enter the number of vertices: ");
    scanf("%d", &V);
    printf("Enter source vertex: ");
    scanf("%d", &src);

    // 其他输入（比如读取邻接矩阵）...
    
    int dist[V]; // 存储每个顶点到源的最短距离
    dijkstra(graph, src, V, dist);

    // 输出结果...
    // 输出dist数组中各顶点到源的最短距离
    for (int i = 0; i < V; ++i) {
        printf("Distance from %d to source: %d\n", i, dist[i]);
    }

    return 0;
}