旅游导游系统问题 （1）问题描述 假设一个旅游景区由n个不同景点组成（有向网），并用带权邻接矩阵表示，权值表示两个景点间的步行时间，试编写程序求任意两个景点间的最短步行时间。 （2）基本要求 实际上是求有向图中任意两顶点间的最短路径问题。利用Floyed算法编写函数实现求图的任意两点间的最短路径。（1）给出程序设计的基本思想、原理和算法描述。

(1) 基本思想：

Floyed算法是一种动态规划算法，用于解决有向图中任意两个顶点之间的最短路径问题。其基本思想是，对于图中的任意两个顶点i和j，以及所有的中间顶点k，如果从i到j通过k会更短，那么就更新i到j的最短路径长度。

(2) 原理：

Floyed算法的主要原理是通过三重循环，依次枚举所有的顶点，计算出每个顶点对之间的最短距离。具体地，设d[i][j]表示顶点i到顶点j之间的最短路径长度，那么对于每个顶点k，若从i到j的路径经过k比不经过k更短，则更新d[i][j]的值为d[i][k]+d[k][j]。

(3) 算法描述：

假设邻接矩阵为dis，顶点数为n，则Floyed算法的伪代码如下：

for k in range(n):
    for i in range(n):
        for j in range(n):
            dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])

其中，k表示中间顶点，i和j表示起点和终点，dis[i][j]表示从i到j的最短路径长度。

(4) Python 代码实现：

def floyd(dis):
    n = len(dis)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
    return dis

其中，dis表示邻接矩阵，函数返回更新后的邻接矩阵。