基于QT的校园地图导航.docx

基于QT的校园地图导航.docx

《基于QT的校园地图导航.docx》由会员分享，可在线阅读，更多相关《基于QT的校园地图导航.docx（51页珍藏版）》请在冰点文库上搜索。

基于QT的校园地图导航

基于QT的校园地图导航

一、需求分析：

随着科技的进步，计算机已越来越深入到任命的生活‘工作中，极大的方便了任命的日常生活和工作。

特别是随着科技的不断进步，智能化也不是一个名词，而是实在的随处可见。

算法设计与分析对于程序的实现起着非常重要的作用，思路才是程序的核心。

这个校园导航系统，利用算法设计里的图俩解决，它将校园景点作为图的结点，将景点间的路径作为图的边，路径距离作为边的权值。

这样一来。

求两景点间的最短路径的问题就抽象成了求图中一结点到另一个结点的问题。

于是我们编写了这个校园导航系统，为刚入学的新生或是初次到学校参观的人提供一个校园导航引导他们出行。

二、主要算法讲解：

1.计算最短路径（dijkstra算法）

Step1:

（1）找到最短路径已经确定的顶点，从它已经确定的顶点，从它除法更新相邻顶点的最短距离。

（2）此后不需要再关心1中的“最短距离已经确定的顶点”。

　　（3）在

（1）和

（2）中提到的“最短距离已经确定的顶点”要求解的关键。

在最开始时，只有起点的最短距离是确定的。

而在尚未使用过的顶点中，距离d[i]最小的顶点就是最短距离已经确定的顶点。

这是因为由于不存在负边，所以d[i]不会在更新中变小。

定义几个方便算法描述的变量:

　　intcost[MAX_V][MAX_V];//cost[u][v]表示表e=（u，v）的权值（不存在这条边时设为INF）

　　intd[MAX_V];//顶点s出发的最短路径

　　boolused[MAX_V];//已经使用的图

Step2:

（1）如果，我们需要输出最短路的路径。

注，在求解最短路径时，满足d[j]=d[k]+cost[k][j]的顶点k（d[j]是表示从起点开始到j的最短路径距离，cost[k][j]是表示k到j的距离）,就是最短路上的顶点j的前驱结点，因此通过不断寻找前驱结点就可以恢复最短路。

时间复杂度是O（E）。

（2）如果，我们用prev[j]来记录最短路上的顶点j的前驱，那么就可以在O（|V|）时间内完成最短路的恢复。

在d[j]=d[k]+cost[k][j]更新时，修改prev[j]=k,这样就可以求得prev数组。

在计算从起点s出发到j的最短路时，通过prev[j]就可以知道顶点j的前驱，因此不断把j替换成prev[j]直到j=s为止即可。

代码如下：

1.首先要对图进行初始化，才能正常计算最短路径

1MainWindow:

:

DijkstraFindPath:

:

DijkstraFindPath（）

2{

3mgraph.vexnum=40;//初始化点数目

4for（inti=0;i

5mgraph.vexs.push_back（i）;

6mgraph.arcnum=98;//边数

7for（inti=0;i

8for（intj=0;j

9if（i==j）

10mgraph.arcs[i][j].adj=0;

11else

12mgraph.arcs[i][j].adj=INF;

13}

14}

15}

2.设置图的景点之间的权值。

1voidMainWindow:

:

DijkstraFindPath:

:

CreateGraph（）

2{

3mgraph.arcs[0][1].adj=mgraph.arcs[1][0].adj=45;//6-5

4mgraph.arcs[0][6].adj=mgraph.arcs[6][0].adj=165;//6-10

5mgraph.arcs[1][2].adj=mgraph.arcs[2][1].adj=45;//5-4

6mgraph.arcs[2][3].adj=mgraph.arcs[3][2].adj=45;//4-3

7mgraph.arcs[3][4].adj=mgraph.arcs[4][3].adj=45;//3-2

8mgraph.arcs[3][15].adj=mgraph.arcs[15][3].adj=24;//3-22

9mgraph.arcs[4][5].adj=mgraph.arcs[5][4].adj=45;//2-1

10mgraph.arcs[13][15].adj=mgraph.arcs[15][13].adj=85;//23-22

11mgraph.arcs[0][13].adj=mgraph.arcs[13][0].adj=55;//6-23

12mgraph.arcs[13][2].adj=mgraph.arcs[2][13].adj=50;//23-4

13mgraph.arcs[5][11].adj=mgraph.arcs[11][5].adj=65;//1-一食堂

14mgraph.arcs[11][12].adj=mgraph.arcs[12][11].adj=10;//一食堂-操场

15mgraph.arcs[11][27].adj=mgraph.arcs[27][11].adj=85;//一食堂-祁通1

16mgraph.arcs[27][28].adj=mgraph.arcs[28][27].adj=85;//祁通1-祁通2（路口）

17mgraph.arcs[5][29].adj=mgraph.arcs[29][5].adj=87;//一食堂-岔路口

18mgraph.arcs[29][11].adj=mgraph.arcs[11][29].adj=50;//一食堂到岔路（通向7号楼的）

19mgraph.arcs[29][30].adj=mgraph.arcs[30][29].adj=32;//岔路-祁通大道

20mgraph.arcs[30][10].adj=mgraph.arcs[10][30].adj=90;//祁通大道-图书馆

21mgraph.arcs[30][28].adj=mgraph.arcs[28][30].adj=80;//祁通大道-祁通2

22mgraph.arcs[28][26].adj=mgraph.arcs[26][28].adj=15;//祁通2-方肇周

23mgraph.arcs[25][27].adj=mgraph.arcs[27][25].adj=273;//西大门-祁通1

24mgraph.arcs[27][28].adj=mgraph.arcs[28][27].adj=84;//祁通1-祁通2

25mgraph.arcs[5][12].adj=mgraph.arcs[12][5].adj=70;//1-操场

26mgraph.arcs[6][7].adj=mgraph.arcs[7][6].adj=45;//10-9

27mgraph.arcs[7][8].adj=mgraph.arcs[8][7].adj=45;//9-8

28mgraph.arcs[8][9].adj=mgraph.arcs[9][8].adj=45;//8-7

29mgraph.arcs[9][10].adj=mgraph.arcs[10][9].adj=150;//7-图书馆

30mgraph.arcs[6][14].adj=mgraph.arcs[14][6].adj=140;//10-13

31mgraph.arcs[14][16].adj=mgraph.arcs[16][14].adj=39;//13-12

32mgraph.arcs[14][17].adj=mgraph.arcs[17][14].adj=39;//13-16

33mgraph.arcs[16][18].adj=mgraph.arcs[18][16].adj=39;//12-15

34mgraph.arcs[17][18].adj=mgraph.arcs[18][17].adj=39;//16-15

35mgraph.arcs[18][19].adj=mgraph.arcs[19][18].adj=20;//15-14

36mgraph.arcs[17][20].adj=mgraph.arcs[20][17].adj=137;//16-19

37mgraph.arcs[20][21].adj=mgraph.arcs[21][20].adj=39;//19-18

38mgraph.arcs[21][22].adj=mgraph.arcs[22][21].adj=39;//18-17

39mgraph.arcs[19][22].adj=mgraph.arcs[22][19].adj=130;//14-17

40mgraph.arcs[22][23].adj=mgraph.arcs[23][22].adj=53;//17-二超

41mgraph.arcs[23][24].adj=mgraph.arcs[24][23].adj=5;//二超-二食堂

42

43//以下处理细节—这是景点之间的一小段路之间的权值，因为用界面绘制路线，会//出现弧状的路线，所以需要定额外的坐标

44mgraph.arcs[30][31].adj=mgraph.arcs[31][30].adj=30;//祁通大道-祁通大道2

45mgraph.arcs[31][32].adj=mgraph.arcs[32][31].adj=10;//祁通大道2-祁通大道3

46mgraph.arcs[32][10].adj=mgraph.arcs[10][32].adj=20;//祁通大道3-图书馆

47mgraph.arcs[10][33].adj=mgraph.arcs[33][10].adj=80;//图书馆-祁通大道4

48mgraph.arcs[33][34].adj=mgraph.arcs[34][33].adj=45;//祁通4-祁通5

49mgraph.arcs[34][24].adj=mgraph.arcs[24][34].adj=45;//祁通5-二食堂

50mgraph.arcs[34][23].adj=mgraph.arcs[23][34].adj=45;//祁通5-二超

51mgraph.arcs[33][35].adj=mgraph.arcs[35][33].adj=30;//祁通4-通向14号楼的小道

52mgraph.arcs[35][19].adj=mgraph.arcs[19][35].adj=10;//小道-14号楼

53mgraph.arcs[35][36].adj=mgraph.arcs[36][35].adj=10;//小道14-小道15

54mgraph.arcs[36][18].adj=mgraph.arcs[18][36].adj=10;//小道15-15

55mgraph.arcs[36][16].adj=mgraph.arcs[16][36].adj=5;//小道15-12

56mgraph.arcs[37][29].adj=mgraph.arcs[29][37].adj=40;//岔路-岔路2

57mgraph.arcs[37][9].adj=mgraph.arcs[9][37].adj=45;//岔路2-7

58

60}

3.计算最短路径，并对输出路径进行初始化工作。

1voidMainWindow:

:

DijkstraFindPath:

:

dijkstra（intstartPos）

2{

3for（inti=0;i

4for（inti=0;i

5for（inti=0;i

6d[startPos]=0;

7

8while（true）{

9intv=-1;

10for（intu=0;u

11if（!

used[u]&&（v==-1||d[u]

12}

13

14if（v==-1）break;

15used[v]=true;

16

17for（intu=0;u

18if（d[u]>d[v]+mgraph.arcs[v][u].adj）{

19d[u]=d[v]+mgraph.arcs[v][u].adj;

20prev[u]=v;

21}

22}

23}

24}

4.存储起点到终点之间的路径。

1QVectorMainWindow:

:

DijkstraFindPath:

:

get_Path（intendPos）

2{

3QVectorpath;

4//保存景点之间的最短路径上的全部景点

5for（;endPos!

=-1;endPos=prev[endPos]）{

6path.push_back（endPos）;

7}

8//由于路径是从终点向起点保存的，还需要将路径逆置。

9std:

:

reverse（path.begin（）,path.end（））;

10returnpath;

11}

三、运行结果：

（1）起点：

公寓1号楼终点：

公寓10号楼

（2）起点：

公寓9号楼终点：

公寓2号楼

（3）起点：

公寓2号楼终点：

公寓4号楼

四、全部代码：

1首先要对图进行初始化，才能正常计算最短路径

1/**

2*主要功能:

3*1.绘制输入起点，终点最短路径

4*2.双击地点,查看景点信息

5*3.修改景点图片

6*4.打开测试地图，查看地图坐标，可缩放地图.

7**/

8#ifndefMAINWINDOW_H

9#defineMAINWINDOW_H

10

11#include

12#include"mapwidget.h"

13#include

14#include

15#include

16#include

17#include

18#include

19#include

20#include

21#include

22#include

23#include

24#include

25#include

26#include

27#include

28

29classMainWindow:

publicQMainWindow

30{

31Q_OBJECT

32public:

33MainWindow（QWidget*parent=0）;

34~MainWindow（）;

35voidcreateToolBar（）;

36voidcreateAction（）;

37voidsetStart（intX,intY）;

38voidsetEnd（intX,intY）;

39voidsetNextPos（intindex）;

40voidinitScene（）;

41publicslots:

42voidsetStartStation（）;

43voidsetEndStation（）;

44voidFindPath（）;

45voidClear（）;

46voidRevise（）;

47voidcallOtherMap（）;

48voidShowDialog（）;

49private:

50MapWidget*mapWidget;

51QLabel*startLabel;

52QLabel*endLabel;

53QComboBox*startComboBox;

54QComboBox*endComboBox;

55QComboBox*reviseComboBox;

56

57QAction*findPathAction;

58QAction*clearAction;

59QAction*reviseAction;

60QAction*callMap;

61

62QGraphicsScene*scene;

63QGraphicsView*view;

64

65intstartX,startY,endX,endY;

66QVectornextPath;

67

68/*

69*图的实现，和最短路径算法声明

70*/

71structArcCell{//弧信息

72intadj;//对无权图有1，0表示是否相邻，对带权图，则为权值类型

73//stringinfo;//该弧的相关信息

74};

75

76

77//内部类

78staticconstintMAX_VERTEX_NUM=50;

79staticconstintINF=999999;

80

81structMGraph{

82QVectorvexs;//顶点集合

83//临接矩阵

84ArcCellarcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

85intvexnum;//顶点数

86intarcnum;//边数

87//intkind;//图的类型

88};

89

90classDijkstraFindPath

91{

92public:

93DijkstraFindPath（）;

94MGraphmgraph;

95voidCreateGraph（）;

96

97intprev[MAX_VERTEX_NUM];//最短路上的前驱顶点

98intd[MAX_VERTEX_NUM];//表示边e=（u,v）的权值（不存在时为INF,不过d[i][i]=0）

99boolused[MAX_VERTEX_NUM];//已经使用过的图

100voiddijkstra（intstartPos）;//求从起点startPos出发到各个顶点的最短距离

101QVectorget_Path（intendPos）;//到顶点endPos的最短路

102};

103

104DijkstraFindPath*dj;

105

106//鼠标事件

107protected:

108voidmouseDoubleClickEvent（QMouseEvent*e）;

109private:

110QPixmaplibrary;//图书馆

111QPixmapcanteen;//餐厅

112QPixmapjxjBuilding;//计算机楼

113QPixmapwestgate;//西门

114QPixmapwestground;//西操

115QPixmaptwoMarket;//二超

116QStringstrPath;//文件路径

117QLabel*label;

118};

119

120#endif//MAINWINDOW_H

1#include"mainwindow.h"

2#include

3#include

4#include

5#include

6#include

7

8MainWindow:

:

MainWindow（QWidget*parent）

9:

QMainWindow（parent）

10{

11setWindowTitle（"可爱的豆豆豆校园导航"）;

12dj=newMainWindow:

:

DijkstraFindPath（）;

13dj->CreateGraph（）;

14

15scene=newQGraphicsScene;

16scene->setSceneRect（-100,-100,700,700）;

17initScene（）;

18

19view=newQGraphicsView;

20view->setScene（scene）;

21view->setMinimumSize（800,800）;

22view->show（）;

23setCentralWidget（view）;

24

25createAction（）;

26createToolBar（）;//实现一个工具栏

27setMinimumSize（800,800）;//设置最小尺寸

28Sleep（2000）;

29}

30

31MainWindow:

:

DijkstraFindPath:

:

DijkstraFindPath（）

32{

33mg