1、 i+） /初始化点编号 5 mgraph.vexs.push_back （i）; 6 mgraph.arcnum = 98; /边数 7 for （int i = 0; i+） 8 for （int j = 0; j j+） 9 if （i = j）10 mgraph.arcsij.adj = 0;11 else12 mgraph.arcsij.adj = INF;13 14 15 2. 设置图的景点之间的权值。 1 void MainWindow:CreateGraph （） 3 mgraph.arcs01.adj = mgraph.arcs10.adj = 45; /6 - 5 4 mg
2、raph.arcs06.adj = mgraph.arcs60.adj = 165; /6 - 10 5 mgraph.arcs12.adj = mgraph.arcs21.adj = 45; /5 - 4 6 mgraph.arcs23.adj = mgraph.arcs32.adj = 45; /4 - 3 7 mgraph.arcs34.adj = mgraph.arcs43.adj = 45; /3 - 2 8 mgraph.arcs315.adj = mgraph.arcs153.adj = 24; /3 - 22 9 mgraph.arcs45.adj = mgraph.arcs5
3、4.adj = 45; /2 - 110 mgraph.arcs1315.adj = mgraph.arcs1513.adj = 85;/23 - 2211 mgraph.arcs013.adj = mgraph.arcs130.adj = 55; /6 - 2312 mgraph.arcs132.adj = mgraph.arcs213.adj = 50; /23 - 413 mgraph.arcs511.adj = mgraph.arcs115.adj = 65; /1 - 一食堂14 mgraph.arcs1112.adj = mgraph.arcs1211.adj = 10;/一食堂-
4、操场15 mgraph.arcs1127.adj = mgraph.arcs2711.adj = 85;/一食堂-祁通116 mgraph.arcs2728.adj = mgraph.arcs2827.adj = 85;/祁通1-祁通2（路口）17 mgraph.arcs529.adj = mgraph.arcs295.adj = 87; /一食堂-岔路口18 mgraph.arcs2911.adj = mgraph.arcs1129.adj = 50;/一食堂到岔路（通向7号楼的）19 mgraph.arcs2930.adj = mgraph.arcs3029.adj = 32;/岔路-祁通
5、大道20 mgraph.arcs3010.adj = mgraph.arcs1030.adj = 90;/祁通大道-图书馆21 mgraph.arcs3028.adj = mgraph.arcs2830.adj = 80;/祁通大道-祁通222 mgraph.arcs2826.adj = mgraph.arcs2628.adj = 15;/祁通2-方肇周23 mgraph.arcs2527.adj = mgraph.arcs2725.adj = 273;/西大门-祁通124 mgraph.arcs2728.adj = mgraph.arcs2827.adj = 84; /祁通1-祁通225 m
6、graph.arcs512.adj = mgraph.arcs125.adj = 70; /1 - 操场26 mgraph.arcs67.adj = mgraph.arcs76.adj = 45; /10 - 927 mgraph.arcs78.adj = mgraph.arcs87.adj = 45; /9 - 828 mgraph.arcs89.adj = mgraph.arcs98.adj = 45; /8 - 729 mgraph.arcs910.adj = mgraph.arcs109.adj = 150; /7 - 图书馆30 mgraph.arcs614.adj = mgraph
7、.arcs146.adj = 140; /10 - 1331 mgraph.arcs1416.adj = mgraph.arcs1614.adj = 39;/13 - 1232 mgraph.arcs1417.adj = mgraph.arcs1714.adj = 39;/13 - 1633 mgraph.arcs1618.adj = mgraph.arcs1816.adj = 39;/12 - 1534 mgraph.arcs1718.adj = mgraph.arcs1817.adj = 39;/16 - 1535 mgraph.arcs1819.adj = mgraph.arcs1918
8、.adj = 20;/15 - 1436 mgraph.arcs1720.adj = mgraph.arcs2017.adj = 137;/16 - 1937 mgraph.arcs2021.adj = mgraph.arcs2120.adj = 39; /19 - 1838 mgraph.arcs2122.adj = mgraph.arcs2221.adj = 39; /18 - 1739 mgraph.arcs1922.adj = mgraph.arcs2219.adj = 130;/14 - 1740 mgraph.arcs2223.adj = mgraph.arcs2322.adj =
9、 53; /17 - 二超41 mgraph.arcs2324.adj = mgraph.arcs2423.adj = 5; /二超 - 二食堂42 43 /以下处理细节这是景点之间的一小段路之间的权值，因为用界面绘制路线，会/出现弧状的路线，所以需要定额外的坐标44 mgraph.arcs3031.adj = mgraph.arcs3130.adj = 30; /祁通大道-祁通大道245 mgraph.arcs3132.adj = mgraph.arcs3231.adj = 10; /祁通大道2-祁通大道346 mgraph.arcs3210.adj = mgraph.arcs1032.ad
10、j = 20; /祁通大道3-图书馆47 mgraph.arcs1033.adj = mgraph.arcs3310.adj = 80; /图书馆-祁通大道448 mgraph.arcs3334.adj = mgraph.arcs3433.adj = 45; /祁通4-祁通549 mgraph.arcs3424.adj = mgraph.arcs2434.adj = 45; /祁通5-二食堂50 mgraph.arcs3423.adj = mgraph.arcs2334.adj = 45; /祁通5-二超51 mgraph.arcs3335.adj = mgraph.arcs3533.adj
11、= 30; /祁通4-通向14号楼的小道52 mgraph.arcs3519.adj = mgraph.arcs1935.adj = 10; /小道-14号楼53 mgraph.arcs3536.adj = mgraph.arcs3635.adj = 10; /小道14-小道1554 mgraph.arcs3618.adj = mgraph.arcs1836.adj = 10; /小道15-1555 mgraph.arcs3616.adj = mgraph.arcs1636.adj = 5; /小道15-1256 mgraph.arcs3729.adj = mgraph.arcs2937.ad
12、j = 40; /岔路-岔路257 mgraph.arcs379.adj = mgraph.arcs937.adj = 45; /岔路2-758 60 3. 计算最短路径，并对输出路径进行初始化工作。dijkstra （int startPos） 3 for （int i = 0; i+） di = INF; i+） usedi = false; 5 for （int i = 0; i+） previ = -1; 6 dstartPos = 0; 7 8 while （true） 9 int v = -1;10 for （int u = 0; u u+） 11 if （!usedu & （v
13、= -1 | du dv + mgraph.arcsvu.adj） 19 du = dv + mgraph.arcsvu.adj;20 prevu = v;21 22 23 24 4.存储起点到终点之间的路径。 1 QVector MainWindow:get_Path （int endPos） 3 QVector path; 4 /保存景点之间的最短路径上的全部景点 5 for （ ; endPos != -1; endPos = prevendPos） 6 path.push_back （endPos）; 7 8 /由于路径是从终点向起点保存的，还需要将路径逆置。 9 std:revers
14、e（path.begin （）, path.end （）;10 return path;11 三、运行结果：（1）起点：公寓1号楼 终点：公寓10号楼（2）起点：公寓9号楼 终点：公寓2号楼（3）起点：公寓2号楼 终点：公寓4号楼四、全部代码：1 首先要对图进行初始化，才能正常计算最短路径 1 /* 2 * 主要功能: 3 * 1. 绘制输入起点，终点最短路径 4 * 2. 双击地点, 查看景点信息 5 * 3. 修改景点图片 6 * 4. 打开测试地图，查看地图坐标，可缩放地图. 7 */ 8 #ifndef MAINWINDOW_H 9 #define MAINWINDOW_H 10 11
15、 #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 29 class MainWindow : public QMainWindow 30 31 Q_OBJECT 32 public: 33 MainWindow（QW
16、idget *parent = 0）; 34 MainWindow（）; 35 void createToolBar（）; 36 void createAction（）; 37 void setStart（int X, int Y）; 38 void setEnd（int X, int Y）; 39 void setNextPos （int index）; 40 void initScene（）; 41 public slots: 42 void setStartStation（）; 43 void setEndStation（）; 44 void FindPath（）; 45 void Cl
17、ear（）; 46 void Revise（）; 47 void callOtherMap（）; 48 void ShowDialog（）; 49 private: 50 MapWidget *mapWidget; 51 QLabel *startLabel; 52 QLabel *endLabel; 53 QComboBox *startComboBox; 54 QComboBox *endComboBox; 55 QComboBox *reviseComboBox; 56 57 QAction *findPathAction; 58 QAction *clearAction; 59 QAc
18、tion *reviseAction; 60 QAction *callMap; 61 62 QGraphicsScene *scene; 63 QGraphicsView *view; 64 65 int startX, startY, endX, endY; 66 QVector nextPath; 67 68 /* 69 * 图的实现，和最短路径算法声明 70 */ 71 struct ArcCell /弧信息 72 int adj; /对无权图有1，0表示是否相邻，对带权图，则为权值类型 73 / string info; /该弧的相关信息 74 ; 75 76 77 /内部类 78
19、static const int MAX_VERTEX_NUM = 50; 79 static const int INF = 999999; 80 81 struct MGraph 82 QVector vexs; /顶点集合 83 /临接矩阵 84 ArcCell arcsMAX_VERTEX_NUMMAX_VERTEX_NUM; 85 int vexnum; /顶点数 86 int arcnum; 87 / int kind; /图的类型 88 ; 89 90 class DijkstraFindPath 91 92 public: 93 DijkstraFindPath（）; 94 M
20、Graph mgraph; 95 void CreateGraph（）; 96 97 int prevMAX_VERTEX_NUM; /最短路上的前驱顶点 98 int dMAX_VERTEX_NUM; /表示边e = （u,v）的权值（不存在时为INF,不过dii=0） 99 bool usedMAX_VERTEX_NUM; /已经使用过的图100 void dijkstra（int startPos）; /求从起点startPos出发到各个顶点的最短距离101 QVector get_Path（int endPos）;/到顶点endPos的最短路102 ;103 104 DijkstraF
21、indPath *dj;105 106 /鼠标事件107 protected:108 void mouseDoubleClickEvent （QMouseEvent *e）;109 private:110 QPixmap library; /图书馆111 QPixmap canteen; /餐厅112 QPixmap jxjBuilding; /计算机楼113 QPixmap westgate; /西门114 QPixmap westground; /西操115 QPixmap twoMarket; /二超116 QString strPath; /文件路径117 QLabel *label;
22、118 ;119 120 #endif / MAINWINDOW_H 1 #include mainwindow.h 2 #include 3 #include 4 #include 5 #include 6 #include 8 MainWindow:MainWindow（QWidget *parent） 9 : QMainWindow（parent） 10 11 setWindowTitle （可爱的豆豆豆 校园导航）; 12 dj = new MainWindow:DijkstraFindPath（）; 13 dj-CreateGraph （）; 14 15 scene = new QG
23、raphicsScene; 16 scene-setSceneRect （-100, -100, 700, 700）; 17 initScene（）; 18 19 view = new QGraphicsView; 20 view-setScene （scene）; 21 view-setMinimumSize （800, 800）; 22 view-show （）; 23 setCentralWidget （view）; 24 25 createAction （）; 26 createToolBar （）; /实现一个工具栏 27 setMinimumSize （800, 800）; /设置最小尺寸 28 Sleep（2000）; 29 30 31 MainWindow: 32 33 mg
