C语言实现Floyd算法：探索最短路径

弗洛伊德算法是一种在图论中用于寻找所有顶点对之间最短路径的经典动态规划方法，它通常用于解决有向或无向图中的单源最短路径问题。在这个C语言实现的版本中，首先定义了一些常量，如最大顶点数MAX_VERTEX_NUM100和最大整数值MAX_INT10000，这些用于限制图的规模和表示无穷大的距离。 `MGraph`结构体用于表示一个邻接矩阵表示的图，其中包含顶点数组`V`和邻接矩阵`A`。邻接矩阵`A[i][j]`表示顶点`i`和`j`之间的边的权重，如果`A[i][j]`小于某个值，则表示存在边且有相应的权重。 `PathType`结构体用来存储从顶点`v`到其他顶点`vi`的最短路径，包括路径长度`pi[]`和路径终点索引`end`。`Floyd`函数的核心逻辑是通过三层循环遍历图的每一对顶点，更新每对顶点之间的最短路径。初始时，假设所有顶点到它们自身的路径长度为0，其他顶点间的路径长度为无穷大（由`MAX_INT`表示）。 在每次迭代中，算法会检查每条边，如果发现经过某中间顶点的路径长度比直接连接的两个顶点的路径更短，就更新这条路径。这个过程会持续进行直到没有进一步的改进，从而确保得到的是每对顶点之间的最短路径。当`Floyd`函数结束时，`D[][]`矩阵将存储所有顶点对之间的最短路径长度，而`path[][]`矩阵则可以用来追踪实际的最短路径。 这个C语言实现的弗洛伊德算法适用于解决大型图的最短路径问题，它的时间复杂度为O(n^3)，其中n是顶点数量。这对于处理相对较小的图是非常有效的，但对于大规模图，可能需要考虑更高效的算法，如迪杰斯特拉算法或贝尔曼-福特算法。这个代码片段为理解和实现基本的图论算法提供了一个实用的示例。