C++基于Floyd算法实现校园导航系统

算法核心：Floyd最短路径原理

Floyd算法是一种用于寻找图中所有顶点对之间最短路径的动态规划算法。其核心思想是逐步引入中间顶点进行松弛操作（Relaxation）。如果在某次迭代中，从起点i经由中间点到达终点的距离小于直接从前i到的距离，则更新最短路径长度。

在本题中，我们需要记录每个节点对的前驱或后继节点信息，以便后续还原具体行走路径。

数据结构定义与地图构建

首先，需要定义图的存储结构。本例采用邻接矩阵来存储校园内各个地点及其之间的距离。若两点间无直接道路，则初始化为极大值（MaxInt）。

#include<iostream>
#include<stdlib.h>
using namespace std;

#define MaxInt 32767 //表示不可达或极大值
#define MaxNum 100   //最大顶点数限制
typedef int status;
typedef string VerTexType;  //顶点名称类型
typedef int ArcType;        //边的权值类型

typedef struct {
    VerTexType vexs[MaxNum];       //顶点表，存储地名
    ArcType arcs[MaxNum][MaxNum];  //邻接矩阵，存储距离
    int vexnum, arcnum;            //当前顶点数和边数
} AMGraph;

// 创建地图函数
status CreateMap(AMGraph &G) {
    G.vexnum = 10;
    G.arcnum = 13;
    
    // 初始化10个地标节点
    G.vexs[0] = "北门";
    G.vexs[1] = "下沉广场";
    G.vexs[2] = "青年公寓";
    G.vexs[3] = "齐贤广场";
    G.vexs[4] = "15教";
    G.vexs[5] = "菜鸟驿站";
    G.vexs[6] = "汇森楼";
    G.vexs[7] = "图书馆";
    G.vexs[8] = "体育馆";
    G.vexs[9] = "南苑餐厅";
    
    // 初始化距离矩阵为无穷大
    for(int i=0; i<MaxNum; i++)
        for(int j=0; j<MaxNum; j++)
            G.arcs[i][j] = MaxInt;
    
    // 设置实际存在的边及其权重（双向）
    G.arcs[0][1] = G.arcs[1][0] = 300;   // 北门 - 下沉广场
    G.arcs[0][2] = G.arcs[2][0] = 600;   // 北门 - 青年公寓
    G.arcs[1][2] = G.arcs[2][1] = 200;   // 下沉广场 - 青年公寓
    G.arcs[2][3] = G.arcs[3][2] = 600;   // 青年公寓 - 齐贤广场
    G.arcs[2][6] = G.arcs[6][2] = 1000;  // 青年公寓 - 汇森楼
    G.arcs[3][4] = G.arcs[4][3] = 100;   // 齐贤广场 - 15教
    G.arcs[3][6] = G.arcs[6][3] = 800;   // 齐贤广场 - 汇森楼
    G.arcs[4][5] = G.arcs[5][4] = 100;   // 15教 - 菜鸟驿站
    G.arcs[4][8] = G.arcs[8][4] = 400;   // 15教 - 体育馆
    G.arcs[5][9] = G.arcs[9][5] = 700;   // 菜鸟驿站 - 南苑餐厅
    G.arcs[6][7] = G.arcs[7][6] = 100;   // 汇森楼 - 图书馆
    G.arcs[7][8] = G.arcs[8][7] = 100;   // 图书馆 - 体育馆
    G.arcs[8][9] = G.arcs[9][8] = 300;   // 体育馆 - 南苑餐厅
    
    return 1;
}

Floyd算法实现逻辑

为了实现路径回溯，我们额外维护两个二维数组：shortPath存储当前计算出的最短距离，Path存储从源点到目标点的下一个跳跃节点索引。算法运行结束后，可通过Path数组逆向或正向追踪完整路径。

int shortPath[MaxNum][MaxNum]; // 记录最短距离
int Path[MaxNum][MaxNum];      // 记录下一跳节点索引

void ShortestPath_Floyd(AMGraph G) {
    int i, j, k;
    
    // 1. 初始化
    for(i=0; i<G.vexnum; i++) {
        for(j=0; j<G.vexnum; j++) {
            shortPath[i][j] = G.arcs[i][j]; // 复制初始距离
            if(shortPath[i][j] < MaxInt && i != j) 
                Path[i][j] = j;             // 如果直连，下一跳就是自身
            else 
                Path[i][j] = -1;            // 否则标记不可达
        }
    }
    
    // 2. 核心松弛循环：遍历所有可能的中间点k
    for(k=0; k<G.vexnum; k++) {
        for(i=0; i<G.vexnum; i++) {
            for(j=0; j<G.vexnum; j++) {
                // 如果发现经过k点的路径更短
                if(shortPath[i][k] + shortPath[k][j] < shortPath[i][j]) {
                    shortPath[i][j] = shortPath[i][k] + shortPath[k][j];
                    Path[i][j] = Path[i][k]; // 更新下一跳为原来i到k的那一跳
                }
            }
        }
    }
}

路径展示与主界面交互

用户输入起始点和终点的编号后，程序调用上述算法得到结果，并通过一个简单的循环输出具体经过的地点。此外，提供文本形式的简易地图查看功能。

// 次级功能：查询最短路径
void math() {
    AMGraph G;
    CreateMap(G);
    ShortestPath_Floyd(G);
    
    cout<<"1.北门 2.下沉广场 3.青年公寓 4.齐贤广场 5.15教"<<endl;
    cout<<"6.菜鸟驿站 7.汇森楼 8.图书馆 9.体育馆 10.南苑餐厅"<<endl;
    
    int a, b;
    cout<<"请输入起点序号: "; cin>>a;
    cout<<"请输入终点序号: "; cin>>b;
    
    // 数组下标从0开始，需减1
    int m = a - 1, n = b - 1;
    
    cout<<"最短距离:" <<shortPath[m][n]<<"米"<<endl;
    cout<<"具体路径: " <<G.vexs[m];
    
    // 根据Path数组回溯路径
    int k = Path[m][n];
    while(k != n) {
        cout<<" -> " <<G.vexs[k];
        k = Path[k][n];
    }
    cout<<" -> " <<G.vexs[n]<<endl;
}

// 显示简易ASCII地图
void scence() {
    cout<<"\t\t--------------------------------------------------------"<<endl;
    // ... (省略部分地图绘制代码，保持原样) ...
    cout<<"--------------------------------------------------------"<<endl;
}

int main() {
    char choice;
    cout<<"欢迎使用校园导航系统"<<endl;
    // ... (主菜单逻辑) ...
    return 0;
}

通过以上步骤，即可得到一个基础的命令行版校园导航程序。开发者可根据实际需求扩展地图规模，或将其图形化前端连接至后端逻辑。