“校园导航”实验

一、实验目的与要求：

（一）实验目的

1、掌握图形结构的（邻接矩阵）输入方法

2、掌握图形结构的说明、创建以及图的存储表示

3、掌握最短路径算法原理

4、掌握最短路径的实现方法

（二）实验要求

1、熟悉C/C 语言编程

2、熟练使用C/C 语言实现图形结构的说明、创建以及图的存储表示

二、实验内容：

校园导航问题

（一）问题描述：

设计校园的平面图，至少包括8个以上的场所，每两个场所间可以有不同的路，且路长也可能不同。

1.（必做）找出从一个场所出发到达其它所有场所的最佳路径（最短路径）。

2.（选做）找出从任意场所到达另一场所的最佳路径（最短路径）。

（二） 基本要求

1、设计校园平面图，在校园景点选8个以上的景点。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。

2、为来访客人提供图中任意景点相关信息的查询。

3、为来访客人提供任意景点的问路查询。

（如：从学校1号门到各景点的最佳路线及距离；主楼到湖边餐厅的最佳路线及距离。）

4、界面要求：有合理提示；每个功能可以设立菜单；根据提示，可以完成相关的功能要求

3、熟练应用图形数据结构编程实现最短路径的算法

三、实验步骤与过程：

[介绍实验过程、算法描述及解题思路等]

[实验代码清单(要有注释语句)]

实验过程：

    先对实验要求进行一个脑中的呈现。如：输出格式，菜单页面，所需算法等等。再根据所想的算法进行代码实现。最后，对输出格式进行修改及完善即可。

算法描述：

  Dijkstra算法是一个基于「贪心」、「广度优先搜索」、「动态规划」求一个图中一个点到其他所有点的最短路径的算法，时间复杂度O(n^2)。 （可以解决问题一）

  Floyd算法是一个基于「贪心」、「动态规划」求一个图中所有点到所有点最短路径的算法，时间复杂度O(n^3)。（可以解决问题二）

解题思路：

  看到第一问和第二问就很容易想到了Dijkstra算法和Floyd算法去实现，所以就去实现这个两个算法即可。

代码呈现：

功能一：对各个场所进行简单描述

注：对于这个其实也可以创建一个顶点的结构体，包含char str[MAX]去存放场所信息。

1.  
   //各个场所的功能函数
2.  
   void feature()
3.  
   {
4.  
   hint();
5.  
   printf("请输入场所编号: ");
6.  
   int num;
7.  
   scanf("%d",&num);
8.  
   switch (num)
9.  
   {
10.  
    case 1:
11.  
    printf("宿舍有公共厨房，公共阅览室，公共厕所\n\n");
12.  
    break;
13.  
    case 2:
14.  
    printf("一食堂有丰富的菜品\n\n");
15.  
    break;
16.  
    case 3:
17.  
    printf("湖滨餐厅有中西方菜品\n\n");
18.  
    break;
19.  
    case 4:
20.  
    printf("图书馆设施好，学习氛围浓烈\n\n");
21.  
    break;
22.  
    case 5:
23.  
    printf("实验楼有实验室以及机房\n\n");
24.  
    break;
25.  
    case 6:
26.  
    printf("可以在里面举办一些晚会\n\n");
27.  
    break;
28.  
    case 7:
29.  
    printf("老师办公区域\n\n");
30.  
    break;
31.  
    case 8:
32.  
    printf("看主楼的最好位置\n\n");
33.  
    break;
34.  
    default:
35.  
    printf("无该场所编号，请重新输入场所编号\n\n");
36.  
    break;
37.  
    }
38.  
    }

功能二：找出从一个场所出发到达其它所有场所的最佳路径（dilkstra算法）

1.  
   //取最小值的函数
2.  
   int getMin(int* d,int* s,Graph* G)
3.  
   {
4.  
   int min=MAX;
5.  
   int index;
6.  
   for(int i=0;i<G->vexNum;i )
7.  
   {
8.  
   if(!s[i] && d[i]<min) //比较权值
9.  
   {
10.  
    min=d[i];
11.  
    index=i;
12.  
    }
13.  
    }
14.  
    return index;
15.  
    }
16.  
     
17.  
    void dijkstra(Graph* G,int index) //index为目标节点
18.  
    {
19.  
    /*
20.  
    最短路径(dijkstra算法)：
21.  
    准备辅助数组：
22.  
    S数组：记录了目标顶点到其他顶点的最短路径是否求得
23.  
    P数组：记录了目标顶点到其他顶点的最短路径的前驱节点
24.  
    D数组：记录了目标顶点到其他顶点的最短路径长度
25.  
    */
26.  
    int* s=(int*)malloc(sizeof(int)*G->vexNum);
27.  
    int* p=(int*)malloc(sizeof(int)*G->vexNum);
28.  
    int* d=(int*)malloc(sizeof(int)*G->vexNum);
29.  
    //对辅助数组进行初始化
30.  
    for(int i=0;i<G->vexNum;i )
31.  
    {
32.  
    if(G->arcs[index][i]>0 && G->arcs[index][i]!=MAX)
33.  
    {
34.  
    d[i]=G->arcs[index][i];
35.  
    p[i]=index;
36.  
    }
37.  
    else
38.  
    {
39.  
    d[i]=MAX;
40.  
    p[i]=-1;
41.  
    }
42.  
    if(i==index)
43.  
    {
44.  
    s[i]=1;
45.  
    d[i]=0;
46.  
    }
47.  
    else
48.  
    {
49.  
    s[i]=0;
50.  
    }
51.  
    }
52.  
    for(int i=0;i<G->vexNum-1;i )
53.  
    {
54.  
    int index=getMin(d,s,G);
55.  
    s[index]=1; //代表已经找到了最小路径
56.  
    for(int j=0;j<G->vexNum;j )
57.  
    {
58.  
    if(!s[j] && d[index] G->arcs[index][j]<d[j]) //判断是否要重新更新d数组中的最小路径
59.  
    {
60.  
    d[j]=d[index] G->arcs[index][j];
61.  
    p[j]=index; //更改
62.  
    }
63.  
    }
64.  
    }
65.  
    //输出到达个点的最短路径
66.  
    for(int i=0;i<=G->vexNum-1;i )
67.  
    {
68.  
    int j=i;
69.  
    printf("%s <—— ",G->vexs[i].name); //最后打印所到场所
70.  
    while(j!=index)
71.  
    {
72.  
    j=p[j];
73.  
    if(j!=index)
74.  
    {
75.  
    printf("%s <—— ",G->vexs[j].name);
76.  
    }
77.  
    }
78.  
    printf("%s",G->vexs[index].name);
79.  
    printf("\n%s --> %s的最短路径大小为：%d分钟",G->vexs[index].name,G->vexs[i].name,d[i]);
80.  
    printf("\n");
81.  
    }
82.  
    }

功能三：找出从一个场所出发到达其它所有场所的最佳路径（floyd算法）

1.  
   /*
2.  
   floyd算法(3 for:[n*n*n]):求每一对顶点之间的最短路径
3.  
   d数组:保存了两点的最短路径长度(权值)
4.  
   p数组:保存了两点之间最短路径前驱
5.  
   核心:试探法，通过加入不同的点进行中转，选择出最优解
6.  
   */
7.  
   void floyd(Graph* G,int f,int n)
8.  
   {
9.  
   int d[G->vexNum][G->vexNum];
10.  
    int p[G->vexNum][G->vexNum];
11.  
    //数组的初始化
12.  
    for(int i=0;i<G->vexNum;i )
13.  
    {
14.  
    for(int j=0;j<G->vexNum;j )
15.  
    {
16.  
    d[i][j]=G->arcs[i][j];
17.  
    if(G->arcs[i][j]>0 && G->arcs[i][j]!=MAX) //两个顶点之间有弧
18.  
    {
19.  
    p[i][j]=i; //有弧指向前继顶点
20.  
    }
21.  
    else
22.  
    {
23.  
    p[i][j]=-1;
24.  
    }
25.  
    }
26.  
    }
27.  
    /*
28.  
    进行试探法:第一个循环代表着加入的顶点进行试探
29.  
    后两个循环代表着每一对顶点
30.  
    */
31.  
    for(int i=0;i<G->vexNum;i )
32.  
    {
33.  
    for(int j=0;j<G->vexNum;j )
34.  
    {
35.  
    for(int k=0;k<G->vexNum;k )
36.  
    {
37.  
    if(d[j][i] d[i][k]<d[j][k])
38.  
    {
39.  
    d[j][k]=d[j][i] d[i][k];
40.  
    p[j][k]=p[i][k];
41.  
    }
42.  
    }
43.  
    }
44.  
    }
45.  
    printf("%s --> %s的最小路径为：%d分钟\n",G->vexs[f].name,G->vexs[n].name,d[f][n]);
46.  
    int l=p[f][n]; // l作为中间变量用来接受最短路径中的父亲节点
47.  
    printf("最短路径为: %s",G->vexs[f].name); // 输出最短路径
48.  
    int temp=0; //创建一个中间变量，便于储存l值
49.  
    while(l!=f)
50.  
    {
51.  
    printf(" --> %s",G->vexs[l].name);
52.  
    if(l==temp) //当后一个l等于前一个l时，循环截至
53.  
    break;
54.  
    l=p[l][n]; // 不断更新l节点
55.  
    temp=l;
56.  
    }
57.  
    printf(" --> %s\n\n",G->vexs[n].name);
58.  
     
59.  
    }

完整代码：

1.  
   #include<stdio.h>
2.  
   #include<stdlib.h>
3.  
   #include<string.h>
4.  
   #include<windows.h>
5.  
    
6.  
   /*图顶点之间不通，那么邻接矩阵的值为MAX
7.  
   如果顶点是自己本身，那么值为0*/
8.  
   #define MAX 32767
9.  
    
10.  
    int system(const char *command);//
11.  
     
12.  
    //结构体定义顶点
13.  
    typedef struct Vertex
14.  
    {
15.  
    int num; //顶点编号
16.  
    char name[MAX]; //顶点名称
17.  
    }Vertex;
18.  
     
19.  
    typedef struct Graph{
20.  
    Vertex vexs[9]; //顶点
21.  
    int** arcs; //权重(使用**目的表示矩阵)
22.  
    int vexNum;
23.  
    int arcsNum;
24.  
    }Graph;
25.  
     
26.  
    //初始化一个图
27.  
    Graph* initGraph(int vexNum)
28.  
    {
29.  
    Graph* G=(Graph*)malloc(sizeof(Graph));
30.  
    G->arcs=(int**)malloc(sizeof(int*) *vexNum);
31.  
    for(int i=0;i<vexNum;i )
32.  
    {
33.  
    G->arcs[i]=(int*)malloc(sizeof(int) *vexNum);
34.  
    }
35.  
    for(int i=1;i<=G->vexNum;i )
36.  
    G->vexs[i].num=i; //初始化顶点编号为1-10
37.  
    G->vexNum=vexNum;
38.  
    G->arcsNum=0;
39.  
    strcpy(G->vexs[0].name,"宿舍");
40.  
    strcpy(G->vexs[1].name,"一食堂");
41.  
    strcpy(G->vexs[2].name,"湖滨餐厅");
42.  
    strcpy(G->vexs[3].name,"图书馆");
43.  
    strcpy(G->vexs[4].name,"二号实验楼");
44.  
    strcpy(G->vexs[5].name,"礼堂");
45.  
    strcpy(G->vexs[6].name,"主楼");
46.  
    strcpy(G->vexs[7].name,"一号门");
47.  
    return G;
48.  
    }
49.  
     
50.  
    //构建一个图
51.  
    void createGraph(Graph* G,int* arcs)
52.  
    {
53.  
    for(int i=0;i<G->vexNum;i )
54.  
    {
55.  
    for(int j=0;j<G->vexNum;j )
56.  
    {
57.  
    G->arcs[i][j]=*(arcs i*G->vexNum j);
58.  
    if(G->arcs[i][j]!=0&&G->arcs[i][j]!=MAX)
59.  
    {
60.  
    G->arcsNum ;
61.  
    }
62.  
    }
63.  
    }
64.  
    G->arcsNum=G->arcsNum/2;
65.  
    }
66.  
     
67.  
    //取最小值的函数
68.  
    int getMin(int* d,int* s,Graph* G)
69.  
    {
70.  
    int min=MAX;
71.  
    int index;
72.  
    for(int i=0;i<G->vexNum;i )
73.  
    {
74.  
    if(!s[i] && d[i]<min) //比较权值
75.  
    {
76.  
    min=d[i];
77.  
    index=i;
78.  
    }
79.  
    }
80.  
    return index;
81.  
    }
82.  
     
83.  
    void dijkstra(Graph* G,int index) //index为目标节点
84.  
    {
85.  
    /*
86.  
    最短路径(dijkstra算法)：
87.  
    准备辅助数组：
88.  
    S数组：记录了目标顶点到其他顶点的最短路径是否求得
89.  
    P数组：记录了目标顶点到其他顶点的最短路径的前驱节点
90.  
    D数组：记录了目标顶点到其他顶点的最短路径长度
91.  
    */
92.  
    int* s=(int*)malloc(sizeof(int)*G->vexNum);
93.  
    int* p=(int*)malloc(sizeof(int)*G->vexNum);
94.  
    int* d=(int*)malloc(sizeof(int)*G->vexNum);
95.  
    //对辅助数组进行初始化
96.  
    for(int i=0;i<G->vexNum;i )
97.  
    {
98.  
    if(G->arcs[index][i]>0 && G->arcs[index][i]!=MAX)
99.  
    {
100.  
     d[i]=G->arcs[index][i];
101.  
     p[i]=index;
102.  
     }
103.  
     else
104.  
     {
105.  
     d[i]=MAX;
106.  
     p[i]=-1;
107.  
     }
108.  
     if(i==index)
109.  
     {
110.  
     s[i]=1;
111.  
     d[i]=0;
112.  
     }
113.  
     else
114.  
     {
115.  
     s[i]=0;
116.  
     }
117.  
     }
118.  
     for(int i=0;i<G->vexNum-1;i )
119.  
     {
120.  
     int index=getMin(d,s,G);
121.  
     s[index]=1; //代表已经找到了最小路径
122.  
     for(int j=0;j<G->vexNum;j )
123.  
     {
124.  
     if(!s[j] && d[index] G->arcs[index][j]<d[j]) //判断是否要重新更新d数组中的最小路径
125.  
     {
126.  
     d[j]=d[index] G->arcs[index][j];
127.  
     p[j]=index; //更改
128.  
     }
129.  
     }
130.  
     }
131.  
     //输出到达个点的最短路径
132.  
     for(int i=0;i<=G->vexNum-1;i )
133.  
     {
134.  
     int j=i;
135.  
     printf("%s <—— ",G->vexs[i].name); //最后打印所到场所
136.  
     while(j!=index)
137.  
     {
138.  
     j=p[j];
139.  
     if(j!=index)
140.  
     {
141.  
     printf("%s <—— ",G->vexs[j].name);
142.  
     }
143.  
     }
144.  
     printf("%s",G->vexs[index].name);
145.  
     printf("\n%s --> %s的最短路径大小为：%d分钟",G->vexs[index].name,G->vexs[i].name,d[i]);
146.  
     printf("\n");
147.  
     }
148.  
     }
149.  
      
150.  
     /*
151.  
     floyd算法(3 for:[n*n*n]):求每一对顶点之间的最短路径
152.  
     d数组:保存了两点的最短路径长度(权值)
153.  
     p数组:保存了两点之间最短路径前驱
154.  
     核心:试探法，通过加入不同的点进行中转，选择出最优解
155.  
     */
156.  
     void floyd(Graph* G,int f,int n)
157.  
     {
158.  
     int d[G->vexNum][G->vexNum];
159.  
     int p[G->vexNum][G->vexNum];
160.  
     //数组的初始化
161.  
     for(int i=0;i<G->vexNum;i )
162.  
     {
163.  
     for(int j=0;j<G->vexNum;j )
164.  
     {
165.  
     d[i][j]=G->arcs[i][j];
166.  
     if(G->arcs[i][j]>0 && G->arcs[i][j]!=MAX) //两个顶点之间有弧
167.  
     {
168.  
     p[i][j]=i; //有弧指向前继顶点
169.  
     }
170.  
     else
171.  
     {
172.  
     p[i][j]=-1;
173.  
     }
174.  
     }
175.  
     }
176.  
     /*
177.  
     进行试探法:第一个循环代表着加入的顶点进行试探
178.  
     后两个循环代表着每一对顶点
179.  
     */
180.  
     for(int i=0;i<G->vexNum;i )
181.  
     {
182.  
     for(int j=0;j<G->vexNum;j )
183.  
     {
184.  
     for(int k=0;k<G->vexNum;k )
185.  
     {
186.  
     if(d[j][i] d[i][k]<d[j][k])
187.  
     {
188.  
     d[j][k]=d[j][i] d[i][k];
189.  
     p[j][k]=p[i][k];
190.  
     }
191.  
     }
192.  
     }
193.  
     }
194.  
     printf("%s --> %s的最小路径为：%d分钟\n",G->vexs[f].name,G->vexs[n].name,d[f][n]);
195.  
     int l=p[f][n]; // l作为中间变量用来接受最短路径中的父亲节点
196.  
     printf("最短路径为: %s",G->vexs[f].name); // 输出最短路径
197.  
     int temp=0; //创建一个中间变量，便于储存l值
198.  
     while(l!=f)
199.  
     {
200.  
     printf(" --> %s",G->vexs[l].name);
201.  
     if(l==temp) //当后一个l等于前一个l时，循环截至
202.  
     break;
203.  
     l=p[l][n]; // 不断更新l节点
204.  
     temp=l;
205.  
     }
206.  
     printf(" --> %s\n\n",G->vexs[n].name);
207.  
      
208.  
     }
209.  
      
210.  
     void menu()
211.  
     {
212.  
     printf("**************************************************************\n");
213.  
     printf(" 深圳北理莫斯科大学校园导航 \n");
214.  
     printf("**************************************************************\n");
215.  
     printf("**** 1.查询找出从一个场所出发到达其它所有场所的最佳路径 ****\n");
216.  
     printf("**** 2.查询找出从任意场所到达另一场所的最佳路径 ****\n");
217.  
     printf("**** 3.查询各个场所的功能 ****\n");
218.  
     printf("**** 4.清屏 ****\n");
219.  
     printf("**** 0.退出程序 ****\n");
220.  
     printf("**************************************************************\n");
221.  
     }
222.  
      
223.  
     void hint()
224.  
     {
225.  
     printf("1-宿舍 2-一食堂 3-湖滨餐厅 4-图书馆\n");
226.  
     printf("5-二号实验楼 6-礼堂 7-主楼 8-一号门\n");
227.  
     }
228.  
      
229.  
     //各个场所的功能函数
230.  
     void feature()
231.  
     {
232.  
     hint();
233.  
     printf("请输入场所编号: ");
234.  
     int num;
235.  
     scanf("%d",&num);
236.  
     switch (num)
237.  
     {
238.  
     case 1:
239.  
     printf("宿舍有公共厨房，公共阅览室，公共厕所\n\n");
240.  
     break;
241.  
     case 2:
242.  
     printf("一食堂有丰富的菜品\n\n");
243.  
     break;
244.  
     case 3:
245.  
     printf("湖滨餐厅有中西方菜品\n\n");
246.  
     break;
247.  
     case 4:
248.  
     printf("图书馆设施好，学习氛围浓烈\n\n");
249.  
     break;
250.  
     case 5:
251.  
     printf("实验楼有实验室以及机房\n\n");
252.  
     break;
253.  
     case 6:
254.  
     printf("可以在里面举办一些晚会\n\n");
255.  
     break;
256.  
     case 7:
257.  
     printf("老师办公区域\n\n");
258.  
     break;
259.  
     case 8:
260.  
     printf("看主楼的最好位置\n\n");
261.  
     break;
262.  
     default:
263.  
     printf("无该场所编号，请重新输入场所编号\n\n");
264.  
     break;
265.  
     }
266.  
     }
267.  
      
268.  
     int main()
269.  
     {
270.  
     //打印学校图(注：需要把照片与代码放在用一个文件夹下)
271.  
     char pic_name[80]="school.PNG";
272.  
     char cmd[100];
273.  
     sprintf(cmd,pic_name);
274.  
     system(cmd);
275.  
     Graph* G=initGraph(8);
276.  
     int arcs[8][8]={ //邻接矩阵(权重(按走到该建筑的时间创立))
277.  
     0,3,6,6,10,5,MAX,4,
278.  
     3,0,4,MAX,MAX,MAX,MAX,MAX,
279.  
     6,4,0,1,6,MAX,MAX,MAX,
280.  
     6,MAX,1,0,5,MAX,MAX,MAX,
281.  
     10,MAX,6,5,0,MAX,3,MAX,
282.  
     5,MAX,MAX,MAX,MAX,0,1,2,
283.  
     MAX,MAX,MAX,MAX,3,1,0,1,
284.  
     4,MAX,MAX,MAX,MAX,2,1,0
285.  
     };
286.  
     printf("学校的平面图为:\n");
287.  
     createGraph(G,(int*)arcs);
288.  
     int input;
289.  
     do
290.  
     {
291.  
     Sleep(1000); //延迟输出1s,方便查看
292.  
     menu();
293.  
     printf("请输入所需要的功能: ");
294.  
     scanf("%d",&input);
295.  
     switch (input) {
296.  
     case 1:
297.  
     {
298.  
     int n;
299.  
     hint();
300.  
     printf("请输入场所编号: ");
301.  
     scanf("%d",&n);
302.  
     if(n<1||n>8)
303.  
     {
304.  
     printf("无该场所编号，请重新输入\n\n");
305.  
     break;
306.  
     }
307.  
     printf("\n从该场所到各个场所的最短路径依次是:\n");
308.  
     dijkstra(G,n-1);
309.  
     printf("\n");
310.  
     break;
311.  
     }
312.  
     case 2:
313.  
     {
314.  
     int a,b;
315.  
     hint();
316.  
     printf("请输入想从哪个场所到哪个场所的编号\n");
317.  
     printf("开始场所: ");
318.  
     scanf("%d",&a);
319.  
     printf("目的地场所: ");
320.  
     scanf("%d",&b);
321.  
     if((a<1||a>8)&&(b<1||b>8))
322.  
     {
323.  
     printf("无该场所编号，请重新输入\n\n");
324.  
     break;
325.  
     }
326.  
     floyd(G,a-1,b-1);
327.  
     break;
328.  
     }
329.  
     case 3:
330.  
     {
331.  
     feature();
332.  
     break;
333.  
     }
334.  
     case 4:
335.  
     {
336.  
     system("cls");
337.  
     break;
338.  
     }
339.  
     case 0:
340.  
     {
341.  
     printf("退出程序\n");
342.  
     break;
343.  
     }
344.  
     default:
345.  
     {
346.  
     printf("无该功能，请重新输入所需的功能\n\n");
347.  
     break;
348.  
     }
349.  
     }
350.  
     }while(input);
351.  
     return 0;
352.  
     }

四、实验结果及数据处理分析： 

 

    根据运行结果，发现此代码实现了该实验的功能。(为了更好的呈现结果这里将清屏功能删除，在实际代码中可实现清屏功能。) 

这篇好文章是转载于：学新通技术网