图的应用：校园导游系统（含Dijkstra和Floyd算法）

2023-12-04 08:08
文章标签 算法 系统 应用 导游 校园 dijkstra floyd

本文主要是介绍图的应用：校园导游系统（含Dijkstra和Floyd算法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！ 

/* 
问题描述：用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点， 
存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。 
要求能够回答有关景点介绍、游览路径等问题。 
基本要求：查询各景点的相关信息； 
查询图中任意两个景点间的最短路径； 
查询图中任意两个景点间的所有路径；增加、删除、更新有关景点和道路的信息。 
选作内容： 
1.求多个景点的最佳（最短）游览路径。 
2.区分机动车道和人行道。 
3.实现导游图的仿真界面。 注：很惭愧，有关基于邻接矩阵存储的无向图某两点之间的所有路径的相关算法我真的不会，另外由于时间关系选做的我也没做，对不起王阿川老师T_T 
*/  #include <iostream>  
#include <stdio.h>  
#include <string.h>  
#include <iomanip>  
#include <stdlib.h>  
#include <math.h>  
#define INFINITY 65535    //无穷大，即不相邻  
#define MAX_VERTEX_NUM 20 //最大的顶点个数  
using namespace std;  
typedef int VRType;  
typedef char InfoType;  typedef struct{  int num;  char name[20];  char introduce[100];  
}VertexType;  typedef struct ArcCell{  VRType adj; //距离  InfoType *info;//边的信息  
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  typedef struct {  VertexType vex[MAX_VERTEX_NUM];//顶点向量  AdjMatrix arcs; //邻接矩阵  int vexnum,arcnum; //顶点数和边数  
}MGraph;  void create(MGraph &g,VertexType site[])  
{  int i,j;  g.vexnum=11;  g.arcnum=12;  for(i=0;i<11;i++)  g.vex[i]=site[i];  for(i=0;i<g.vexnum;i++)  for(j=0;j<g.vexnum;j++)  g.arcs[i][j]={INFINITY,NULL};  g.arcs[0][1].adj=200;  g.arcs[1][2].adj=150;  g.arcs[2][3].adj=50;  g.arcs[3][4].adj=100;  g.arcs[4][5].adj=50;  g.arcs[5][9].adj=300;  g.arcs[6][7].adj=450;  g.arcs[6][9].adj=500;  g.arcs[0][4].adj=300;  g.arcs[0][7].adj=250;  g.arcs[9][10].adj=700;  g.arcs[7][8].adj=20;  for(i=0;i<g.vexnum;i++)  for(j=0;j<g.vexnum;j++)  g.arcs[j][i].adj= g.arcs[i][j].adj;  }  void output(MGraph g,int i)//根据序号i输出对应的景点的相关信息  
{  printf("景点序号：%d\n",i);  printf("景点名称：%s\n",g.vex[i-1].name);  printf("景点简介：%s\n",g.vex[i-1].introduce);  
}  void search(MGraph g)  
{  int i;  printf("请输入你想查找的景点的序号：\n");  scanf("%d",&i);  output(g,i);  
}  void Shortest_Path_Dijkstra(MGraph g,int v0,int P[][20],int D[20])  
{  int v,w,i,j,final[20],min;  for(v=0;v<g.vexnum;v++){  final[v]=0;  D[v]=g.arcs[v0][v].adj;  for(w=0;w<g.vexnum;w++)  P[v][w]=-1;  if(D[v]<INFINITY)  {  P[v][0]=v0;  P[v][1]=v;  }  }  D[v0]=0;  final[v0]=1;  for(i=1;i<g.vexnum;i++){  min=INFINITY;  for(w=0;w<g.vexnum;w++)  if(!final[w]&&D[w]<min)  {  v=w;  min=D[w];  }  final[v]=1;  for(w=0;w<g.vexnum;w++)  if(!final[w]&&(min+g.arcs[v][w].adj<D[w])){  D[w]=min+g.arcs[v][w].adj;  for(j=0;j<g.vexnum;j++)  {  P[w][j]=P[v][j];  if(P[w][j]==-1)//在p[w][]第一个等于-1的地方加上顶点w  {  P[w][j]=w;  break;  }  }  }  }  
}  void ShortestPath_FLOYD(MGraph g, int P[20][20][20], int D[][20])  
{  int u,v,w,i,j;  for(v=0;v<g.vexnum;v++)  for(w=0;w<g.vexnum;w++)  {  D[v][w]=g.arcs[v][w].adj;  for(u=0; u<g.vexnum;u++)  P[v][w][u]=-1;  if(D[v][w]<INFINITY)  {  P[v][w][0]=v;  P[v][w][1]=w;  }  }  for(u=0;u<g.vexnum;u++)  for(v=0;v<g.vexnum;v++)  for(w=0;w<g.vexnum;w++)  if(D[v][u]<INFINITY&&D[u][w]<INFINITY&&D[v][u]+D[u][w]<D[v][w])  {  //更新D  D[v][w]=D[v][u]+D[u][w];  //更新p，从v到w的路径是从v到u，再从u到w的所有路径  for(i=0;i<g.vexnum;i++)  {  if(P[v][u][i]!=-1)  P[v][w][i]=P[v][u][i];  else  break;  }  for(j=1;j<g.vexnum;j++)//注意：这里j从1开始而不是从0开始，因为从v到u的路径最后一个顶点是u, 而从u到w的路径第一个顶点是u，只需打印u一次即可。  {  if(P[u][w][j]!=-1)  P[v][w][i++]=P[u][w][j];  else  break;  }  }  }  void update(MGraph &g)  
{  int i;  printf("请输入你想查找的景点的序号：\n");  scanf("%d",&i);  if(i>=1&&i<=11)  {  printf("请输入新的景点名称：\n");  scanf("%s",g.vex[i-1].name);  printf("请输入新的景点名称简介：\n");  scanf("%s",g.vex[i-1].introduce);  }  
}  void add_arc(MGraph &g)  
{  int v1,v2,n;  printf("请输入你想增加的边两端的顶点序号：\n");  printf("请输入第一个顶点号：\n");  scanf("%d",&v1);  printf("请输入第二个顶点号：\n");  scanf("%d",&v2);  if(g.arcs[v1-1][v2-1].adj==INFINITY)  {  printf("请输入两点之间的距离：\n");  scanf("%d",&g.arcs[v1-1][v2-1].adj);  g.arcs[v2-1][v1-1].adj=g.arcs[v1-1][v2-1].adj;  printf("增加成功！\n");  }  else  {  
LL0:    printf("这两点已经有路径存在了，你想要修改它吗？想的话请按1，不想请按2：\n");  scanf("%d",&n);  if(n==1)  {  printf("请输入两点之间的新的距离：\n");  scanf("%d",&g.arcs[v1-1][v2-1].adj);  g.arcs[v2-1][v1-1].adj=g.arcs[v1-1][v2-1].adj;  printf("修改成功！\n");  }  else if(n==2)  {  printf("增加失败，呜呜呜T_T\n");  }  else  {  printf("你的输入有误，请重新输入！\n");  goto LL0;  }  }  
}  void delete_arc(MGraph &g)  
{  int v1,v2;  printf("请输入你想删除的边两端的顶点序号：\n");  printf("请输入第一个顶点号：\n");  scanf("%d",&v1);  printf("请输入第二个顶点号：\n");  scanf("%d",&v2);  if(g.arcs[v1-1][v2-1].adj!=INFINITY)  {  g.arcs[v1-1][v2-1].adj=g.arcs[v2-1][v1-1].adj=INFINITY;  printf("删除成功！\n");  }  else  {  printf("删除失败！这两个点之间本来就没有直接通路，你还删它干嘛？？？\n");  }  
}  void display_num(MGraph g)  
{  int i;  printf("景点序号   景点名称\n");  for(i=0;i<g.vexnum;i++)  {  if(i+1<10)  printf("%d          %s\n",g.vex[i].num,g.vex[i].name);  else  printf("%d         %s\n",g.vex[i].num,g.vex[i].name);  }  
}  void display_all(MGraph g)  
{  int i;  printf("景点序号   景点名称            景点简介\n");  for(i=0;i<g.vexnum;i++)  {  if(i+1<10)  printf("%d          %s          %s\n",g.vex[i].num,g.vex[i].name,g.vex[i].introduce);  else  printf("%d         %s         %s\n",g.vex[i].num,g.vex[i].name,g.vex[i].introduce);  }  
}  void menu()  
{  printf("\n1.显示所有景点的序号\n");  printf("2.查询所有景点的信息\n");  printf("3.查询某个景点的信息\n");  printf("4.查询某个景点到其他景点的最短路径\n");  printf("5.输出任意两个景点之间的最短路径\n");  printf("6.增加某一条边\n");  printf("7.删除某一条边\n");  printf("8.修改某一条边\n");  printf("9.退出系统\n");  
}  int main()  
{  int v1,v2,P1[20][20],P2[20][20][20],D1[20],D2[20][20],i,j,k;  MGraph g;  VertexType site[11]={  {1,"主楼","林学院和土木学院的老巢"},  {2,"理学楼","理学院老师和学生办公和上课的地方"},  {3,"动资楼","动资院的老巢"},  {4,"锦绣楼","马克思和外院最喜欢上课的地方"},  {5,"丹青楼","我现在就在丹青9楼苦逼的敲代码"},  {6,"行政楼","李大大办公的地方"},  {7,"操场","情侣们秀恩爱的最佳去处"},  {8,"9A学生公寓","信息学院男生的窝"},  {9,"老食堂","味道比新食堂好那么一点点"},  {10,"体育馆","大一上乒乓球的时候去过，听说郭德纲也去踩了踩"},  {11,"新食堂","难吃"}  };  create(g,site);  printf("欢迎来到校园导游系统！\n");  
LL1:menu();  printf("\n请输入你的选择：\n");  scanf("%d",&i);  switch(i)  {  case 1:  display_num(g);  goto LL1;  break;  case 2:  display_all(g);  goto LL1;  break;  case 3:  search(g);  goto LL1;  break;  case 4:  printf("请输入景点的序号：\n");  scanf("%d",&k);  Shortest_Path_Dijkstra(g,k-1,P1,D1);  for(i=1;i<g.vexnum;i++){  printf("%d号(%s)到%d号(%s)：",k,g.vex[k-1].name,i+1,g.vex[i].name);  for(j=0;P1[i][j]!=-1;j++)  printf("%d号(%s)  ",P1[i][j]+1,g.vex[P1[i][j]].name);  printf("\n距离为：%d\n",D1[i]);  puts("");  }  goto LL1;  break;  case 5:  ShortestPath_FLOYD(g,P2,D2);  for(i=0; i<g.vexnum; i++)  {  for(int j=0; j<g.vexnum; j++)  {  if(i!=j)  {  if(D2[i][j]!=INFINITY)  {  cout<<g.vex[i].name<<"到"<<g.vex[j].name<<"的最短长度为："<<setw(5)<<D2[i][j]<<", 最短路径为：";  for(int k=0; k<g.vexnum; k++)  {  if(P2[i][j][k]!=-1)  cout<<g.vex[P2[i][j][k]].name<<" ";  else  break;  }  puts("");  }  else  cout<<g.vex[i].name<<"到"<<g.vex[j].name<<"不可达"<<endl;  }  }  puts("");  }  goto LL1;  break;  case 6:  add_arc(g);  goto LL1;  break;  case 7:  delete_arc(g);  goto LL1;  break;  case 8:  update(g);  goto LL1;  break;  case 9:  printf("谢谢你的使用，寨见!\n");  exit(0);  goto LL1;  break;  default:  printf("你的输入有误，请重新输入！\n");  goto LL1;  break;  }  
}



这篇关于图的应用：校园导游系统（含Dijkstra和Floyd算法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/452760。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
中文分词jieba库的使用与实景应用（一）

中文分词jieba库的使用与实景应用（一）

知识星球：https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义： 精确模式（默认模式）： 全模式： 搜索引擎模式： paddle 模式（基于深度学习的分词模式）： 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取
阅读更多...
基于人工智能的图像分类系统

基于人工智能的图像分类系统

目录 引言项目背景环境准备 硬件要求软件安装与配置系统设计 系统架构关键技术代码示例 数据预处理模型训练模型预测应用场景结论 1. 引言 图像分类是计算机视觉中的一个重要任务，目标是自动识别图像中的对象类别。通过卷积神经网络（CNN）等深度学习技术，我们可以构建高效的图像分类系统，广泛应用于自动驾驶、医疗影像诊断、监控分析等领域。本文将介绍如何构建一个基于人工智能的图像分类系统，包括环境
阅读更多...
水位雨量在线监测系统概述及应用介绍

水位雨量在线监测系统概述及应用介绍

在当今社会，随着科技的飞速发展，各种智能监测系统已成为保障公共安全、促进资源管理和环境保护的重要工具。其中，水位雨量在线监测系统作为自然灾害预警、水资源管理及水利工程运行的关键技术，其重要性不言而喻。 一、水位雨量在线监测系统的基本原理 水位雨量在线监测系统主要由数据采集单元、数据传输网络、数据处理中心及用户终端四大部分构成，形成了一个完整的闭环系统。 数据采集单元：这是系统的“眼睛”，
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
hdu1394(线段树点更新的应用)

hdu1394(线段树点更新的应用)

题意：求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质，在0到n-1这些数字组成的乱序排列，将第一个数字A移到最后一位，得到的逆序数为res-a+(n-a-1) 知道上面的知识点后，可以用暴力来解 代码如下： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in
阅读更多...
嵌入式QT开发：构建高效智能的嵌入式系统

嵌入式QT开发：构建高效智能的嵌入式系统

摘要： 本文深入探讨了嵌入式 QT 相关的各个方面。从 QT 框架的基础架构和核心概念出发，详细阐述了其在嵌入式环境中的优势与特点。文中分析了嵌入式 QT 的开发环境搭建过程，包括交叉编译工具链的配置等关键步骤。进一步探讨了嵌入式 QT 的界面设计与开发，涵盖了从基本控件的使用到复杂界面布局的构建。同时也深入研究了信号与槽机制在嵌入式系统中的应用，以及嵌入式 QT 与硬件设备的交互，包括输入输出设
阅读更多...
JAVA智听未来一站式有声阅读平台听书系统小程序源码

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来，一站式有声阅读平台听书系统 🌟&nbsp;开篇：遇见未来，从“智听”开始 在这个快节奏的时代，你是否渴望在忙碌的间隙，找到一片属于自己的宁静角落？是否梦想着能随时随地，沉浸在知识的海洋，或是故事的奇幻世界里？今天，就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统，它正悄悄改变着我们的阅读方式，让未来触手可及！ 📚&nbsp;第一站：海量资源，应有尽有 走进“智听
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2