北京地铁线路图纯算法附带求极权值(原创) 性能提升版
先上一張大家都看過而且熟悉的北京地鐵線路圖：
?
其中本人由于時間時間問題所以就寫入了：昌平線,1,2,4,5,6,8,10,13共9條線路圖：
接下來我說說我的思路 我的思路是這樣的：
首先定義變量b，e分別代表用戶搜索的開始地點和到達地點
然后加載地鐵線路圖主數據，下文代碼中的LoadData()方法 ，此時要說明一點LoadData()方法加載的數據即是北京地鐵線路圖換乘的所有地鐵站，放在一個有序的集合里，
【此處要ps一下，后面我會用int類型的value代表各個地鐵站換乘的站名稱再放在一個有序的容器里(放入方法可用選擇排序)，這樣做的目的是為了后面代碼高性能查找(以O(lgn)的二分法快速查找)】 先說到這里 后期會用此方法！
下面開始，為了便于表達本人用偽代碼表示
?設置北京地鐵線路圖換乘的所有地鐵站的集合為Ux, GetLine(string stationname),函數GetPreOrNextNode(string stationname)
?GetLine方法代表根據地鐵站名稱查找所在的地鐵線，GetPreOrNextNode方法代表根據地鐵站名稱查找周圍的換乘站(換乘結點)
0：如果b,e都為結點(換乘站) 直接進行第3步；
1:string[] nodebegin= Getline(b);string [] nodeend=gteline(e);
2:把1中的nodebegin和nodeend放入Ux集合中；
3:把nodebegin，nodeend傳入方法 ?GetF() 進行遞歸操作;
這里我給出GetF()代碼的一部分，要是要完整代碼請使勁 ?點擊我
1 List<string> GetF(List<string> beginlist) 2 { 3 if (maindata == null) return null; 4 5 List<string> returnlist = new List<string>(); 6 if (beginlist.Count == 0) 7 isend = 1; 8 else 9 { 10 foreach (string fs in beginlist) 11 { 12 if (fresult.Contains(fs) == false) 13 fresult.Add(fs); 14 } 15 //此處省略了 比較復雜31 } 32 if (isend == 0) 33 return GetF(returnlist); 34 else 35 return null; 36 }關于GetF() 方法原理可以這樣理解：我們已經知道開始結點和結束結點，所以我們不用遞歸整個換乘結點，那么我們將除開開始結點和結束結點之外的結點給移除，這里的問題來了，
QA：我怎么知道什么結點該移除呢？
AN：因為我沒能求的極權值，依次把極大的權值相關的結點除去。
這里要用到方法的核心了 貼一張圖給看看：
?Dijkstra無向圖算法！ 因為我們知道換乘是雙向的，不是單向的！
?ps:之前用的遞歸性能很低，由于代碼的繁瑣思維的混亂！
?
說了這么多我給出運行結果：
?
?
?
?
測試1：五道口----前門(非換乘站)
?
程序測試開始時間：2013 04 26 19 50 00 124
程序測試結束時間：2013 04 26 19 50 01 265
?
五道口------------->前門:
五道口-知春路-大鐘寺-西直門-車公莊-阜成門-復興門-長椿街-宣武門-和平門-前門
五道口-知春路-大鐘寺-西直門-車公莊-阜成門-復興門-西單-宣武門-和平門-前門
五道口-知春路-大鐘寺-西直門-車公莊-平安里-西四-靈境胡同-西單-宣武門-和平門-前門
五道口-知春路-大鐘寺-西直門-新街口-平安里-西四-靈境胡同-西單-宣武門-和平門-前門
五道口-知春路-大鐘寺-西直門-新街口-平安里-車公莊-阜成門-復興門-長椿街-宣武門-和平門-前門
五道口-知春路-大鐘寺-西直門-新街口-平安里-車公莊-阜成門-復興門-西單-宣武門-和平門-前門
五道口-知春路-大鐘寺-西直門-車公莊-平安里-西四-靈境胡同-西單-復興門-長椿街-宣武門-和平門-前門
五道口-知春路-大鐘寺-西直門-新街口-平安里-西四-靈境胡同-西單-復興門-長椿街-宣武門-和平門-前門
五道口-知春路-大鐘寺-西直門-積水潭-鼓樓大街-安定門-雍和宮-東直門-東四十條-朝陽門-建國門-北京站-崇文門-前門
.
.此處省略n個 要想看全部 請點擊我
.
count:774
權最大為:五道口-上地-西二旗-龍澤-回龍觀-霍營-立水橋-北苑-望京西-芍藥居-太陽宮-三元橋-亮馬橋-農業展覽館-團結湖-呼家樓-金臺夕照-國貿-雙井-勁松-潘家園-十里河-分鐘寺-成壽寺-宋家莊-石榴莊-大紅門-角門西-馬家堡-北京南站-陶然亭-菜市口-宣武門-西單-靈境胡同-西四-平安里-車公莊-阜成門-復興門-南禮士路-木樨地-軍事博物館-公主墳-西釣魚臺-慈壽寺-車道溝-長春橋-火器營-巴溝-蘇州街-海淀黃莊-人民大學-魏公村-國家圖書館-動物園-西直門-積水潭-鼓樓大街-安定門-雍和宮-東直門-東四十條-朝陽門-建國門-北京站-崇文門-前門:106.463
權最小為:五道口-知春路-大鐘寺-西直門-車公莊-阜成門-復興門-長椿街-宣武門-和平門-前門:14.204
?
測試2：西二旗----西單(換乘站)
程序測試開始時間：2013 04 26 20 00 03 526
程序測試結束時間：2013 04 26 20 00 04 854
西二旗------------->西單:
西二旗-西直門-平安里-西單
西二旗-西直門-車公莊-復興門-西單
西二旗-西直門-車公莊-復興門-宣武門-西單
西二旗-西直門-鼓樓大街-雍和宮-東四-東單-西單
西二旗-霍營-北土城-鼓樓大街-西直門-平安里-西單
西二旗-西直門-車公莊-復興門-宣武門-崇文門-東單-西單
西二旗-西直門-國家圖書館-海淀黃莊-慈壽寺-公主墳-復興門-西單
西二旗-霍營-立水橋-惠新西街南口-雍和宮-東四-東單-西單
西二旗-霍營-北土城-鼓樓大街-西直門-車公莊-復興門-西單
西二旗-霍營-北土城-鼓樓大街-雍和宮-東四-東單-西單
西二旗-霍營-北土城-惠新西街南口-雍和宮-東四-東單-西單
西二旗-西直門-鼓樓大街-北土城-惠新西街南口-雍和宮-東四-東單-西單
西二旗-西直門-鼓樓大街-雍和宮-東四-東單-崇文門-宣武門-西單
西二旗-西直門-鼓樓大街-雍和宮-東直門-朝陽門-建國門-東單-西單
西二旗-西直門-車公莊-復興門-宣武門-崇文門-建國門-東單-西單
西二旗-西直門-國家圖書館-海淀黃莊-慈壽寺-公主墳-復興門-宣武門-西單
西二旗-霍營-立水橋-惠新西街南口-雍和宮-鼓樓大街-西直門-平安里-西單
西二旗-霍營-立水橋-惠新西街南口-北土城-鼓樓大街-西直門-平安里-西單
西二旗-霍營-北土城-鼓樓大街-西直門-車公莊-復興門-宣武門-西單
西二旗-霍營-北土城-知春路-海淀黃莊-國家圖書館-西直門-平安里-西單
西二旗-霍營-北土城-知春路-海淀黃莊-慈壽寺-公主墳-復興門-西單
西二旗-霍營-北土城-惠新西街南口-雍和宮-鼓樓大街-西直門-平安里-西單
西二旗-西直門-鼓樓大街-北土城-知春路-海淀黃莊-慈壽寺-公主墳-復興門-西單
西二旗-西直門-鼓樓大街-雍和宮-東四-東單-崇文門-宣武門-復興門-西單
西二旗-西直門-鼓樓大街-雍和宮-東四-東單-建國門-崇文門-宣武門-西單
西二旗-西直門-鼓樓大街-雍和宮-東直門-朝陽門-建國門-崇文門-東單-西單
西二旗-西直門-鼓樓大街-雍和宮-東直門-朝陽門-建國門-崇文門-宣武門-西單
西二旗-西直門-車公莊-復興門-宣武門-角門西-宋家莊-崇文門-東單-西單
西二旗-霍營-立水橋-望京西-芍藥居-東直門-雍和宮-東四-東單-西單
西二旗-霍營-立水橋-望京西-芍藥居-東直門-朝陽門-建國門-東單-西單
.
.此處省略n個 要想看全部?請點擊我
.
count:4602
權最大為:西二旗-西直門-車公莊-復興門-公主墳-慈壽寺-海淀黃莊-知春路-北土城-霍營-立水橋-望京西-芍藥居-三元橋-呼家樓-國貿-宋家莊-角門西-宣武門-崇文門-建國門-朝陽門-東直門-雍和宮-東四-東單-西單:117.337
權最小為:西二旗-西直門-平安里-西單:18.4
?
?
最后我我發現百度地圖計算不準確了：
解釋如下 先看看本人的部分換乘數據：len表示b1到b2之間的路程(this date from baidu map),timem代表時間，但是我還沒用到timem次字段，預留為后期做準備！
昌平線,1,2,4,5,8,10,13, :1號線開始
b1 = "蘋果園";
b2 = "公主墳";
len = "12.7";
timem = "22";
SWAP(backlist, ref arry, b1, b2, len, timem);
b1 = "復興門";
b2 = "公主墳";
len = "4";
timem = "8";
SWAP(backlist, ref arry, b1, b2, len, timem);
b1 = "復興門";
b2 = "西單";
len = "1.7";
timem = "3";
SWAP(backlist, ref arry, b1, b2, len, timem);
b1 = "東單";
b2 = "西單";
len = "3.6";
timem = "8";
SWAP(backlist, ref arry, b1, b2, len, timem);
b1 = "東單";
b2 = "建國門";
len = "2.3";
timem = "3";
SWAP(backlist, ref arry, b1, b2, len, timem);
b1 = "國貿";
b2 = "建國門";
len = "2.8";
timem = "4";
SWAP(backlist, ref arry, b1, b2, len, timem);
b1 = "國貿";
b2 = "四惠惠";
len = "3";
timem = "6";
SWAP(backlist, ref arry, b1, b2, len, timem);
b1 = "四惠東";
b2 = "四惠惠";
len = "1.7";
timem = "3";
SWAP(backlist, ref arry, b1, b2, len, timem);
b1 = "四惠東";
b2 = "土橋";
len = "16.6";
timem = "29";
SWAP(backlist, ref arry, b1, b2, len, timem);
昌平線,1,2,4,5,8,10,13, :1號線end
?
看到了“權最小為:西二旗-西直門-平安里-西單:18.4”
我再搜百度的：?是19km
我的是18.4 km ， ? 小于百度的搜索數據 ? ? 還有一系列問題等待這去解決！?
熱烈歡迎大家發表自己的意見和其他！
?
下篇再見！?
?
BY:SF
time: 2013-04-26-20:21
?
轉載于:https://www.cnblogs.com/chinhi/archive/2013/04/26/bejingsbwmap.html
總結
以上是生活随笔為你收集整理的北京地铁线路图纯算法附带求极权值(原创) 性能提升版的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： [Serializable]序列化一句话
- 下一篇： 蓝桥杯比武问题