离上次写北京地铁最短路程换乘已经有一些时间了，本来是昨天晚上写的但是因为有点晚了所以没写！ 写在现在写在这里。
话不多说 直接进入正题！
首先我给出demo 输入比如 五道口，国贸 点击按钮搜索查询即可！
现在我说说我的思路：
S1:加载全部换乘结点 方法Hashtable LoadDC()
DCht.Add("XX", new double[] { -2, -1.4 });
上面是执行的一句代码，XX的坐标即为(-1,-1.4) 用double类型后面要是地铁换乘站在X之前增加了 那就直接写上小于-1.4的，反之大于1.4！ 否则若用int类型那耦合性太高了
这是不用int类型的好处！
S2:加载换乘站之间的关系{Relation for Node} 方法 HashSet<string[]> LoadDD()
b1 = "begin"; b2 = "end"; len = "4.1"; timem = "7"; SWAP(backlist, ref arry, b1, b2, len, timem);
len代表路程(数据来至百度)，timem代表b1到b2的时间！
S3：现在我要查询B到E的最短路程 搜索： B-E 开始
S3_1：如果B，E都是换乘结点比如“西二旗”到“国贸” 那直接进行第四步S4
S3_2:如果B，E中有一个不是换乘结点，执行方法 HashSet<string> GetPreOrNextNode(string stationname)
string[] Linecp = { "西二旗", "生命科学园", "朱辛庄", "巩华城", "沙河", "沙河高教园", "南邵" }; int[] Linecpnode = { 1, 0, 0, 0, 0, 0, 1 }; liststr.Add(Linecp); listint.Add(Linecpnode);
1代表是换乘点或者是X号线的起点，0代表不是换乘结点
hs = new HashSet<string>(tempstr); ///O(1) if (hs.Contains(stationname) == true)
执行hash查找 最优情况下:O(1)
while (pre > -1) { if (tint[pre] == 1) break; pre = pre - 1; } int next = b; while (next < tint.Length) { if (tint[next] == 1) break; next = next + 1; } HashSet<string> hr = new HashSet<string>(); hr.Add(liststr[a][pre]); hr.Add(liststr[a][next]); return hr;
现在返回可能值：(b1x,b1y),(b2x,b2y) 可能值共有C(2,2)+C(3,2)+C(4,2)=10种可能
根据起点B和终点E查询出来了BE附近的可能结点 然后用点到点的距离 找出最多10中可能值的最小值 返回min_b_node,min_e_node
S4：
现在已经有b_node,和e_node 起点和终点附近最短距离的换乘结点，（最短距离不代表最短路程，因为有可能它们之间没有换乘关系） 但不要紧，请看下面：
坐标中从一点出发到另一点的8种情况 直接上代码：
bool CK(bool isadd, double[] bxy, double[] exy) { if (dx >= 0 && dy >= 0 && exy[0] >= bxy[0] && exy[1] >= bxy[1] && exy[0] <= ex && exy[1] <= ey) //1 x增大y增大 isadd = true; else if (dx >= 0 && dy <= 0 && exy[0] >= bxy[0] && exy[1] <= bxy[1] && exy[0] <= ex && exy[1] >= ey)//2 x增大y减小 isadd = true; else if (dx <= 0 && dy >= 0 && exy[0] <= bxy[0] && exy[1] >= bxy[1] && exy[0] >= ex && exy[1] <= ey)//3 x减小y增大 isadd = true; else if (dx <= 0 && dy <= 0 && exy[0] <= bxy[0] && exy[1] <= bxy[1] && exy[0] >= ex && exy[1] >= ey)//4 x减小y减小 isadd = true; else if (dx >= 0 && dy == 0 && exy[0] >= bxy[0] && exy[1] == bxy[1] && exy[1] == ey && exy[0] <= ex)//5 x增大y不变 isadd = true; else if (dx == 0 && dy >= 0 && exy[0] == bxy[0] && exy[1] >= bxy[1] && exy[0] == ex && exy[1] <= ey)//6 x不变y增大 isadd = true; else if (dx <= 0 && dy == 0 && exy[0] <= bxy[0] && exy[1] == bxy[1] && exy[1] == by && exy[0] >= ex)//7 x减小y不变 isadd = true; else if (dx == 0 && dy <= 0 && exy[0] == bxy[0] && exy[1] <= bxy[1] && exy[0] == bx && exy[1] >= ey)//8 x不变 y减小 isadd = true; else isadd = false; return isadd; }
代码我就不用解释了，下面是核心代码
///O(n) foreach (string strbegin in beginlist) { if (strbegin.IndexOf("-") == -1 && mainht.ContainsKey(strbegin) == true)//have this key and first load data { bxy = (double[])DCht[strbegin]; earry = mainht[strbegin].ToString().Split(','); foreach (string ar in earry) { exy = (double[])DCht[ar]; isadd = CK(isadd, bxy, exy); if (isadd == true) { returnlist.Add(strbegin + "-" + ar); isend = 0; } } } else if (strbegin.IndexOf("-") > -1 && mainht.ContainsKey(strbegin.Substring(strbegin.LastIndexOf("-") + 1)) == true) { temgstr = strbegin.Substring(strbegin.LastIndexOf("-") + 1); bxy = (double[])DCht[temgstr]; earry = mainht[temgstr].ToString().Split(',');//exchange node foreach (string ar in earry) { exy = (double[])DCht[ar]; isadd = CK(isadd, bxy, exy); if (isadd == true) { if (!strbegin.Contains(ar)) returnlist.Add(strbegin + "-" + ar); isend = 0; } } } } } earry = null; if (isend == 0) return GetF(returnlist, i); else return null;
到这里本人有个问题请教：
Code1: if (fresult.Contains(temp) == false) fresult.Add(temp);
Code2: fresult.Add(temp);
Code1和Code2有什么区别？ freault为hashset 性能上的？？？？？ 我看了java中的实现过程 但是C#语言看不了实现过程 只看了过程的描述！
后面的实现过程就很简单了！ 找到BE之间尽量短的可能路线的集合然后找出其中最短的路径 程序结束！
测试结果：
程序开始执行时间:20130515115735 734 LoadData begin:20130515115735 734 换乘站全集:Ux begin: 20130515115735734换乘站全集:Ux end: 20130515115735734 LoadData endss:20130515115735 734 GetF() begin:20130515115735:734 GetF() endss:20130515115735:734 五道口-知春路------------->北京西站: 五道口-知春路-西直门-车公庄-白石桥南-北京西站 五道口-知春路-西直门-国家图书馆-白石桥南-北京西站 五道口-知春路-海淀黄庄-国家图书馆-白石桥南-北京西站 count:3 最短路程为:五道口-知春路-海淀黄庄-国家图书馆-白石桥南-北京西站:11.3 程序结束执行时间:20130515115735 734
程序开始执行时间:20130515115844 812 LoadData begin:20130515115844 812 换乘站全集:Ux begin: 20130515115844812换乘站全集:Ux end: 20130515115844812 LoadData endss:20130515115844 812 GetF() begin:20130515115844:812 GetF() endss:20130515115844:812 五道口-知春路------------->国贸: 五道口-知春路-西直门-平安里-西单-东单-建国门-国贸 五道口-知春路-西直门-平安里-东四-东单-建国门-国贸 五道口-知春路-西直门-平安里-东四-朝阳门-建国门-国贸 五道口-知春路-西直门-平安里-东四-朝阳门-呼家楼-国贸 五道口-知春路-北土城-惠新西街南口-芍药居-三元桥-呼家楼-国贸 五道口-知春路-西直门-鼓楼大街-雍和宫-东四-东单-建国门-国贸 五道口-知春路-西直门-鼓楼大街-雍和宫-东四-朝阳门-建国门-国贸 五道口-知春路-西直门-鼓楼大街-雍和宫-东四-朝阳门-呼家楼-国贸 五道口-知春路-西直门-鼓楼大街-雍和宫-东直门-朝阳门-建国门-国贸 五道口-知春路-西直门-鼓楼大街-雍和宫-东直门-朝阳门-呼家楼-国贸 五道口-知春路-西直门-车公庄-复兴门-西单-东单-建国门-国贸 五道口-知春路-西直门-车公庄-平安里-西单-东单-建国门-国贸 五道口-知春路-西直门-车公庄-平安里-东四-东单-建国门-国贸 五道口-知春路-西直门-车公庄-平安里-东四-朝阳门-建国门-国贸 五道口-知春路-西直门-车公庄-平安里-东四-朝阳门-呼家楼-国贸 五道口-知春路-北土城-鼓楼大街-雍和宫-东四-东单-建国门-国贸 五道口-知春路-北土城-鼓楼大街-雍和宫-东四-朝阳门-建国门-国贸 五道口-知春路-北土城-鼓楼大街-雍和宫-东四-朝阳门-呼家楼-国贸 五道口-知春路-北土城-鼓楼大街-雍和宫-东直门-朝阳门-建国门-国贸 五道口-知春路-北土城-鼓楼大街-雍和宫-东直门-朝阳门-呼家楼-国贸 五道口-知春路-北土城-惠新西街南口-雍和宫-东四-东单-建国门-国贸 五道口-知春路-北土城-惠新西街南口-雍和宫-东四-朝阳门-建国门-国贸 五道口-知春路-北土城-惠新西街南口-雍和宫-东四-朝阳门-呼家楼-国贸 五道口-知春路-北土城-惠新西街南口-雍和宫-东直门-朝阳门-建国门-国贸 五道口-知春路-北土城-惠新西街南口-雍和宫-东直门-朝阳门-呼家楼-国贸 五道口-知春路-北土城-惠新西街南口-芍药居-东直门-朝阳门-建国门-国贸 五道口-知春路-北土城-惠新西街南口-芍药居-东直门-朝阳门-呼家楼-国贸 count:27 最短路程为:五道口-知春路-北土城-惠新西街南口-芍药居-三元桥-呼家楼-国贸:16.8 程序结束执行时间:20130515115844 812
献上测试链接 点击我
SF 2013.05.15
END