数据结构之校园导航(弗洛伊德算法)

题目要求(校园导航):
设计要求:设计某某大学的平面图,至少包括10个以上的场所,每两个场所间可以有不同的路,且路长也可能不同,找出从任意场所到达另一场所的最佳路径(最短路径)。
基本要求:
(1)设计校园平面图,在校园景点选10个左右景点。以图中顶点表示校园内各景点,存放景点名称、代号、简介等信息;以边表示路径,存放路径长度等有关信息。
(2)为来访客人提供图中任意景点相关信息的查询。
(3)为来访客人提供任意景点的问路查询,即查询任意两个景点之间的一条最短路径。
实现提示:一般情况下,校园的道路是双向通行的,可设计校园平面图是一个无向网。顶点和边均含有相关信息。

解题思路和大纲
首先读完题目,我们能清晰的了解到他所用到的数据结构和算法,那么不考虑其他部分,核心算法的选择是一个重要的问题。我们可以了解到,求解每一对顶点之间的最短路径有两种方法:
其一是分别以图中的每个顶点为源点共调用n次迪杰斯特拉算法;
其二是采用下面介绍的弗洛伊德(Floyd)算法。
两种算法的时间复杂度均为0(n3),但后者形式上较简单,弗洛伊德算法仍然使用带权的邻接矩阵arcs来表示。不难看出,此处我们小组选择的是弗洛伊德算法,简单粗暴,一次性算出任意两个顶点的最短距离。为什么选择弗洛伊德算法,第一个原因是大家可能首选迪杰斯特拉算法,为了新颖,我们组选择了弗洛伊德算法。第二个原因就是上面说的,简单粗暴。

那么,万事开头难。其他部分怎么开始,怎么解决,同样是难题。接下来我们小组的做法是:

1从高德地图采集地点信息,建立无向网(如何建立)

2如何储存顶点信息、边的信息(顶点,边的定义)

3如何建立图信息(联系点和边)

4邻接表?邻接矩阵?(由核心算法决定)

5.菜单页面(如何设计)

6文件读取  

7核心算法选择(已解决)

此处我只介绍核心算法部分。MAX_VERTICES为点的总数。即循环的限制条件为顶的总数。

  // 弗洛伊德算法主循环
    for (k = 0; k < MAX_VERTICES; k++) {
        for (i = 0; i < MAX_VERTICES; i++) {
            for (j = 0; j < MAX_VERTICES; j++) {
                if (Edg[i][j] > (Edg[i][k] + Edg[k][j])) {
                    Edg[i][j] = (Edg[i][k] + Edg[k][j]);//k为中间地点 
                    path[i][j] = k; // 记录任意两地点之间的中间点 
                }
            }
        }
    }

 核心算法部分还有一个关键问题需要解决,如何输出最短路径。从核心代码部分,我们可以看出顶点i到顶点j之间可能有一个中间点k,也可能有两个,三个,或者更多。那么我们如何解决中间点k覆盖了顶点i到顶点j之间的点。其实很容易解决,如果能理解path[i][j]的关键作用,问题其实很简单。因为path数组存放了任意两点间的中间点。只需递归调用函数即可。

//递归显示最短路径
void show_ShortestPathRecursive(CampusMap* map, int i, int j, int intermediate) 
{
    if (intermediate == -1) {
        printf("----%s", map->vertices[j].name);//打印终点 
    } else {
        show_ShortestPathRecursive(map, i, intermediate, path[i][intermediate]);//递归i和intermediate点之间的中间点 
        show_ShortestPathRecursive(map, intermediate, j, path[intermediate][j]);//递归intermediate和j点之间的中间点
    }
}

当然除了核心算法部分,需要解决的问题有很多。其余部分不在解释,最后附上源代码,仅供参考。欢迎大家提意见指正,相互学习。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_VERTICES 10//最大地点 
#define INF 99999//无穷大 

//地点结构体 
typedef struct {
    char name[50];// 地点名字 
    char description[200];//地点简介 
}VertexInfo;

//无向网结构体 
typedef struct {
    VertexInfo vertices[MAX_VERTICES];//地点结构体数组
    int adjacencyMatrix[MAX_VERTICES][MAX_VERTICES];//邻接矩阵
    int numVertices;//地点个数
} CampusMap;

//全局变量方便函数直接使用、引用 
CampusMap campus;
int path[MAX_VERTICES][MAX_VERTICES];
int Edg[MAX_VERTICES][MAX_VERTICES];
 
//初始化无向网 
void initCampusMap(CampusMap* map) {
    map->numVertices = 0;
    for (int i = 0; i < MAX_VERTICES; ++i) {
        for (int j = 0; j < MAX_VERTICES; ++j) {
            if (i == j)
            {//自身到达自身为0
                map->adjacencyMatrix[i][j] = 0;
            }
            else 
            {
                map->adjacencyMatrix[i][j] = INF;
            }
        }
    }
}

//添加地点 
void addVertex(CampusMap* map, char name[], char description[]) {
    if (map->numVertices < MAX_VERTICES) {
        strcpy(map->vertices[map->numVertices].name, name);//地点名字
        strcpy(map->vertices[map->numVertices].description, description);//地点简介
        map->numVertices++;
    }
    else
	{//报错提醒 
        printf("Error: Too many vertices
");
    }
}
//添加边 
void addEdge(CampusMap* map, int start, int end, int length) {
    if (start >= 0 && start <map->numVertices && end >= 0 && end < map->numVertices) {
    	//无向边 
        map->adjacencyMatrix[start][end] = length;
        map->adjacencyMatrix[end][start] = length;
    }
    else 
	{//报错提醒 
        printf("Error: Invalid vertex indices
");
    } 
}
//以上是读取文件(点边图的初始化) 

//输出各地点名称
void print_address(CampusMap* map)
{
    int i = 0;
    for (i = 0; i < MAX_VERTICES; i++)
    {
        printf("%d--%s	", i+1, map->vertices[i].name);
    }
    printf("

");
}
//打印地图
void Creat_maps()
{
	printf("                    ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━东北门━━━━━━┓ 
");
	printf("                    ┃                                                                              ┃ 
");
	printf("【某某某某某某大学】|      二区篮球场                                                               ┃ 
");
	printf("                    ┃            o                                                                 ┃ 
");
	printf("                    ┃                                 三峡大坝岩心                                 ┃ 
");
	printf("                    ┃                                    o                                         ┃ 
");
	printf("  ┏━━━━━━━━━                                                    o 生活广场                 ┃ 
");
	printf("  ┃                                                                                                ┃ 
");
	printf("  ┃              二区餐厅                                                                          ┃ 
");
	printf("  ┃                  o                  第一报告厅                                   o 文体会堂        
");
	printf("  ┃                                          o                                                        
");
	printf("  ┃                     校医院                                                                       
");
	printf(" 西门                       o                                                                          
");
	printf("  ┃    近邻宝                                                                                         
");
	printf("  ┃      o                                                                                         ┃  
");
	printf("  ┃                                                                                                     
");
	printf("  ┃                                   o图书馆                                                           
");
	printf("                                                                                      ┃        
");
	printf("                                                                                      ┃        
");
	printf("                                                                            信息工程学院楼      ┃   
");
	printf("                                                                               o                      
") ;
	printf("                                                                                                   
") ; 
	printf("   ┗  ━━━━━━━━━━━━━━━  ━━━━━━━━━━━━━━━南大门━                           

");
	                    
}
//遍历地点,查找查询地点的简介。 
void Search(CampusMap* map,int a)
{
	printf("%s:%s
",map->vertices[a].name,map->vertices[a].description);
}
// 弗洛伊德算法求两点最小权值
void floyd(CampusMap* map) 
{
    int i, j, k;

    // 初始化路径矩阵、边矩阵 
    for (i = 0; i < MAX_VERTICES; i++) {
        for (j = 0; j < MAX_VERTICES; j++) 
		{
			Edg[i][j]=map->adjacencyMatrix[i][j]; //初始化Edg矩阵 
            path[i][j] = -1; // 初始路径为空
        }
    }
    // 弗洛伊德算法主循环
    for (k = 0; k < MAX_VERTICES; k++) {
        for (i = 0; i < MAX_VERTICES; i++) {
            for (j = 0; j < MAX_VERTICES; j++) {
                if (Edg[i][j] > (Edg[i][k] + Edg[k][j])) {
                    Edg[i][j] = (Edg[i][k] + Edg[k][j]);//k为中间地点 
                    path[i][j] = k; // 记录任意两地点之间的中间点 
                }
            }
        }
    }
}

// 递归显示最短路径
void show_ShortestPathRecursive(CampusMap* map, int i, int j, int intermediate) 
{
    if (intermediate == -1) {
        printf("----%s", map->vertices[j].name);//打印终点 
    } else {
        show_ShortestPathRecursive(map, i, intermediate, path[i][intermediate]);//递归i和intermediate点之间的中间点 
        show_ShortestPathRecursive(map, intermediate, j, path[intermediate][j]);//递归intermediate和j点之间的中间点
    }
}
// 显示最短路径
void show_ShortestPath(CampusMap* map, int i, int j) {
    printf("从 %s 到 %s 的最短路径为:
", map->vertices[i].name, map->vertices[j].name);
    printf("%s", map->vertices[i].name);//打印起点 

    if (path[i][j] != -1) 
	{ 
        show_ShortestPathRecursive(map, i, j, path[i][j]);//调用函数show_ShortestPathRecursive 
    }
    printf("
最短距离为:%d米。
", Edg[i][j]);//最短距离 
}

//打印最短距离邻接矩阵 
void print_adjacencyMatrix()
{
	int i=0;int j=0;
	for(i=0;i<MAX_VERTICES;i++)
	{
		for(j=0;j<MAX_VERTICES;j++)
		printf("%d  ",Edg[i][j]);
		printf("
");
	}
}
//主函数
int main() {
    initCampusMap(&campus);
    //文件读取数据 
    FILE *file;
	    file = fopen("shujujiegou.txt", "r");//打开文件 
	    if (file == NULL) {
	        printf("无法打开文件。
");
	        return 1;
	    }
	    
	    // 初始化点
	    int Vertexnum;
	    fscanf(file, "%d", &Vertexnum); //输入总顶点数
	    for (int i = 0; i < Vertexnum; i++) {
	        char address[50];//名字 
	        char dercription[200];//介绍 
	        fscanf(file, "%s %s", address, dercription);//文件读入 
	        addVertex(&campus, address, dercription);//调用添加点addVertex函数
	    }
	    
	    // 初始化边
	    int Edgnum;
	    fscanf(file, "%d", &Edgnum);//输入总边数 
	    for (int i = 0; i < Edgnum; i++) {
	        int start, end, length;//起点、终点、距离 
	        fscanf(file, "%d %d %d", &start, &end, &length);//文件读入 
	        addEdge(&campus, start, end, length);//调用添加边addEdge函数 
	    }
	    fclose(file);//关闭文件 
	    
    //调用Floyd函数 
    floyd(&campus);
    
    //菜单页面 
    printf("			           功能菜单
");
	printf("--------------------------------------------------------------------------------
");
    printf("		<1> 查看校园地图请输入1               		
");
	printf("		<2> 查看校园各地点代号请输入2         		
");
	printf("		<3> 最短路径查询请输入3               		
");
	printf("		<4> 查看存放最短路径的邻接矩阵请输入4 		
"); 
	printf("		<5> 退出系统请输入5                   		
");
	printf("------------------------------------------------------------------------------
");
     //遍历地点 
    print_address(&campus);
    //功能菜单 
    int choice;
		    do {
		    	printf("请输入对应功能的数字:
");
		        scanf("%d", &choice);
		        switch (choice) {
		        	case 1:
					   printf("地图如下:
");
					   Creat_maps ();//打印地图 
					   break;
		            case 2:
		                int value;
		                printf("请输入你要查询的地址:
");
		                scanf("%d", &value);
		                Search(&campus, value-1);//调用查找函数,查找地点相应简介。 
		                break;
		            case 3:
		                printf("请用户输入您要查询的路线(地点对应的序号):
");
		                int a_start, a_end;
		                scanf("%d %d", &a_start, &a_end);
		                show_ShortestPath(&campus, a_start-1 , a_end-1 );//调用显示最短路径函数 
		                break;
		            case 4:
		            	printf("打印最短距离的邻接矩阵:
");
		            	print_adjacencyMatrix();//调用遍历最短路径矩阵 
		            	break;
					case 5:
		                printf("退出菜单
");
		                break;
		            default:
		                printf("无效的选择,请重新输入
");
		        }
		    } while (choice != 5);
    return 0;
}