使用Floyd算法解决有向图最短路径问题

"Floyd算法，也称为Floyd-Warshall算法，是一种用于寻找图中所有顶点对之间最短路径的动态规划方法。在给定的带权有向图G=(V,E)中，Floyd算法通过迭代的方式，检查是否存在通过中间节点改善两个顶点之间最短路径的可能性。其时间复杂度为O(n^3)，其中n是图中的顶点数量。" Floyd算法的基本思想是逐步增加中间节点，检查每一对顶点之间是否存在更短的路径。初始时，假设每个顶点到自身的距离为0，其他顶点对的距离为图中的边权重。算法包含以下步骤： 1. 初始化：创建一个n×n的矩阵A来存储最短路径长度，另一个矩阵P来存储路径信息。对于所有顶点对(v, w)，A[i][j]初始化为边(i, j)的权重，如果不存在边，则设为无穷大（在这里用MAX表示）。P[i][j]初始化为0，表示没有中间节点。 2. 遍历中间节点：对于每一个节点k（从0到n-1），遍历所有顶点对(i, j)： - 检查路径i -> k -> j是否比当前已知的最短路径i -> j更短。如果更短，更新A[i][j]为A[i][k] + A[k][j]，并将P[i][j]设置为k，表示最短路径经过了节点k。 3. 当所有中间节点都被遍历过，A矩阵就包含了所有顶点对之间的最短路径长度，P矩阵则记录了最短路径上经过的中间节点信息。 在提供的代码中，`Floyd`函数实现了Floyd算法的逻辑。`PATH`函数根据P矩阵打印出从一个顶点到另一个顶点的最短路径。`main`函数中，首先定义了一个示例的边权重矩阵C，并调用`Floyd`和`PATH`函数计算并打印出0到3以及3到0的最短路径。 在实际应用中，Floyd算法不仅适用于理论问题，还广泛应用于网络路由、交通路径规划等领域，因为其能处理负权边的最短路径问题，只要图中不存在负权环。然而，如果图中确实存在负权边，Floyd算法可能无法正确找到最短路径，此时可以考虑使用其他算法，如Bellman-Ford算法。