校园导航问题（数据结构课设）（C语言版）
这个课题的代码原型来自我的一位同学，我对于图和网的操作不是十分熟悉，一些知识点已经忘掉了，所以复习也耽误了一些时间。程序整体优化程度不大，但是基本可以实现功能。
·
本文为数据结构与算法课设--《校园导航问题》课题的一个分享。采用图的结构进行存储数据和计算带权路线。
目录
1.设计内容与要求
|
设计内容： （1）设计学校的平面图（至少包括10个以上的场所）。每两个场所间可以有不同的路径，且路长也可能不同（图形结构要求通过键盘输入数据后采用创建图的算法生成图形）； （2）提供起始点与终点能自动找出从任意场所到达另一场所的最佳路径（最短路径，要求采用算法实现，不能直接指定）。 设计要求： (1) 符合课题要求，实现相应功能； (2) 要求界面友好美观，操作方便易行； (3) 注意程序的实用性、安全性； |
2.程序调试
逐个实现功能并最后退出。
3.代码实现
1.结构体与数据初始化
由于导航系统是归于一个固定的地址，并不需要用户自行键入，所以在全局变量里存储使用。
int visited[MAXSIZE];
char R[MAXSIZE][MAXSIZE] = {
{" 1 文涛九 "},
{" 2 龙山餐厅 "},
{" 3 十号教学楼 "},
{" 4 五号教学楼 "},
{" 5 图书馆 "},
{" 6 九号教学楼 "},
{" 7 瑾瑜国际会议中心 "},
{" 8 东区篮球场 "},
{" 9 主操场 "},
{" 10 十七号教学楼 "},
{" 11 十一号教学楼 "},
{" 12 行知广场 "},
{" 13 铁路主题公园 "},
{" 14 七道门 "},
{" 15 柏林园 "},
{" 16 第四食堂 "},
{" 17 怡丁苑 "},
{" 18 软件学院 "},
};
int A[MAXSIZE][MAXSIZE] = {
{0,200,250,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,800},
{200,0,50,INFINIFY,INFINIFY,INFINIFY,50,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY},
{250,50,0,50,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY},
{INFINIFY,INFINIFY,50,0,INFINIFY,INFINIFY,INFINIFY,100,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY},
{INFINIFY,INFINIFY,INFINIFY,INFINIFY,0,100,200,60,INFINIFY,INFINIFY,INFINIFY,1200,INFINIFY,INFINIFY,INFINIFY,50,INFINIFY,INFINIFY},
{INFINIFY,INFINIFY,INFINIFY,INFINIFY,100,0,INFINIFY,50,900,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY},
{INFINIFY,50,INFINIFY,INFINIFY,200,INFINIFY,0,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY},
{INFINIFY,INFINIFY,INFINIFY,100,60,50,INFINIFY,0,INFINIFY,700,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY},
{INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,900,INFINIFY,INFINIFY,0,50,500,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY},
{INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,50,INFINIFY,700,50,0,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY},
{INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,500,INFINIFY,0,100,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY},
{INFINIFY,50,INFINIFY,INFINIFY,1200,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,100,0,50,100,INFINIFY,INFINIFY,INFINIFY,INFINIFY},
{INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,100,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,50,0,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY},
{INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,100,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,100,INFINIFY,0,1000,INFINIFY,800,INFINIFY},
{INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,1000,0,500,INFINIFY,300},
{INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,500,0,100,INFINIFY},
{INFINIFY,INFINIFY,500,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,800,INFINIFY,100,0,INFINIFY},
{800,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,300,INFINIFY,INFINIFY,0},
};
int B[MAXSIZE] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18 };
typedef char DataType;
typedef int WeightType;
typedef struct //以下定义邻接矩阵类型
{
int number; //顶点编号
DataType xinxi; //顶点其他信息
}VertexType; //顶点类型
typedef struct
{
WeightType G[MAXSIZE][MAXSIZE]; //邻接矩阵数组
int Nv; //顶点数
int Ne; //边数
VertexType Data[MAXSIZE]; //存放顶点信息
}MGraph; //完整的图邻接矩阵类型
typedef struct ANode //定义邻接表类型
{
int Adjv; //该边的邻接点编号
struct ANode* Next; //指向下一条边的指针
WeightType weight; //该边的相关信息如权值（用整形表示）
}ENode; //边结点类型
typedef struct Vnode
{
DataType xinxi; //顶点其他信息
ENode* FirstEdge; //指向第一条边
}VNode; //邻接表头结点类型
typedef struct
{
VNode Adjlist[MAXSIZE]; //邻接表头结点数组
int Nv, Ne; //图中顶点数n和边数e
}LGraph;2. 地图查看与显示
void map()//地图查看
{
printf("\n");
printf("\n");
printf("***********************************************************************************************************************\t\t\t\t\t");
printf("\n");
printf("**----------------------------------------------------------(10)十七号教学楼----------------------------------------**\t\t\t\t\t");
printf("\n");
printf("**----------------------------------------------------------(9)主操场-----------------------------------------------**\t\t\t\t\t");
printf("\n");
printf("**---(8)东区篮球场-----------------------(6)九号教学楼------------------------------(11)十一号教学楼----------------**\t\t\t\t\t");
printf("\n");
printf("**-----------------------------------(5)图书馆------------------------(12)行知广场-----(13)铁路主题公园-------------**\t\t\t\t\t");
printf("\n");
printf("**---(4)五号教学楼-----------------------------------------------(14)七道门-----------------------------------------**\t\t\t\t\t");
printf("\n");
printf("**---(3)十号教学楼----------------(7)瑾瑜国际会议中心---------------------------------------------------------------**\t\t\t\t\t");
printf("\n");
printf("**-- (1)文涛九------------------(2)龙山餐厅-------------------------------------------------------------------------**\t\t\t\t\t");
printf("\n");
printf("**------------------------ (18)软件学院--------(15)柏林园-----------------(16)第四食堂-----(17)怡丁苑---------------**\t\t\t\t\t");
printf("\n");
printf("**********************************************************************************************************************\t\t\t\t\t");
printf("\n");
printf("\n");
}
3.起始点输入和最短路径查找
void Shortlu(MGraph g, int z, int& Nv, int B[MAXSIZE], char R[MAXSIZE][MAXSIZE])//找寻最短路径函数
{
int dist[MAXSIZE], path[MAXSIZE];
int S[MAXSIZE]; //S[i]=1表示顶点i在S中, S[i]=0表示顶点i在U中
int Mindis, i, j, u = 0;
for (i = 0; i < g.Ne; i++)
{
dist[i] = g.G[z][i]; //距离初始化
S[i] = 0; //S[]置空
if (g.G[z][i] < INFINIFY) //路径初始化
path[i] = z;
else
path[i] = -1;
}
S[z] = 1; path[z] = 0;
for (i = 0; i < g.Nv - 1; i++)
{
Mindis = INFINIFY;
for (j = 0; j < g.Nv; j++)
if (S[j] == 0 && dist[j] < Mindis)
{
u = j;
Mindis = dist[j];
}
S[u] = 1;
for (j = 0; j < g.Nv; j++)
if (S[j] == 0)
if (g.G[u][j] < INFINIFY && dist[u] + g.G[u][j] < dist[j])
{
dist[j] = dist[u] + g.G[u][j];
path[j] = u;
}
}
PutShortlu(g, dist, path, S, z, Nv, B, R); //输出最短路径
}
int input1() { //判断菜单输入的数 是否合理，不合理则再次输入
int m;
char n = 1;
scanf("%d", &m);
while (n)
{
if (m < 1 || m>8)
{
printf("输入错误,请再次输入:");
scanf("%d", &m);
}
else
n = 0;
}
return m;
}
void Bestlu(LGraph* G, int z, char R[MAXSIZE][MAXSIZE]) ///找寻最佳浏览路线函数
{
ENode* p;
int t[MAXSIZE];
int top = -1, y, x, i;
for (i = 0; i < G->Nv; i++)
visited[i] = 0; ///将访问标志均置为0,代表未访问过
printf("%s", R[z]); ///访问顶点v
visited[z] = 1; ///表示顶点v已被访问
top++;
t[top] = z; ///将顶点v进栈
while (top > -1) ///判断栈是否为空，为空则不进入循环
{
x = t[top]; ///取栈顶顶点x作为当前顶点
p = G->Adjlist[x].FirstEdge; ///找顶点x的第一个相邻点
while (p != NULL) ///判断节点是否为空
{
y = p->Adjv;
if (visited[y] == 0)
{
printf(" -> %s", R[y]);
visited[y] = 1;
top++;
t[top] = y;
break;
}
p = p->Next; ///找顶点x的下一个相邻点
}
if (p == NULL)
top--; ///若顶点x在没有相邻点，将其退栈
}
printf("\n");
}
4.邻接矩阵的输出
void CreateGraph(MGraph& g, int A[MAXSIZE][MAXSIZE], int Nv, int Ne) //创建图的邻接矩阵
{
int i, j;
g.Nv = Nv;
g.Ne = Ne;
for (i = 0; i < g.Nv; i++)
for (j = 0; j < g.Ne; j++)
g.G[i][j] = A[i][j];
}
void PutMGraph(MGraph g) //输出邻接矩阵g
{
int i, j;
for (i = 0; i < g.Nv; i++)
{
for (j = 0; j < g.Nv; j++)
if (g.G[i][j] != INFINIFY)
printf("%4d", g.G[i][j]);
else
printf("%4s", "∞");
printf("\n");
}
}
*5.完整代码
//
// main.cpp
// 校园导航问题
//
// Created by 1 on 2024/6/20.
//
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define INFINIFY 65535 //定义无穷大
#define MAXSIZE 100 //定义最大定点数
int visited[MAXSIZE];
char R[MAXSIZE][MAXSIZE] = {
{" 1 文涛九 "},
{" 2 龙山餐厅 "},
{" 3 十号教学楼 "},
{" 4 五号教学楼 "},
{" 5 图书馆 "},
{" 6 九号教学楼 "},
{" 7 瑾瑜国际会议中心 "},
{" 8 东区篮球场 "},
{" 9 主操场 "},
{" 10 十七号教学楼 "},
{" 11 十一号教学楼 "},
{" 12 行知广场 "},
{" 13 铁路主题公园 "},
{" 14 七道门 "},
{" 15 柏林园 "},
{" 16 第四食堂 "},
{" 17 怡丁苑 "},
{" 18 软件学院 "},
};
int A[MAXSIZE][MAXSIZE] = {
{0,200,250,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,800},
{200,0,50,INFINIFY,INFINIFY,INFINIFY,50,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY},
{250,50,0,50,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY},
{INFINIFY,INFINIFY,50,0,INFINIFY,INFINIFY,INFINIFY,100,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY},
{INFINIFY,INFINIFY,INFINIFY,INFINIFY,0,100,200,60,INFINIFY,INFINIFY,INFINIFY,1200,INFINIFY,INFINIFY,INFINIFY,50,INFINIFY,INFINIFY},
{INFINIFY,INFINIFY,INFINIFY,INFINIFY,100,0,INFINIFY,50,900,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY},
{INFINIFY,50,INFINIFY,INFINIFY,200,INFINIFY,0,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY},
{INFINIFY,INFINIFY,INFINIFY,100,60,50,INFINIFY,0,INFINIFY,700,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY},
{INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,900,INFINIFY,INFINIFY,0,50,500,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY},
{INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,50,INFINIFY,700,50,0,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY},
{INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,500,INFINIFY,0,100,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY},
{INFINIFY,50,INFINIFY,INFINIFY,1200,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,100,0,50,100,INFINIFY,INFINIFY,INFINIFY,INFINIFY},
{INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,100,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,50,0,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY},
{INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,100,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,100,INFINIFY,0,1000,INFINIFY,800,INFINIFY},
{INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,1000,0,500,INFINIFY,300},
{INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,500,0,100,INFINIFY},
{INFINIFY,INFINIFY,500,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,800,INFINIFY,100,0,INFINIFY},
{800,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,INFINIFY,300,INFINIFY,INFINIFY,0},
};
int B[MAXSIZE] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18 };
typedef char DataType;
typedef int WeightType;
typedef struct //以下定义邻接矩阵类型
{
int number; //顶点编号
DataType xinxi; //顶点其他信息
}VertexType; //顶点类型
typedef struct
{
WeightType G[MAXSIZE][MAXSIZE]; //邻接矩阵数组
int Nv; //顶点数
int Ne; //边数
VertexType Data[MAXSIZE]; //存放顶点信息
}MGraph; //完整的图邻接矩阵类型
typedef struct ANode //定义邻接表类型
{
int Adjv; //该边的邻接点编号
struct ANode* Next; //指向下一条边的指针
WeightType weight; //该边的相关信息如权值（用整形表示）
}ENode; //边结点类型
typedef struct Vnode
{
DataType xinxi; //顶点其他信息
ENode* FirstEdge; //指向第一条边
}VNode; //邻接表头结点类型
typedef struct
{
VNode Adjlist[MAXSIZE]; //邻接表头结点数组
int Nv, Ne; //图中顶点数n和边数e
}LGraph;
void Caidan()//菜单函数
{
printf(" ********************欢迎使用校园导航系统***********************");
printf(" \n 欢迎来到中北大学 ");
printf(" \n 菜单选择 ");
printf(" \n 1、学校地图查看 ");
printf(" \n 2、查询最短路径 ");
printf(" \n 3、打印邻接矩阵 ");
printf(" \n 4、退出系统 ");
printf(" \n***********************************************************");
printf("\n");
printf("请输入你的选择:");
}
void map()//地图查看
{
printf("\n");
printf("\n");
printf("***********************************************************************************************************************\t\t\t\t\t");
printf("\n");
printf("**----------------------------------------------------------(10)十七号教学楼----------------------------------------**\t\t\t\t\t");
printf("\n");
printf("**----------------------------------------------------------(9)主操场-----------------------------------------------**\t\t\t\t\t");
printf("\n");
printf("**---(8)东区篮球场-----------------------(6)九号教学楼------------------------------(11)十一号教学楼----------------**\t\t\t\t\t");
printf("\n");
printf("**-----------------------------------(5)图书馆------------------------(12)行知广场-----(13)铁路主题公园-------------**\t\t\t\t\t");
printf("\n");
printf("**---(4)五号教学楼-----------------------------------------------(14)七道门-----------------------------------------**\t\t\t\t\t");
printf("\n");
printf("**---(3)十号教学楼----------------(7)瑾瑜国际会议中心---------------------------------------------------------------**\t\t\t\t\t");
printf("\n");
printf("**-- (1)文涛九------------------(2)龙山餐厅-------------------------------------------------------------------------**\t\t\t\t\t");
printf("\n");
printf("**------------------------ (18)软件学院--------(15)柏林园-----------------(16)第四食堂-----(17)怡丁苑---------------**\t\t\t\t\t");
printf("\n");
printf("**********************************************************************************************************************\t\t\t\t\t");
printf("\n");
printf("\n");
}
int input1() { //判断菜单输入的数 是否合理，不合理则再次输入
int m;
char n = 1;
scanf("%d", &m);
while (n)
{
if (m < 1 || m>8)
{
printf("输入错误,请再次输入:");
scanf("%d", &m);
}
else
n = 0;
}
return m;
}
void Bestlu(LGraph* G, int z, char R[MAXSIZE][MAXSIZE]) ///找寻最佳浏览路线函数
{
ENode* p;
int t[MAXSIZE];
int top = -1, y, x, i;
for (i = 0; i < G->Nv; i++)
visited[i] = 0; ///将访问标志均置为0,代表未访问过
printf("%s", R[z]); ///访问顶点v
visited[z] = 1; ///表示顶点v已被访问
top++;
t[top] = z; ///将顶点v进栈
while (top > -1) ///判断栈是否为空，为空则不进入循环
{
x = t[top]; ///取栈顶顶点x作为当前顶点
p = G->Adjlist[x].FirstEdge; ///找顶点x的第一个相邻点
while (p != NULL) ///判断节点是否为空
{
y = p->Adjv;
if (visited[y] == 0)
{
printf(" -> %s", R[y]);
visited[y] = 1;
top++;
t[top] = y;
break;
}
p = p->Next; ///找顶点x的下一个相邻点
}
if (p == NULL)
top--; ///若顶点x在没有相邻点，将其退栈
}
printf("\n");
}
int input2(int& Nv, int B[MAXSIZE]) //输入函数2
{
int m, y = 0;
char n = 1;
scanf("%d", &m);
while (m != 88) ///判断输入是否进行循环
{
while (n)
{
if (m<1 || m>Nv) ///判断输入值的是否正确
{
printf("该地标节点不存在请重新输入:");
scanf("%d", &m); ///判断输入错误重新输入
}
if (B != NULL) ///判断一位数组B是否为空
{
for (int i = 0; i < MAXSIZE; i++) ///判断该数值是否存在于数组B
if (B[i] == m)
y++;
if (y <= 0)
{
printf("该地标节点不存在请重新输入:");
scanf("%d", &m); ///不存在则重新输入
}
else
n = 0; ///退出循环
}
else
n = 0;
}
break;
}
return m; ///返回输入值
}
void DestroyLGraph(LGraph* G)//销毁邻接表
{
ENode* pre, * p;
for (int i = 0; i < G->Nv; i++)
{
pre = G->Adjlist[i].FirstEdge;
if (pre != NULL)
{
p = pre->Next;
while (p != NULL)
{
free(pre);
pre = p;
p = p->Next;
}
free(pre);
}
}
free(G);
}
void CreateGraph(MGraph& g, int A[MAXSIZE][MAXSIZE], int Nv, int Ne) //创建图的邻接矩阵
{
int i, j;
g.Nv = Nv;
g.Ne = Ne;
for (i = 0; i < g.Nv; i++)
for (j = 0; j < g.Ne; j++)
g.G[i][j] = A[i][j];
}
void PutMGraph(MGraph g) //输出邻接矩阵g
{
int i, j;
for (i = 0; i < g.Nv; i++)
{
for (j = 0; j < g.Nv; j++)
if (g.G[i][j] != INFINIFY)
printf("%4d", g.G[i][j]);
else
printf("%4s", "∞");
printf("\n");
}
}
void PutShortlu(MGraph g, int dist[], int path[], int S[], int z, int& Nv, int B[MAXSIZE], char R[MAXSIZE][MAXSIZE]) //输出从顶点v出发的所有最短路径
{
int i, j, k;
int apath[MAXSIZE], d; //存放一条最短路径(逆向)及其顶点个数
printf("输入你要到达的地点：");
i = input2(Nv, B); //循环输出从顶点v到i的路径
i = i - 1;
if (S[i] == 1 && i != z)
{
printf(" 从地点%s到地点%s的最短路径长度为:%d\n 路径为:", R[z], R[i], dist[i]);
d = 0;
apath[d] = i;
k = path[i];
if (k == -1)
printf("无路径\n");
else
{
while (k != z)
{
d++;
apath[d] = k;
k = path[k];
}
d++;
apath[d] = z;
printf("%s", R[apath[d]]);
for (j = d - 1; j >= 0; j--)
printf("->%s", R[apath[j]]);
printf("\n");
}
}
}
void Shortlu(MGraph g, int z, int& Nv, int B[MAXSIZE], char R[MAXSIZE][MAXSIZE])//找寻最短路径函数
{
int dist[MAXSIZE], path[MAXSIZE];
int S[MAXSIZE]; //S[i]=1表示顶点i在S中, S[i]=0表示顶点i在U中
int Mindis, i, j, u = 0;
for (i = 0; i < g.Ne; i++)
{
dist[i] = g.G[z][i]; //距离初始化
S[i] = 0; //S[]置空
if (g.G[z][i] < INFINIFY) //路径初始化
path[i] = z;
else
path[i] = -1;
}
S[z] = 1; path[z] = 0;
for (i = 0; i < g.Nv - 1; i++)
{
Mindis = INFINIFY;
for (j = 0; j < g.Nv; j++)
if (S[j] == 0 && dist[j] < Mindis)
{
u = j;
Mindis = dist[j];
}
S[u] = 1;
for (j = 0; j < g.Nv; j++)
if (S[j] == 0)
if (g.G[u][j] < INFINIFY && dist[u] + g.G[u][j] < dist[j])
{
dist[j] = dist[u] + g.G[u][j];
path[j] = u;
}
}
PutShortlu(g, dist, path, S, z, Nv, B, R); //输出最短路径
}
int main() {
Caidan();
MGraph g;
LGraph* G;
int Nv = 18, Ne = 24;
int x, z;
x = input1();
while (1)
{
switch (x)
{
case 1:
Caidan();
printf("\n学校地图查看:");
map();
printf("\n已返回主菜单，请输入需要查询的菜单栏选项:\n");
printf("\n");
Caidan();
x = input1();
break;
case 2:
Caidan();
printf("输入所在位置，为你规划最短路径：");
CreateGraph(g, A, Nv, Ne);
z = input2(Nv, B) - 1;
Shortlu(g, z, Nv, B, R);
printf("\n已返回主菜单，请输入需要查询的菜单栏选项:\n");
printf("\n");
Caidan();
x = input1();
break;
case 3:
Caidan();
printf("\n打印邻接矩阵:\n");
CreateGraph(g, A, Nv, Ne);
PutMGraph(g);
printf("\n已返回主菜单，请输入需要查询的菜单栏选项:\n");
printf("\n");
Caidan();
x = input1();
break;
}
if (x == 4)
break;
}
printf("已退出系统\n");
return 1;
}
4.问题反思与总结
这个课题的代码原型来自我的一位同学，我对于图和网的操作不是十分熟悉，一些知识点已经忘掉了，所以复习也耽误了一些时间。程序整体优化程度不大，但是基本可以实现功能。
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
9
0- 0
已为社区贡献6条内容
所有评论(0)