弗洛伊德最短路径算法

弗洛伊德最短路径算法是一种用于求解带权有向图中任意一对顶点间最短路径的算法。该算法的时间复度为O(n^3)，相对于迪杰斯特拉算法来说，弗洛伊德算法的形式更为简单。

弗洛伊德算法的基本思想是通过一个三重循环，依次考察每个顶点作为中间节点的情况，更新每一对顶点间的最短路径长度。具体步骤如下：

1. 读入一个有向图的带权邻接矩阵，建立有向图。
2. 初始化一个二维数组d，用于存储每一对顶点间的最短路径长度。将邻接矩阵复制给d。
3. 通过一个三重循环，依次考察每个顶点作为中间节点的情况。假设当前中间节点为k，对于每一对顶点i和j，比较d[i][k] + d[k][j]与d[i][j]的大小，将较小值更新为d[i][j]。
4. 继续进行第3步，直到所有的顶点都被考察为中间节点，即完成了所有顶点间的最短路径计算。
5. 输出最终的d数组，即为每一对顶点间的最短路径长度。

需要注意的是，在计算最短路径的过程中，可以将每个顶点是否可达记录下来，以便后续判断是否存在从源点至相应顶点的路径。如果不存在路径，则输出-1。对于某个顶点到其本身的最短路径长度，输出0。

在题目描述中，输入的第一行为正整数n，表示图中共有n个顶点。接下来的n行为n个用空格隔开的整数，表示带权邻接矩阵。输出为n行n个整数，表示源点至每一个顶点的最短路径长度。

参考资料：
[1] 引用[1]
[2] 引用[2]
[3] 引用[3]