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

（1）基本思想

Floyd算法是一种动态规划算法，用于解决图中任意两点间的最短路径问题。通过对每个顶点作为中间节点进行遍历，更新两个顶点之间的最短路径。

（2）原理和算法描述

假设有一个有向图G=(V,E)，其中V表示顶点集合，E表示边集合，w(i,j)表示从顶点i到顶点j的边的权值（如果i和j之间没有边，则w(i,j)为无穷大）。Floyd算法通过一个n*n的矩阵D表示任意两个顶点的最短路径长度，其中D[i][j]表示从顶点i到顶点j的最短路径长度。算法的基本思想是：以顶点k为中间节点，检查从顶点i到顶点j的路径是否可以通过k来缩短。如果可以，则更新D[i][j]的值。

Floyd算法的具体步骤如下：

1. 初始化矩阵D，对于有边相连的顶点i和j，D[i][j]的值为w(i,j)，对于其他的D[i][j]，其值为无穷大。

2. 以每个顶点k为中间节点，遍历所有的顶点i和j，如果从顶点i到顶点j的路径可以通过k来缩短，则更新D[i][j]的值为D[i][k]+D[k][j]。

3. 遍历完所有的顶点k后，矩阵D中存储的就是任意两点之间的最短路径长度。

（3）程序设计

以下是用C++实现Floyd算法的代码：

#include <iostream>
using namespace std;

const int INF = 1e9; //定义无穷大

int main()
{
    int n; //顶点数
    cin >> n;

    int graph[n][n]; //邻接矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> graph[i][j];
            if (graph[i][j] == -1) { //如果两个顶点之间没有边，则设置其权值为无穷大
                graph[i][j] = INF;
            }
        }
    }

    //Floyd算法核心代码
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (graph[i][k] != INF && graph[k][j] != INF && graph[i][j] > graph[i][k] + graph[k][j]) {
                    graph[i][j] = graph[i][k] + graph[k][j];
                }
            }
        }
    }

    //输出任意两点间的最短路径长度
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (graph[i][j] == INF) {
                cout << "inf ";
            } else {
                cout << graph[i][j] << " ";
            }
        }
        cout << endl;
    }

    return 0;
}

程序中，先读入顶点数和邻接矩阵，然后用Floyd算法求出任意两个顶点间的最短路径长度，并将结果输出。