山大公交线路上优化路径查询试验报告

1、山东大学 计算机科学与技术 学院数据结构课程实验报告学号：姓名：班级:实验题目：公交线路上优化路径的查询实验学时：32实验日期:硬件环境： 软件环境: 实验内容与设计：1. 实验内容： 问题描述：最短路径问题是图论中的一个经典问题，其中的 Dijkstra算法一直被认为是图论中的好 算法，但有的时候需要适当的调整Dijkstra算法才能完成多种不同的优化路径的查询。对于某城市的公交线路，乘坐公交的顾客希望在这样的线路上实现各种优化路径的查 询。设该城市的公交线路的输入格式为：线路编号：起始站名（该站坐标）；经过的站点1名（该站坐标）；经过的站点2名（该站坐 标）； ；经过的站点n名（该站坐标）

2、;终点站名（该站坐标）。该线路的乘坐价钱。该线路 平均经过多少时间来一辆。车速。例如：63： A（32,45） ； B（76,45） ； C（76,90）；N（100,100）。1 元。5分钟。1/每分 钟。假定线路的乘坐价钱与乘坐站数无关，假定不考虑公交线路在路上的交通堵塞。对这样的公交线路，需要在其上进行的优化路径查询包括：任何两个站点之间最便宜的 路径；任何两个站点之间最省时间的路径等等。基本要求： 根据上述公交线路的输入格式，定义并建立合适的图模型。 针对上述公交线路，能查询获得任何两个站点之间最便宜的路径，即输入站名S，T后，可以输出从S到T的最便宜的路径，输出格式为：线路x :站名

3、S,，站名M1;换乘线路 x:站名M1,，站名M2；换乘线路x:站名MK，站名T。共花费x元。 针对上述公交线路，能查询获得任何两个站点之间最省时间的路径（不考虑在中间站等下一辆线路的等待时间），即输入站名 S，T后，可以输出从S到T的考虑在中间站等下一 辆线路的等待时间的最省时间的路径，输出格式为：线路 x :站名S,，站名M1;换乘线路 x:站名M1,，站名M2；换乘线路x:站名MK，站名T。共花费x时间。 针对上述公交线路，能查询获得任何两个站点之间最省时间的路径（要考虑在中间站等下一辆线路的等待时间），即输入站名 S，T后，可以输出从S到T的考虑在中间站等下一 辆线路的等待时间的最省时

4、间的路径，输出格式为：线路 x :站名S,，站名M1;换乘线路 x:站名M1,，站名M2；换乘线路x:站名MK，站名T。共花费x时间。 实现提示：需深入考虑，应根据不同的应用目标，即不同的优化查询来建立合适的图模型。2. 实验设计：（1）实验需求：（1）输入数据：总的路线数目，各路线的站点数目，各站点的名称、位置坐标以及各 公交路线的速度及票价。(2) 输出数据：输入数据的预处理结果(中间链表)与多个索引数组，三个不同权值 的邻接矩阵的值(距离，时间，票价)，以及各种不同需求下公交线路的结果。(3) 功能：实现在不同查询条件下最优公交线路的输出。(2) 实现思想：首先需要对输入的数据进行预处理

5、。 此处运用双向链表来存储各站点的名称、横纵坐标及相对位置关系。然后用一个公交车 Bus类来存储各个线路的票价、速度及总线路。之后需要整合所有链表以生成邻接矩阵。首先将所有链表进行第一步处理，算出相邻两 点间距离存入第一个结点中原横坐标的位置，特别的，每个链表最后一个站点对应结点的相同位置则存储为 NoEdge( 99999)。接着将各站点按顺序编号存于原链表纵坐标位置。接下 来将各路线的链表连接在一起形成一个存有全部路线的新链表wholeRoad。对wholeRoad进行处理。因为各路线中站点可能出现重复的情况，因此需要对编号进行 去重操作。遍历链表若发现某站点名出现过两次或两次以上，则将第

6、二个以后的编号皆赋成第一个的编号值，同时设置一个变量count来记录多次出现的的站点数。count初始值为0， 若出现一次重复则count加1，同时后面所有的编号赋为原编号减去 count。通过以上方法 来解决重复站点问题。根据最终站点编号建立原始编号与最终编号的索引数组和最终编号与站点名的索引数 组，并提供逆向查找方法。最后生成以距离为邻接矩阵时依照的就是最终的编号。不过在生 成过程中还是按照总线路链表进行循环，遍历总路线链表并根据索引将对应的距离存入真正 的位置，其他位置均设为 NoEdge而生成以时间为权值和以票价为权值的邻接矩阵过程基 本一样，只不过是将对应位置的值除相应速度或换为相应

7、票价乘上线路编号的平方(原因下方解释)。在最终邻接矩阵处理中主要运用 Dijkstra 算法。在时间最少与距离最短查询时直接使 用Dijkstra 算法即可。然而在票价最少时需要对算法进行调整。因为坐公交车时在一条线 路上一直乘坐只需要交一次车票钱因此不能直接将票价进行累加，然而不同线路间也可能存在票价相同的情况，因此也不能直接运用只要和上一条路线票价相同就不进行累加的方法。 为了避免不同线路票价权值相同，在赋值前先进行预处理，将票价改为相应票价乘上线路编 号的平方，并建立索引以及添加一个寻找原票价的方法。因此对于最少花费查询，只需在 Dijkstra算法中加上寻找原票价的方法以及判断将要添加

8、的路径的权值是否与上一条相同的步骤。最终结果是将存的点按索引转化为对应的站点名后按顺序输出，并将最小加权一并输 出。先进行判断如果加权和仍为 NoEdge则输出“无路径！ ”。边从属的路线的判断首先 通过每个路线的链表将所有可能的路线按顺序存储起来，然后通过查找方法找到对应的路线 名称即可。(3) 使用说明：路线数，各站点坐标均为数字。查询方法选择时有效输入为1，2, 3。其他输入会输出特定字符并结束程序。“是否继续时”只有输入y或丫才会继续。gX曰髓二调试程序:3而第1且经过组合它们均可到达同一个地方(d)来测试最少花费的正确(4)调试说明：输入三条线路进行测试。距离、时间问题不大，主要通过

9、设置第一个线路票价为 二、三条线路票价均为 性。大致线路图：情输.人线路的个数;3谙输入第诔路线的站点的个埶器输入各个站点的名称尺坐标日1 1b 3 4e 5 2d 4 6请输入第僚路线钱路的速度，票价!4 3请输入第猱路线的站点的啊请输入各个站点的名称及坐标， a 1 1e 7 4f S 3请输入第凍路銭线路的速度,票价:5 1请输/V第除路线的站点的个数：4请输入各个站点的名称及坐标； g 2 2e7411 3 3)ebugCraiyTrainheed 4 6请输入第3条路线线路的速度,票价：3 1a(3.6, l)-b(2.82, 2)-c(4.12,3)-d(99999, 4)a(6.

10、7, 5)-e(1. 41, 6) -f (99999, 7)g(5.38, 8)-e(l. 41, 9)-h(5,10)-d(99999,11)a(3.6,1)-b(2.82, 2)-c(4. 12,3)-d(99999? 4)-a(6. 7,5)-e(l. 41,6)-f (99999, 7)-g(5 .38, 8)-e(l. 41, 9)-h(5, 10)-d(999995 11)a(3.6,1)-b(2.82, 2)-c(4 12,3)-d(99999, 4)-a(6 7, l)-e(l. 41,5)-f(99999, 6)-g(5 .38,7)-e(l. 41, 5)h(5, 8)-

11、d(99999,4)1 2 3 4 1 5 6 7 5 8 4.bcdefgh3 1 13 4 912 21 23 32 34 43 15 51 56 65 75 57 58 85 84 4899999. 003.6099999.0099999.006. 7099999. 0099999. 0099999. 003. 6099999. 002. 8299999. 0099999.0099999. 0099999.0099999. 0099999.002. 8299999. 004. 1299999. 0099999. 0099999.0099999. 0099999.0099999. 004.

12、 1299999. 0099999.0099999. 0099999.005. 006.7099999. 0099999. 0099999. 0099999. 001. 415.381. 4199999.0099999. 0099999. 0099999. 001.4199999. 0099999.0099999. 0099999.0099999. 0099999. 0099999. 005.3899999. 0099999.0099999. 0099999. 0099999. 0099999.005. 001.4199999. 0099999.0099999. 0099999.000. 90

13、99999. 0099999. 001.3499999. 0099999.0099999. 000. 9099999. 000, 7099999. 0099999. 0099999. 0099999.0099999. 0099999. 000. 7099999. 001. 0399999. 0099999. 0099999.0099999. 0099999.0099999. 001. 0399999. 0099999. 0099999. 0099999.001. 661.3499999. 0099999. 0099999. 0099999.000. 281.790. 4699999.00999

14、99. 0099999. 0099999. 001. 7999999.0099999. 0099999.0099999. 0099999. 0099999. 001.660. 4699999.0099999. 0099999.0099999. 003.0099999. 0099999. 0040099999.0099999. 0099999.003.0099999. 003. 0099999. 0099999. 0099999. 0099999. 0099999.0099999.003.0099999. 003.0099999. 0099999. 0099999. 0099999.009999

15、9.0099999. 003. 0099999. 0099999. 0099999. 0099999. 009.004. 0099999. 0099999.0099999. 0099999. 004. 009. 009. 0099999.0099999. 0099999.0099999. 004. 0099999.0099999. 0099999.0099999. 0099999. 0099999. 0099999. 009. 0099999.0099999. 0099999.0099999. 0099999. 0099999. 009.009. 0099999.0099999. 009999

16、9.00请选择您想选择的查询方法：1 最短路径2. 最小花费3. 最短时间1请输入想查询的起始站与终点站:g bg站到b站的最矩路径长虞:15. 68g站至lj b揶的最短站径 : g - （公交线路3）e （公交线路2）a - （公交线路l）b 是否继绞?请选择您想选择的查询方法；1. 最短路径2最小花费3.最短时间请输入想査询的起始站与终点站；a da站到d站的最少花费：2a站到d站的最省钱路径为：a - （公交线路2）已（公交线路3）h（公交践路3）d 是否继?99请选择您想选择的查询方法：1. 最短壘径2. 最hk.S3. 最短时间和输入想查询的起始站与终点站：? eC站至| e站的最

17、短时间:2.64c站到e站的最省时路径为:c -公交线路l）b - （公交线J&Da - （公交线略戈尢 是否m备选择您想选择的查询方注L最短路径2.最1觉费匕最短时间5*口口 wst be kidding me! !0T2_Process returned 0 （0x0） executian tiine : 67L 064 Press any key to continue.(5)实验代码：1.头文件 SickRoad.h#in clude#in clude#in clude#in cludeusing n amespace std;#defi ne NoEdge 99999无路线int n

18、umber;/公交线路数int count=O;多次出现的地点数int *area;double *price;车票价格数组int *speed;车速数组double *DistanceMap;/以距离为权值的邻接矩阵 double *PriceMap;/以票价为权值的邻接矩阵 double *TimeMap;以时间为权值的邻接矩阵int *numlndex;/车站编号索引 string *nameIndex;/ 车站姓名索引 int *priceIndex;/ 票价索引 int *lpriceIndex;/处理后的票价 int ran ge;/总车站数double Restrict(doub

19、le a)/double 保留两位小数方法 double tem=i nt(a*100);return tem/100;double getDista nce(double a,double b,double c,double d) 求两点间距离方法 return Restrict(sqrt(a-c)*(a-c)+(b-d)*(b-d);class RChai nN ode/链表结点类frie nd class BusRouti ne;frie nd class RCha in;public:stri ng stati on;double px;double py;RChai nN ode *

20、n ext;RChai nN ode *prior;class RChai n/链表类frie nd class BusRouti ne;public:RChai n()first = 0;RChai n();bool lsEmpty()retur n first = 0;int Len gth() con st;RChai nN ode *getFirst() 得到链表头结点return first;RCha in &ln sert(c onst stri ng &s, const double &x,c onst double &y); RChai n &lln sert(RChai nN

21、 ode *rn);void Output(ostream &o ut) con st;stri ng getStati on() 返回站点名return first-station;RCha in & Rearra nge(double & y);RChai n & reCharge(RChain &r);RChai n & dRejudge();private:RChai nN ode *first;RCha in:RCha in()RChai nN ode *n ext;while (first)n ext = first- n ext;delete first;first = n ex

22、t;int RCha in:Le ngth() constRCha inN ode *curre nt = first;in t le n = 0;while (curre nt)len+;curre nt = curre nt-n ext;return len;RChai n & RChai n:l nsert(co nst stri ng &s, const double &x, const double &y)从后插入新结点 if (!first)first = new RCha inN ode;first-stati on = s;first-px = x;first-py = y;f

23、irst- n ext = 0;first-prior = 0;elseRChai nN ode *p = first;while (p-n ext)p = p-n ext;RChai nN ode *r = new RChai nN ode;r-stati on=s;r-px = x;r-py = y;p-n ext = r;r-prior = p;r-n ext=0;return *this;RChai n & RChai n:ll nsert(RChai nN ode *rn)从后插入一个已有结点if(first)RCha inN ode *tem=rn;RChai nN ode *p

24、= first;while (p-n ext)p = p-n ext;p-n ext=tem;tem-prior=p;elsefirst=rn;RCha in & RChai n:Rearra nge(double & y)将车站链表处理，得到距离及对应累加序号 RChai nN ode *Curre nt=first;for(Curre nt; Curre nt- n ext; Curre nt=Curre nt-n ext)RCha inN ode *tem=Curre nt- n ext;Curre nt-px=getDista nce(Curre nt-px,Curre nt-py,t

25、em-px,tem-py); Curren t-py=y;y+;Curren t-px=NoEdge;Curren t-py=y;y+;RCha in & RChai n:reCharge(RChain &r将两个链表连接在一起this-ll nsert(r.getFirst();if(!first)this-first=r.getFirst();return *this;RCha in & RChai n:dRejudge()对链表去重，重新编号ran ge=Le ngth();RChai nN ode *curre nt=first;for(i nt i=0; ipy+=O;curre n

26、t=curre nt-n ext;elseRCha inN ode *temp=first;int flag=0;for(i nt j=0; jstation=temp-station)/ 查找是否有重复站点 curre nt-py=temp-py;flag+;coun t+;/记录重复站点个数 break;temp=temp-n ext;if(!flag)curre nt-py-=co unt;curre nt=curre nt-n ext;return *this; void RChai n:Output(ostream &o ut) con st/ 重载，输出链表 LRChai nN o

27、de *curre nt;for (curre nt = first; curre nt-n ext; curre nt = curre nt- n ext)out stati on (pxpyvv)v; out station ( px , py ) endl;ostream &operator(ostream &out, const RCha in &x) x.Output(out); return out; class BusRout ine/公交车类public:BusRouti ne()Num=0;Speed=0;Stage.first=O;void SetStage(i nt nm

28、,i nt n) 设置几路及站点数Name=nm;Num=n;stri ng s;double x, y;cout 请输入各个站点的名称及坐标： endl; for (i nt j = 0; j s x y;Stage .In sert(s, x, y);void setOthers(i nt s,i nt p) 设置速度及票价Speed=s;Price=p;RChai n & getStage()return Stage;void aOutPut()打印全部信息cout线路vvNamevvendl; cout Stage;coutSpeed: vSpeedvvkm/hvve ndl; cou

29、tPrice: vPricevvRMBvve ndl;void bOutPut()仅打印公交线路cout Stage;int getPrice()/ 获得票价return Price;int getSpeed()/ 获得速度retur n Speed;int getNum()return Num;int getName()return Name;private:int Name;/公交线路编号int Num;int Speed;int Price;RCha in Stage;BusRouti ne *Bus;/ 公交车数组RChai n wholeRoad;/整合后的总路线链表void Cha

30、 nge(BusRout ine *Bus,i nt n)/对每条公交路线进行重排，求距离并编号 double x=1;for(i nt i=0; in; i+)(Busi.getStage().Rearra nge(x); void getNumI ndex()得到各站点序号的索引 Lint all=wholeRoad.Le ngth(); numln dex=new in tall+1; numln dexO=O;RCha inN ode *temp=wholeRoad.getFirst(); for(i nt i=1; ipy; if(i!=all)temp=temp-n ext;voi

31、d numln dexOutPut()for(i nt i=1; i=ra nge; i+) cout vnumln dexi; coute ndlvve ndl;void getNamel ndex()各站点序号与名字的对应关系 ran ge-=co unt;n ame In dex=new stri ngra nge+1;RCha inN ode *temp=wholeRoad.getFirst();n ame In dex0=;for(int i=1; istatio n; if(i!=wholeRoad丄e ngth() temp=temp-n ext;void n amel ndex

32、OutPut()for(i nt i=1; i=ra nge; i+) cout n ame In dexi;coutvve ndlvve ndl;bool searchNo(stri ng a,i nt & b)根据站点名得到其编号 for(i nt i=1; i=ra nge; i+)if(a=n ame In dexi) b=i; return true;E return false; void getPricel ndex() 得到价格索引price In dex=new in t nu mber+1;price In dex0=0; for(i nt i=1; i=nu mber;

33、i+)price In dexi=Busi-1.getPrice();void getlPriceI ndex()得到处理后价格lprice In dex=new in t nu mber+1; lpriceI ndex0=0;for(i nt i=1; i=nu mber; i+) lpriceI ndexi=priceI ndexi*i*i;void price In dexOutPut()for(i nt i=1; i=nu mber; i+) coutvvprice In dexi;coute ndle ndl;void lprice In dexOutPut()for(i nt i=

34、1; i=nu mber; i+) coutlprice In dexi;coute ndle ndl;int searchPrice(i nt p)根据处理后价格查找原价格 for(i nt i=1; i=nu mber; i+) if(p=lprice In dexi) int temp=price In dexi; return temp;retur n NoEdge;void getArea()依此得到各站点中可能出现的边int boun d=2*(wholeRoad.Le ngth()-nu mber)+1;area=new in tbo un d;int i=1,ii=1;int

35、sig n=0;while(i=bo un d-1)for(i nt j=0; j nu mber; j+)for(int k=1; kBusj.getNum(); k+)areai=10* numln dexii+sig n+numln dexii+1+sig n; areai+1=10* numln dexii+sig n+1+numln dexii+sig n; i=i+2;ii+;if(k=Busj.getNum()-1)sig n+;void areaOutPut()int boun d=2*(wholeRoad.Le ngth()-nu mber)+1; for(i nt i=1;

36、 ibo und; i+) coutareai;coute ndle ndl;int areaCheck(i nt a,i nt b)/根据两点判断其从属的路线名int boun d=2*(wholeRoad.Le ngth()-nu mber)+1;int temp=10*a+b;int i=1;for(i; ibo und; i+)if(areai=temp)break;int roadNumber nu mber+1;roadNumber0=0;for(i nt j=1; j=nu mber; j+) roadNumberj=Busj-1.getNum()+roadNumberj-1;f

37、or(i nt j=0; j2*(roadNumberj-j )&i=2*(roadNumberj+1-j-1)return j+1;void getDista nceMap ()/得到以距离为权值的邻接矩阵DistanceMap=new double *range+1;for(i nt i=0; i=ra nge; i+)Dista nceMapi=new doublera nge+1;RChai nN ode *tem=wholeRoad.getFirst();for(i nt i=0; i=ra nge; i+)for(i nt j=0; j=ra nge; j+)Dista nceMa

38、p ij=NoEdge;for(i nt i=1; ipx; Dista nceMap nu ml ndexi+1 nu ml ndexi=tem-px; tem=tem-n ext;void dMapOutPut()打印出以距离为权值的邻接矩阵for(i nt i=1; i=ra nge; i+)for(i nt j=1; j=ra nge; j+)printf( %8.2f ,Dista nceMapij);coute ndl; coute ndl;void getTimeMap()/得到以时间为权值的邻接矩阵TimeMap=new double *ra nge+1; for(i nt i

39、=0; i=ra nge; i+)TimeMapi=new doublera nge+1;for(i nt i=0; i=ra nge; i+)for(i nt j=0; j=ra nge; j+)Time Map ij=Dista nceMap ij;int i=1;while(iwholeRoad 丄en gth()for(i nt j=0； j nu mber; j+)for(int k=0; kBusj.getNum(); k+)if(k!=Busj.getNum()-1)TimeM apnumln dexi nu ml ndexi+1=Restrict(TimeMap numI nd

40、exi numI ndexi+1/Busj.g etSpeed();TimeMap numln dexi+1 numln dexi=TimeMap numln dexi numln dexi+1;i+;if(k=Busj.getNum()-1)i+;void tMapOutPut()打印出以时间为权值的邻接矩阵for(i nt i=1; i=ra nge; i+)for(i nt j=1; j=ra nge; j+)prin tf( %8.2f ,TimeMapij);coute ndl;coute ndl;void getPrice Map ()/得到以时间为权值的邻接矩阵PriceMap=

41、new double *ra nge+1;for(i nt i=0; i=ra nge; i+)PriceMapi=new doublera nge+1;for(i nt i=0; i=ra nge; i+)for(i nt j=0; j=ra nge; j+)PriceM apij=Dista nceMapij;int i=1;while(iwholeRoad 丄en gth()for(i nt j=0； j nu mber; j+)for(int k=0; kBusj.getNum(); k+)if(k!=Busj.getNum()-1)PriceM apn uml ndexi nu ml

42、 ndexi+1=Busj.getPrice()*Busj.getName()*Busj.getName();PriceM apn uml ndexi+1 numI ndexi=Price Mapnu ml ndexi numI ndexi+1; i+;if(k=Busj.getNum()-1)i+;void pMapOutPut()打印出以票价为权值的邻接矩阵for(i nt i=1; i=ra nge; i+)for(i nt j=1; j=ra nge; j+)prin tf( %8.2f ,PriceMapij);coute ndl;coute ndl;/Dijkstra 算法/各数组

43、都从下标1开始double *dist; /表示当前点到源点的最短路径长度int *prev; /记录当前点的前一个结点int line=2*(range-1);/图的结点数和路径数/ range - n no des/ v - the source node/ dist - the distance from the ith node to the source node/ prev - the previous node of the ith node/ c - every two no des dista ncevoid in itialize()dist=new doublera ng

44、e+1;prev=new in tra nge+1;for(i nt i=1; i=ra nge; +i)disti = NoEdge;void Dijkstra(i nt n, int v, double *dist, int *prev, double *c)bool srange+1;/判断是否已存入该点到 S集合中for(i nt i=1; i=n; +i)disti = cvi;si = 0;/初始都未用过该点if(disti = NoEdge)previ = 0;elseprevi = v;distv = 0;sv = 1;/依次将未放入S集合的结点中，取dist最小值的结点，放入

45、结合S中/ 一旦S包含了所有V中顶点，dist就记录了从源点到所有其他顶点之间的最短路径长 度/注意是从第二个节点开始，第一个为源点for(i nt i=2; i=n; +i)int tmp = NoEdge;int u = v;/找出当前未使用的点j的distj最小值for(i nt j=1; j=n; +j)if(!sj) & distjtmp)u = j;/ u保存当前邻接点中距离最小的点的号码tmp = distj;su = 1;/表示u点已存入S集合中/更新distfor(i nt j=1; j=n; +j)if(!sj) & cujNoEdge)double n ewdist =

46、distu + cuj;if(n ewdist distj)distj = n ewdist;prevj = u;/查找从源点V到终点u的路径，并输出void ReDijkstra(i nt n, int v, double *dist, int *prev, double *c)bool srange+1;/判断是否已存入该点到 S集合中for(i nt i=1; i=n; +i)disti = searchPrice(static_cast (cvi);si = 0;/初始都未用过该点if(disti = NoEdge) previ = 0;elseprevi = v;distv = 0;

47、sv = 1;/依次将未放入S集合的结点中，取dist最小值的结点，放入结合S中/ 一旦S包含了所有V中顶点，dist就记录了从源点到所有其他顶点之间的最短路径长 度/注意是从第二个节点开始，第一个为源点for(i nt i=2; i=n; +i)int tmp = NoEdge;int u = v;/找出当前未使用的点j的distj最小值for(i nt j=1; j=n; +j)if(!sj) & distjtmp)u = j;/ u保存当前邻接点中距离最小的点的号码tmp = distj;su = 1;/表示u点已存入S集合中/更新distfor(i nt j=1; j=n; +j)if

48、(!sj) & cujNoEdge)double n ewdist;if(cuprevu!=cuj)/是否与上一边的权值相同 newdist = distu + searchPrice(cuj);/ 不同则加上真正的权值 elsenewdist = distu;/相同则保持原值if(n ewdist =1; -i)if(i != 1)cout n ame In dexquei ; cout(公交线路areaCheck(quei,quei-1)vv);elsecout n ame In dexquei en dl;/完毕0-0void getDRoad(stri ng s,stri ng e)int startp,e ndp;/各数组都从下标1开始/输入结点数if(searchNo(s,startp )&searchNo(e,e ndp)