VC出租车路线规划算法Dijkstra设计(5)
时间:2017-01-10 10:59 来源:毕业论文 作者:毕业论文 点击:次
pot[2].x=485;pot[2].y=283;//C pot[3].x=366;pot[3].y=366;//D pot[4].x=383;pot[4].y=272;//E pot[5].x=352;pot[5].y=437;//F pot[6].x=313;pot[6].y=417;//G pot[7].x=394;pot[7].y=160;//H pot[8].x=250;pot[8].y=441;//I pot[9].x=277;pot[9].y=317;//J pot[10].x=333;pot[10].y=329;//K pot[11].x=339;pot[11].y=267;//L pot[12].x=344;pot[12].y=157;//M pot[13].x=408;pot[13].y=50;//N pot[14].x=287;pot[14].y=265;//O pot[15].x=308;pot[15].y=157;//P pot[16].x=328;pot[16].y=60;//Q pot[17].x=357;pot[17].y=62;//R pot[18].x=379;pot[18].y=3;//S pot[19].x=265;pot[19].y=186;//T pot[20].x=242;pot[20].y=258;//U pot[21].x=181;pot[21].y=240;//V pot[22].x=185;pot[22].y=163;//W pot[23].x=243;pot[23].y=136;//X pot[24].x=232;pot[24].y=175;//Y pot[25].x=111;pot[25].y=147;//Z pot[26].x=194;pot[26].y=125;//A1 pot[27].x=248;pot[27].y=98;//A2 pot[28].x=200;pot[28].y=93;//A3 pot[29].x=253;pot[29].y=67;//A4 pot[30].x=206;pot[30].y=57;//A5 pot[31].x=93;pot[31].y=48;//A6 pot[32].x=104;pot[32].y=120;//A7 pot[33].x=71;pot[33].y=115;//A8 pot[34].x=58;pot[34].y=48;//A9 pot[35].x=70;pot[35].y=83;//A10 pot[36].x=20;pot[36].y=42;//A11 pot[37].x=19;pot[37].y=85;//A12 pot[38].x=21;pot[38].y=142;//A13 //连接点及之间距离 g[0][1]=103;g[1][0]=103;g[1][3]=114;g[3][1]=114; g[1][2]=91;g[2][1]=91;g[2][4]=102;g[4][2]=102; g[7][4]=112;g[4][7]=112;g[11][4]=44;g[4][11]=44; g[11][12]=110;g[12][11]=110;g[11][10]=62;g[10][11]=62; g[12][7]=50;g[7][12]=50;g[13][7]=110;g[7][13]=110; g[13][18]=55;g[18][13]=55;g[17][18]=62;g[18][17]=62; g[17][16]=29;g[16][17]=29;g[11][14]=52;g[14][11]=52; g[10][9]=57;g[9][10]=57;g[14][9]=52;g[9][14]=52; g[3][5]=72;g[5][3]=72; g[6][5]=43;g[5][6]=43; g[6][8]=67;g[8][6]=67;g[9][8]=126;g[8][9]=126; g[14][15]=110;g[15][14]=110;g[16][15]=99;g[15][16]=99; g[23][15]=68;g[15][23]=68;g[14][20]=45;g[20][14]=45; g[19][20]=75;g[20][19]=75;g[21][20]=63;g[20][21]=63; g[22][21]=77;g[21][22]=77;g[22][26]=39;g[26][22]=39; g[22][24]=48;g[24][22]=48;g[23][24]=40;g[24][23]=40; g[23][27]=38;g[27][23]=38;g[24][19]=34;g[19][24]=34; g[27][28]=48;g[28][27]=48;g[27][29]=31;g[29][27]=31; g[30][29]=48;g[29][30]=48;g[30][31]=113;g[31][30]=113; g[30][28]=36;g[28][30]=36;g[26][28]=32;g[28][26]=32; g[26][23]=50;g[23][26]=50;g[22][25]=75;g[25][22]=75; g[32][25]=27;g[25][32]=27;g[32][26]=90;g[26][32]=90; g[32][33]=33;g[33][32]=33;g[32][31]=72;g[31][32]=72; g[31][34]=35;g[34][31]=35;g[35][34]=37;g[34][35]=37; g[35][33]=32;g[33][35]=32;g[38][33]=56;g[33][38]=56; g[38][37]=57;g[37][38]=57;g[35][37]=51;g[37][35]=51; g[36][37]=43;g[37][36]=43;g[36][34]=38;g[34][36]=38; 3 寻路算法介绍 3.1 Djikstra 3.1.1 简介 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。 (责任编辑：qin) |