山大公交線路上優(yōu)化路徑查詢實驗報告

1、山東大學 計算機科學與技術學院數(shù)據(jù)結構課程實驗報告學號：姓名：班級:實驗題目：公交線路上優(yōu)化路徑的查詢實驗學時：32實驗日期： 一硬件環(huán)境： 軟件環(huán)境: 實驗內容與設計：1 .實驗內容： 問題描述：最短路徑問題是圖論中的一個經(jīng)典問題，其中的 Dijkstra算法一直被認為是圖論中的好 算法，但有的時候需要適當?shù)恼{整Dijkstra算法才能完成多種不同的優(yōu)化路徑的查詢。對于某城市的公交線路，乘坐公交的顧客希望在這樣的線路上實現(xiàn)各種優(yōu)化路徑的查 詢。設該城市的公交線路的輸入格式為：線路編號：起始站名（該站坐標）；經(jīng)過的站點1名（該站坐標）；經(jīng)過的站點2名（該站坐 標）； ；經(jīng)過的站點n名（該站坐標

2、）；終點站名（該站坐標）。該線路的乘坐價錢。該線路 平均經(jīng)過多少時間來一輛。車速。例如：63: A（32,45） ; B（76,45） ; C（76,90）;；N（100,100）。1 元。5分鐘。1/每分假定線路的乘坐價錢與乘坐站數(shù)無關，假定不考慮公交線路在路上的交通堵塞。對這樣的公交線路，需要在其上進行的優(yōu)化路徑查詢包括：任何兩個站點之間最便宜的 路徑；任何兩個站點之間最省時間的路徑等等?；疽螅焊鶕?jù)上述公交線路的輸入格式，定義并建立合適的圖模型。針對上述公交線路，能查詢獲得任何兩個站點之間最便宜的路徑，即輸入站名S, T后，可以輸出從SiIJT的最便宜的路徑，/&出格式為：線路

3、x:站名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時間。 實現(xiàn)提示：需深入考慮，應根據(jù)不同的應用目標，即不同的優(yōu)化查詢來建立合適的圖模型。2 .實驗設計：（1）實驗需求：（1）輸入數(shù)據(jù)：總的路線數(shù)目，各路線的站點數(shù)目，各站點的名稱、位置坐標以及各(2)輸出數(shù)據(jù)：輸入數(shù)據(jù)的預處理結果(中間鏈表)與多個索引數(shù)組，三個不同權值 的鄰接矩陣的值(距離，時間，票價)，以及各種不同需求下公交線路的結果。(3)功能：實現(xiàn)在不同查詢條件下最優(yōu)公交線路的輸出。(2)實現(xiàn)思想：首先需要對輸入的數(shù)據(jù)進行預處理。此處運用雙向鏈表來

5、存儲各站點的名稱、橫縱坐標及相對位置關系。然后用一個公交車 Bus類來存儲各個線路的票價、速度及總線路。之后需要整合所有鏈表以生成鄰接矩陣。首先將所有鏈表進行第一步處理，算出相鄰兩 點間距離存入第一個結點中原橫坐標的位置，特別的，每個鏈表最后一個站點對應結點的相同位置則存儲為 NoEdge (99999)。接著將各站點按順序編號存于原鏈表縱坐標位置。接下 來將各路線的鏈表連接在一起形成一個存有全部路線的新鏈表wholeRoad。對wholeRoad進行處理。因為各路線中站點可能出現(xiàn)重復的情況，因此需要對編號進行 去重操作。遍歷鏈表若發(fā)現(xiàn)某站點名出現(xiàn)過兩次或兩次以上，則將第二個以后的編號皆賦成第

6、一個的編號值，同時設置一個變量count來記錄多次出現(xiàn)的的站點數(shù)。count初始值為0, 若出現(xiàn)一次重復則count加1,同時后面所有的編號賦為原編號減去 count。通過以上方法 來解決重復站點問題。根據(jù)最終站點編號建立原始編號與最終編號的索引數(shù)組和最終編號與站點名的索引數(shù) 組，并提供逆向查找方法。最后生成以距離為鄰接矩陣時依照的就是最終的編號。不過在生 成過程中還是按照總線路鏈表進行循環(huán)，遍歷總路線鏈表并根據(jù)索引將對應的距離存入真正 的位置，其他位置均設為 NoEdge而生成以時間為權值和以票價為權值的鄰接矩陣過程基 本一樣，只不過是將對應位置的值除相應速度或換為相應票價乘上線路編號的平方

7、(原因下方解釋)。在最終鄰接矩陣處理中主要運用 Dijkstra 算法。在時間最少與距離最短查詢時直接使 用Dijkstra 算法即可。然而在票價最少時需要對算法進行調整。因為坐公交車時在一條線 路上一直乘坐只需要交一次車票錢因此不能直接將票價進行累加，然而不同線路間也可能存在票價相同的情況，因此也不能直接運用只要和上一條路線票價相同就不進行累加的方法。 為了避免不同線路票價權值相同，在賦值前先進行預處理，將票價改為相應票價乘上線路編 號的平方，并建立索引以及添加一個尋找原票價的方法。因此對于最少花費查詢，只需在 Dijkstra 算法中加上尋找原票價的方法以及判斷將要添加的路徑的權值是否與上

8、一條相同 的步驟。最終結果是將存的點按索引轉化為對應的站點名后按順序輸出，并將最小加權一并輸 出。先進行判斷如果加權和仍為NoEdge則輸出“無路徑！ ”。邊從屬的路線的判斷首先通過每個路線的鏈表將所有可能的路線按順序存儲起來，然后通過查找方法找到對應的路線 名稱即可。(3)使用說明：路線數(shù)，各站點坐標均為數(shù)字。查詢方法選擇時有效輸入為1, 2, 3。其他輸入會輸出特定字符并結束程序?！笔欠窭^續(xù)時”只有輸入y或Y才會繼續(xù)。調試說明：輸入三條線路進行測試。距離、時間問題不大，主要通過設置第一個線路票價為3而第二、三條線路票價均為1且經(jīng)過組合它們均可到達同一個地方（d）來測試最少花費的正確 性。大

9、致線路圖：調試程序：D;5tudyprc g ramCraiyT rainbi nDebugCrazyT ra in.e>e一 X請輸入線路的個數(shù);3請輸入第1條路線的站點的個數(shù)，3輸入各個站點的名稱及坐標;a 1 1b 3 4e 5 2d 4 6清輸入第1條路線線路的速度,票價!4 3請榆入第2條路線的站點的個數(shù).請輸入各個站點的名稱及坐標：a 1 1e 7 4f S 3請輸入第2條路線線路的速度,票價:5 1請輸入第3條路線的站點的個數(shù),4請輸入各個站點的名稱及坐標1g 2 2e7411 3 3d 4 6請輸入第3條路線線路的速度,票價：3 1a(3. 6, l)->b(2.

10、82, 2)->c(4. 12,3)->d(99999, 4)a(6.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 (9999% 7)->g(5 .38,8)->e(l. 41, 9) ->h(5, 10)->d(999,11)a(3.6, l)->

11、b(2.82, 2)->c(4. 12,3)->d(99999, 4)->a(6, 7, l)->eCl. 41,5)->f(99999, 6)->g(5 .38,7)->e(l. 41, 5)->h(5, 8)->d(99999,4)1 2 3 4 1 5 6 7 5 8 4abcdefgh3 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. 60999

12、99. 002. 8299999. 0099999.0099999. 0099999.0099999. 0099999. 002. 8299999. 004. 1299999.0099999. 0099999.0099999. 0099999.0099999. 004. 1299999. 0099999.0099999. 0099999.005. 006.7099999. 0099999. 0099999. 0099999. 001. 415.381. 4199999.0099999. 0099999. 0099999. 001.4199999. 0099999.0099999. 009999

13、9.0099999. 0099999. 0099999. 005.3899999. 0099999.0099999. 0099999.0099999. 0099999.005. 001.4199999. 0099999.0099999. 0099999.000. 9099999. 0099999. 001.3499999. 0099999.0099999. 000. 9099999. 000. 7099999. 0099999.0099999. 0099999.0099999. 0099999.000. 7099999. 001. 0399999.0099999. 0099999.009999

14、9. 0099999.0099999. 001. 0399999. 0099999. 0099999. 0099999.001. 661.3499999. 0099999. 0099999. 0099999.000. 281.790. 4699999.0099999.0099999.003.0099999.0099999.004. 0099999.0099999. 0099999.00ggggg. oo99999. 003.0099999. 003.0099999. 0099999. 0099999. 0099999. 0099999. 0099999. 0099999. 0099999. 0

15、03. 0099999.003.0099999. 0099999.0099999. 0099999. 00999gg. 001.6699999. 00ggggg. oo3.0099999. 0099999. 0099999. 0099999. 009.001. 790. 464. 0099999. 0099999. 0099999. 0099999. 004. 009. 009. 0099999.0099999.0099999.0099999.0099999.0099999.004. 0099999.0099999.0099999.00999gg. 0099999. 0099999. 0099

16、999. 0099999. 0099999. 009. 0099999. 0099999. 0099999. 0099999.0099999.0099999.0099999.0099999.009.009. 0099999.0099999.0099999.00請選擇您想選擇的查詢方法：L最迪路徑2 .最小花費3 .最短時間1請輸入想查詢的起始站與終點站：g bg站到b站的最處路徑長度：68g就薊b患的最短藍徑為: g -> （公交線路3）e -> （公交線路2）a（公交線路l）b是否繼續(xù)?<Y/N> 請選擇您想選擇的查詢方法；1 .最短路徑2 .最小花費3 .最短時間n

17、 乙 請輸入想查詢的起始站與終點站；a da站到d站的最少花費：2a站到d站的最省錢路徑為：a -> （公交線路2） e -> （公交線路3）h -> （公交線路3）d 是否繼續(xù)99清選擇您想選擇的查詢方法：1 .最短電徑2 .最小花費3 .最短時間工輸入想查詢的起始站與終點站：e站到e站的最短時間：2.94c站到e站的最省時路徑為：c -> （公交線路Db -> （公交線路4 （公交線路2儲 是否維續(xù)?<"N>解選擇您想選擇的查詢方法，L最短路徑2 ,最“訛費3.最短時間5心口口 wst be kidding me! !0T2_Proces

18、s returripd 0 （0x0）executi an tiine : 671.064 £Press any key to continue.(5)實驗代碼：頭文件 SickRoad.h#include<iostream>#include<string>#include<cmath>#include<cstdio>using namespace std;#define NoEdge 99999/無路線int number;/公交線路數(shù)int count=0;/多次出現(xiàn)的地點數(shù)int *area;double *price;車票價格數(shù)

19、組int *speed;/車速數(shù)組double *DistanceMap;/以距離為權值的鄰接矩陣double *PriceMap;/以票價為權值的鄰接矩陣double *TimeMap;/以時間為權值的鄰接矩陣int *numIndex;/車站編號索引string *nameIndex;/ 車站姓名索引int *priceIndex;/ 票價索引int *lpriceIndex;/處理后的票價int range;/總車站數(shù)double Restrict(double a)/double 保留兩位小數(shù)方法 double tem=int(a*100);return tem/100;double

20、getDistance(double a,double b,double c,double d)/求兩點間距離方法 return Restrict(sqrt(a-c)*(a-c)+(b-d)*(b-d);class RChainNode/1表結點類friend class BusRoutine;friend class RChain;public:string station;double px;double py;RChainNode *next;RChainNode *prior;class RChain/糖表類friend class BusRoutine;public:RChain()

21、first = 0;RChain();bool IsEmpty() return first = 0;int Length() const;RChainNode *getFirst()得到鏈表頭結點 return first;RChain &Insert(const string &s, const double &x,const double &y);RChain &IInsert(RChainNode *rn);void Output(ostream &out) const;string getStation() 返回站點名return fi

22、rst->station;RChain &Rearrange(double &y);RChain &reCharge(RChain &r);RChain &dRejudge();private:RChainNode *first;；RChain:RChain()RChainNode *next;while (first)next = first->next;delete first;first = next;int RChain二Length() constRChainNode *current = first;int len = 0;whi

23、le (current)len+;current = current->next;return len;RChain &RChain二Insert(const string &s, const double &x, const double &y)從后插入新結點 if (!first)first = new RChainNode;first->station = s;first->px = x;first->py = y;first->next = 0;first->prior = 0;_else RChainNode *p

24、= first; while (p->next) p = p->next;RChainNode *r = new RChainNode; r->station=s;r->px = x; r->py = y; p->next = r; r->prior = p; r->next=0; return *this;RChain &RChain:IInsert(RChainNode *rn)以后插入一個已有結點 if(first) RChainNode *tem=rn;RChainNode *p = first; while (p->nex

25、t) p = p->next;p->next=tem; tem->prior=p; else first=rn;RChain &RChain二Rearrange(double &y)/1車站鏈表處理，得到距離及對應累加序號 RChainNode *Current=first;for(Current; Current->next; Current=Current->next) RChainNode *tem=Current->next;Current->px=getDistance(Current->px,Current->p

26、y,tem->px,tem->py);Current->py=y;y+;Current->px=NoEdge;Current->py=y;y+;RChain &RChain:reCharge(RChain &r潮兩個鏈表連接在一起 this->IInsert(r.getFirst();if(!first)this->first=r.getFirst(); return *this;RChain &RChain二dRejudge()對鏈表去重，重新編號range=Length();RChainNode *current=first

27、;for(int i=0; i<Length(); i+)if(i=0)current->py+=0;current=current->next;else RChainNode *temp=first; int flag=0;for(int j=0; j<i; j+) if(current->station=temp->station) 查找是否有重復站點 current->py=temp->py; flag+;count+;/記錄重復站點個數(shù) break; temp=temp->next;if(!flag) current->py-

28、=count;current=current->next;return *this; void RChain二Output(ostream &out) const/重載，輸出鏈表RChainNode *current;for (current = first; current->next; current = current->next)out << current->station << '('<<current->px<<','<<current->py&

29、lt;<')'<<"->"out << current->station << '(' << current->px << ',' << current->py << ')' << endl; ostream &operator<<(ostream &out, const RChain &x)x.Output(out);return out; clas

30、s BusRoutine/公交車類public:BusRoutine()Num=0;Speed=0;Stage.first=0;void SetStage(int nm,int n)/設置幾路及站點數(shù)Name=nm;Num=n;string s;double x, y;cout << "請輸入各個站點的名稱及坐標："<< endl;for (int j = 0; j < n; j+)cin >> s >> x >> y;Stage.Insert(s, x, y);void setOthers(int s,in

31、t p)/ 設置速度及票價Speed=s;Price=p;RChain &getStage()return Stage;void aOutPut()打印全部信息cout<<"線路"<<Name<<endl;cout << Stage;cout<<"Speed: "<<Speed<<"km/h"<<endl;cout<<"Price: "<<Price<<"RMB&qu

32、ot;<<endl;void bOutPut()僅打印公交線路cout << Stage;int getPrice()/ 獲得票價return Price;int getSpeed()/獲得速度return Speed;int getNum() return Num;int getName() return Name;private:int Name;/公交線路編號int Num;int Speed;int Price;RChain Stage;BusRoutine *Bus;/公交車數(shù)組RChain wholeRoad;/SE合后的總路線鏈表void Change(B

33、usRoutine *Bus,int n)/對每條公交路線進行重排，求距離并編號 double x=1;for(int i=0; i<n; i+)(Busi.getStage().Rearrange(x);void getNumIndex()/得到各站點序號的索引Iint all=wholeRoad.Length();numIndex=new intall+1;numIndex0=0;RChainNode *temp=wholeRoad.getFirst();for(int i=1; i<=all; i+)numIndexi=temp->py;if(i!=all) temp=

34、temp->next;void numIndexOutPut()for(int i=1; i<=range; i+) cout<<numIndexi<<""cout<<endl<<endl;void getNameIndex()/各站點序號與名字的對應關系range-=count;nameIndex=new stringrange+1;RChainNode *temp=wholeRoad.getFirst();nameIndex0=""for(int i=1; i<=wholeRoad.L

35、ength(); i+)nameIndexnumIndexi=temp->station;if(i!=wholeRoad.Length() temp=temp->next;void nameIndexOutPut()for(int i=1; i<=range; i+) cout<<nameIndexi<<""cout<<endl<<endl;bool searchNo(string a,int &b)/根據(jù)站點名得到其編號for(int i=1; i<=range; i+)if(a=nameIn

36、dexi)b=i;return true;return false;void getPriceIndex()得至 ij 價格索弓 IpriceIndex=new intnumber+1;priceIndex0=0;for(int i=1; i<=number; i+)priceIndexi=Busi-1.getPrice();void getlPriceIndex()/得到處理后價格lpriceIndex=new intnumber+1;lpriceIndex0=0;for(int i=1; i<=number; i+)lpriceIndexi=priceIndexi*i*i;vo

37、id priceIndexOutPut()for(int i=1; i<=number; i+) cout<<priceIndexi<<""cout<<endl<<endl;void lpriceIndexOutPut()for(int i=1; i<=number; i+) cout<<lpriceIndexi<<"" cout<<endl<<endl;int searchPrice(int p)/根據(jù)處理后價格查找原價格for(int i=1;

38、 i<=number; i+)if(p=lpriceIndexi)int temp=priceIndexi;return temp;return NoEdge;void getArea()/依此得到各站點中可能出現(xiàn)的邊 int bound=2*(wholeRoad.Length()-number)+1; area=new intbound;int i=1,ii=1;int sign=0;while(i<=bound-1)for(int j=0; j<number; j+)for(int k=1; k<Busj.getNum(); k+)areai=10*numIndex

39、ii+sign+numIndexii+1+sign;areai+1=10*numIndexii+sign+1+numIndexii+sign;i=i+2;ii+;if(k=Busj.getNum()-1)sign+;void areaOutPut()int bound=2*(wholeRoad.Length()-number)+1; for(int i=1; i<bound; i+)cout<<areai<<""cout<<endl<<endl;int areaCheck(int a,int b)/根據(jù)兩點判斷其從屬的路

40、線名 int bound=2*(wholeRoad.Length()-number)+1;int temp=10*a+b;int i=1;for(i; i<bound; i+)if(areai=temp)break;int roadNumbernumber+1;roadNumber0=0;for(int j=1; j<=number; j+)roadNumberj=Busj-1.getNum()+roadNumberj-1;for(int j=0; j<number; j+)if(i>2*(roadNumberj-j)&&i<=2*(roadNum

41、berj+1-j-1)return j+1;void getDistanceMap()/得到以距離為權值的鄰接矩陣DistanceMap=new double *range+1;for(int i=0; i<=range; i+)DistanceMapi=new doublerange+1;RChainNode *tem=wholeRoad.getFirst();for(int i=0; i<=range; i+)for(int j=0; j<=range; j+)DistanceMapij=NoEdge;for(int i=1; i<=wholeRoad.Length

42、()-1; i+)DistanceMapnumIndexinumIndexi+1=tem->px;DistanceMapnumIndexi+1numIndexi=tem->px; tem=tem->next;void dMapOutPut()打印出以距離為權值的令口接矩陣for(int i=1; i<=range; i+)for(int j=1; j<=range; j+)printf(" %8.2f ”,DistanceMapij);cout<<endl;cout<<endl;void getTimeMap()/得到以時間為權值

43、的鄰接矩陣TimeMap=new double *range+1;for(int i=0; i<=range; i+)TimeMapi=new doublerange+1;for(int i=0; i<=range; i+)for(int j=0; j<=range; j+)TimeMapij=DistanceMapij;int i=1;while(i<wholeRoad.Length()for(int j=0; j<number; j+)for(int k=0; k<Busj.getNum(); k+)if(k!=Busj.getNum()-1)TimeM

44、apnumIndexinumIndexi+1=Restrict(TimeMapnumIndexinumIndexi+1/Busj.g etSpeed();TimeMapnumIndexi+1numIndexi=TimeMapnumIndexinumIndexi+1;i+；if(k=Busj.getNum()-1) i+；void tMapOutPut()打印出以時間為權值的鄰接矩陣for(int i=1; i<=range; i+)for(int j=1; j<=range; j+)printf(" %8.2f ”,TimeMapij);cout<<endl;

45、 cout<<endl;void getPriceMap()/得到以時間為權值的鄰接矩陣PriceMap=new double *range+1;for(int i=0; i<=range; i+)PriceMapi=new doublerange+1;for(int i=0; i<=range; i+)for(int j=0; j<=range; j+) PriceMapij=DistanceMapij;int i=1;while(i<wholeRoad.Length()_for(int j=0; j<number; j+) for(int k=0;

46、 k<Busj.getNum(); k+)if(k!=Busj.getNum()-1) PriceMapnumIndexinumIndexi+1=Busj.getPrice()*Busj.getName()*Busj.getName();PriceMapnumIndexi+1numIndexi=PriceMapnumIndexinumIndexi+1;i+；if(k=Busj.getNum()-1) i+；void pMapOutPut()打印出以票價為權值的令口接矩陣for(int i=1; i<=range; i+)for(int j=1; j<=range; j+)pr

47、intf(" %8.2f ”,PriceMapij);cout<<endl;cout<<endl;/Dijkstra 算法/各數(shù)組都從下標1開始double *dist; /表示當前點到源點的最短路徑長度int *prev; /記錄當前點的前一個結點int line=2*(range-1);/圖的結點數(shù)和路徑數(shù)/ range - n nodes/ v - the source node/ dist - the distance from the ith node to the source node/ prev - the previous node of t

48、he ith node/ c - every two nodes' distancevoid initialize。dist=new doublerange+1;prev=new intrange+1;for(int i=1; i<=range; +i)disti = NoEdge;void Dijkstra(int n, int v, double *dist, int *prev, double *c)bool srange+1; /判斷是否已存入該點到 S集合中for(int i=1; i<=n; +i) disti = cvi;si = 0;/初始都未用過該點if(

49、disti = NoEdge)previ = 0; elseprevi = v;distv = 0;sv = 1;/依次將未放入S集合的結點中，取dist口最小值的結點，放入結合S中/ 一旦S包含了所有V中頂點，dist就記錄了從源點到所有其他頂點之間的最短路徑長 度/注意是從第二個節(jié)點開始，第一個為源點for(int i=2; i<=n; +i)int tmp = NoEdge;int u = v;/找出當前未使用的點j的distj最小值for(int j=1; j<=n; +j)if(!sj) && distj<tmp) u = j;/ u保存當前鄰接點中

50、距離最小的點的號碼tmp = distj;su = 1;/表示u點已存入S集合中/更新distfor(int j=1; j<=n; +j)if(!sj) && cuj<NoEdge) double newdist = distu + cuj;if(newdist < distj) distj = newdist;prevj = u;/查找從源點v到終點u的路徑，并輸出void ReDijkstra(int n, int v, double *dist, int *prev, double *c) bool srange+1; /判斷是否已存入該點到 S集合中f

51、or(int i=1; i<=n; +i)disti = searchPrice(static_cast<int>(cvi);si = 0;/初始都未用過該點if(disti = NoEdge)previ = 0;elseprevi = v;distv = 0;sv = 1;/依次將未放入S集合的結點中，取dist口最小值的結點，放入結合S中/ 一旦S包含了所有V中頂點，dist就記錄了從源點到所有其他頂點之間的最短路徑長 度/注意是從第二個節(jié)點開始，第一個為源點for(int i=2; i<=n; +i)int tmp = NoEdge;int u = v;/找出當前

52、未使用的點j的distj最小值for(int j=1; j<=n; +j)if(!sj) && distj<tmp)u = j;/ u保存當前鄰接點中距離最小的點的號碼tmp = distj;su = 1;/表示u點已存入S集合中/更新distfor(int j=1; j<=n; +j)if(!sj) && cuj<NoEdge)double newdist;if(cuprevu!=cuj)/是否與上一邊的權值相同newdist = distu + searchPrice(cuj);/不同貝 U 力口上真正的權值 elsenewdist

53、= distu;/相同則保持原值if(newdist < distj) distj = newdist; prevj = u;/查找從源點v到終點u的路徑，并輸出void searchPath(int *prev,int v, int u)int querange+1;int tot = 1;quetot = u;tot+;int tmp = prevu;while(tmp != v)quetot = tmp;tot+;tmp = prevtmp;quetot = v;for(int i=tot; i>=1; -i)if(i != 1)cout << nameIndex

54、quei << "-> "cout<<"(公交線路"<<areaCheck(quei,quei-1)<<")" elsecout << nameIndexquei << endl;/完畢0-0void getDRoad(string s,string e)int startp,endp;/各數(shù)組都從下標1開始/輸入結點數(shù)if(searchNo(s,startp)&&searchNo(e,endp)initialize。;Dijkstra(ra

55、nge, startp, dist, prev, DistanceMap);/最短路徑長度if(distendp=NoEdge)cout<<"不可達！ ！ ！ "<<endl;elsecout << s<<"站至U "<<e<<”站的最短路徑長度："<< distendp << endl;/路徑cout << s<<"站至U "<<e<<”站的最短路徑為：" searchP

56、ath(prev, startp, endp);elsecout<<"No Such Station! ! "<<endl;void getTRoad(string s,string e)int startp,endp;/各數(shù)組都從下標1開始/輸入結點數(shù)if(searchNo(s,startp)&&searchNo(e,endp)initialize。;Dijkstra(range, startp, dist, prev, TimeMap);/最短路徑長度cout << s<<"站至U "&

57、lt;<e<<"站的最短時間："<< distendp << endl;/路徑cout << s<<"站至I "<<e<<"站的最省時路徑為：" searchPath(prev, startp, endp);elsecout<<"No Such Station! ! "<<endl;void getPRoad(string s,string e)int startp,endp;/各數(shù)組都從下標1開始/輸入結點數(shù)if(searchNo(s,startp)&&searchNo(e,endp)initialize。;ReDijkstra(range, startp, dist, prev, PriceMap);/最短路徑長度cout << s<<"站至U "<<e<<”站的最少