北京地铁换乘算法(二维坐标系，图的深度搜索)开源下载Android源码、性能最优解,附带C#版本
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了北京地铁换乘算法(二维坐标系，图的深度搜索)开源下载Android源码、性能最优解,附带C#版本，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含47632字，纯文字阅读大概需要69分钟。
内容图文
距离2012年11月2日下午2:05:31 已经过去158751270这么多秒了，不小心暴露了我的当前时间。
java代码贴出来。
private
static
long
gettimelong() {
long result = new Date().getTime() - new Date("2012/11/02 14:05:31").getTime();
return result / 1000;
}
接下来是介绍北京地体换乘算法的最优解，比如程序随便运行一下是这样的result：
程序开始执行时间:20171113101010 82
五道口------------->阜成门:
最短路程为:五道口-知春路-西直门-车公庄-阜成门(4.937 km)
程序结束执行时间:20171113101010 184
我这是web版本，加上程序的执行还有网络的阻塞时间定义为t、则t=184-82=102（ms）
想要C#版本，请留下您的邮箱
SO WHAT YOU THINK ?
北京地铁站那么多，是怎么计算得如此之快呢？
本人思路：
（1）小明要从a点去c点，那么首先获取a点附近的换乘站：GetTheNearestTransferStation（a）、返回ArrayList<Station>定义为al；
同理再次获取c点附近的换乘站GetTheNearestTransferStation（c）；返回ArrayList<Station>定义为cl；
（2）经过上述步骤1我们得到了两个对象al和cl，然后通过获取最近两个车站GetTheNearestTwoStations（al，cl），返回ArrayList<Station>定义为sl；
（3）根据坐标系，东南西北，以及西南，东北，西北，东南等八个方位角进行图的遍历。
（3）得到最优的一条路线记为Lin1，然后再计算line1的各个属性值。
（4）显示在界面上。完毕！
设计图如下
Android apk logo图
运行环境：Android2.2+
java版本代码
数据的存储
/*
* Project Name:BeiJingS
* File Name:上面是数据的存储
* Package Name:
* Date:2012年11月2日下午2:05:31
* Copyright (c) 2017, xx@163.com xx Rights Reserved.
*
*/
package
cn.chenfei.WeidghtAD;
/*
*@author xx
*@version 1.0.0
*/
public
class
Data
{
public
Data()
{
//
//
TODO: Add constructor logic here
//
}
public
static java.util.Hashtable<String, double[]> LoadDC()
{
java.util.Hashtable<String, double[]> DCht = new java.util.Hashtable<String, double[]>();
DCht.put("复兴门", newdouble[] { 0, 0 });
DCht.put("车公庄庄", newdouble[] { 0, 1 });
DCht.put("西直门", newdouble[] { 0, 2 });
DCht.put("知春路", newdouble[] { 0, 3 });
DCht.put("西二旗", newdouble[] { 0, 4 });
DCht.put("南邵", newdouble[] { 0, 5 });
DCht.put("西单", newdouble[] { 1, 0 });
DCht.put("平安里", newdouble[] { 1, 1 });
DCht.put("鼓楼大街", newdouble[] { 2, 2 });
DCht.put("北土城", newdouble[] { 2, 3 });
DCht.put("霍营", newdouble[] { 2, 4 });
DCht.put("回龙观东大街", newdouble[] { 2, 5 });
DCht.put("天通苑北", newdouble[] { 3, 5 });
DCht.put("立水桥", newdouble[] { 3, 4 });
DCht.put("惠新西街南口", newdouble[] { 3, 3 });
DCht.put("雍和宫", newdouble[] { 3, 2 });
DCht.put("东四", newdouble[] { 3, 1 });
DCht.put("东单", newdouble[] { 3, 0 });
DCht.put("俸伯", newdouble[] { 4, 5 });
DCht.put("望京西", newdouble[] { 4, 4 });
DCht.put("芍药居", newdouble[] { 4, 3 });
DCht.put("东直门", newdouble[] { 4, 2 });
DCht.put("朝阳门", newdouble[] { 4, 1 });
DCht.put("建国门", newdouble[] { 4, 0 });
DCht.put("三元桥", newdouble[] { 5, 2 });
DCht.put("呼家楼", newdouble[] { 5, 1 });
DCht.put("草房", newdouble[] { 6, 1 });
DCht.put("国贸", newdouble[] { 5, 0 });
DCht.put("四惠惠", newdouble[] { 6, 0 });
DCht.put("四惠东", newdouble[] { 7, 0 });
DCht.put("土桥", newdouble[] { 7, -1 });
DCht.put("崇文门", newdouble[] { 3, -1 }); //1
DCht.put("磁器口", newdouble[] { 3, -1.2 }); //1
DCht.put("蒲黄榆", newdouble[] { 3, -1.4 }); //1
DCht.put("宋家庄", newdouble[] { 3, -2 });
DCht.put("次渠", newdouble[] { 3, -3 });
DCht.put("宣武门", newdouble[] { 0, -1 });
//DCht.Add("首经贸", new double[] { 0, -2 });
DCht.put("安河桥北", newdouble[] { -1, 4 });
DCht.put("海淀黄庄", newdouble[] { -1, 3 });
DCht.put("国家图书馆", newdouble[] { -1, 2 });
DCht.put("白石桥南", newdouble[] { -1, 1 });
DCht.put("六里桥", newdouble[] { -2, -1.2 }); //1
DCht.put("西局", newdouble[] { -2, -1.4 }); //1
DCht.put("郭公庄", newdouble[] { -3, -1.2 }); //1
DCht.put("苏庄", newdouble[] { -4, -1.2 }); //1
DCht.put("慈寿寺", newdouble[] { -2, 1 });
DCht.put("公主坟", newdouble[] { -2, 0 });
DCht.put("海淀五路居", newdouble[] { -3, 1 });
DCht.put("苹果园", newdouble[] { -3, 0 });
DCht.put("张郭庄", newdouble[] { -3, -1.4 }); //1
DCht.put("南锣鼓巷", newdouble[] { 2, 1 });
DCht.put("北京西站", newdouble[] { -1, -1.2 }); //1
DCht.put("菜市口", newdouble[] { 0, -1.2 }); //1
DCht.put("北京南站", newdouble[] { 0, -1.4 }); //1
DCht.put("角门西", newdouble[] { 0, -2 });
DCht.put("天宫院", newdouble[] { 0, -3 });
DCht.put("十里河", newdouble[] { 5, -1.4 }); //1
DCht.put("双井", newdouble[] { 5, -1.2 }); //1
DCht.put("大望路", newdouble[] { 5.2, 0 }); //1
DCht.put("雨台", newdouble[] { 5.2, 0 }); //1return DCht;
}
privatestaticvoid SWAP(java.util.HashSet<String[]> backlist, RefObject<String[]> arry, String b1, String b2, String len, String m)
{
arry.argvalue = new String[4];
arry.argvalue[0] = b1;
arry.argvalue[1] = b2;
arry.argvalue[2] = len;
arry.argvalue[3] = m;
backlist.add(arry.argvalue);
arry.argvalue = null;
arry.argvalue = new String[4];
arry.argvalue[0] = b2;
arry.argvalue[1] = b1;
arry.argvalue[2] = len;
arry.argvalue[3] = m;
backlist.add(arry.argvalue);
arry.argvalue = null;
}
publicstatic java.util.HashSet<String[]> LoadDD()
{
String[] arry = null;
java.util.HashSet<String[]> backlist = new java.util.HashSet<String[]>();
String b1 = "";
String b2 = "";
String len = "";
String timem = "";
//13号线开始
b1 = "西直门";
b2 = "知春路";
len = "4.1";
timem = "7";
RefObject<String[]> tempRef_arry = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry, b1, b2, len, timem);
arry = tempRef_arry.argvalue;
b1 = "西二旗";
b2 = "知春路";
len = "9.3";
timem = "15";
RefObject<String[]> tempRef_arry2 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry2, b1, b2, len, timem);
arry = tempRef_arry2.argvalue;
b1 = "霍营";
b2 = "西二旗";
len = "7.1";
timem = "10";
RefObject<String[]> tempRef_arry3 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry3, b1, b2, len, timem);
arry = tempRef_arry3.argvalue;
b1 = "霍营";
b2 = "立水桥";
len = "4.8";
timem = "10";
RefObject<String[]> tempRef_arry4 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry4, b1, b2, len, timem);
arry = tempRef_arry4.argvalue;
b1 = "望京西";
b2 = "立水桥";
len = "9.1";
timem = "20";
RefObject<String[]> tempRef_arry5 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry5, b1, b2, len, timem);
arry = tempRef_arry5.argvalue;
b1 = "望京西";
b2 = "芍药居";
len = "2";
timem = "10";
RefObject<String[]> tempRef_arry6 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry6, b1, b2, len, timem);
arry = tempRef_arry6.argvalue;
b1 = "东直门";
b2 = "芍药居";
len = "3.9";
timem = "10";
RefObject<String[]> tempRef_arry7 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry7, b1, b2, len, timem);
arry = tempRef_arry7.argvalue;
//13号线结束
//昌平线号线开始
b1 = "南邵";
b2 = "西二旗";
len = "21.2";
timem = "40";
RefObject<String[]> tempRef_arry8 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry8, b1, b2, len, timem);
arry = tempRef_arry8.argvalue;
//昌平线号线end
//8号线开始
b1 = "回龙观东大街";
b2 = "霍营";
len = "1.1";
timem = "5";
RefObject<String[]> tempRef_arry9 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry9, b1, b2, len, timem);
arry = tempRef_arry9.argvalue;
b1 = "北土城";
b2 = "霍营";
len = "13.2";
timem = "30";
RefObject<String[]> tempRef_arry10 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry10, b1, b2, len, timem);
arry = tempRef_arry10.argvalue;
b1 = "北土城";
b2 = "鼓楼大街";
len = "3.2";
timem = "10";
RefObject<String[]> tempRef_arry11 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry11, b1, b2, len, timem);
arry = tempRef_arry11.argvalue;
//8号线end
//5号线开始 8号线开始 13 昌平线
b1 = "天通苑北";
b2 = "立水桥";
len = "3.4";
timem = "10";
RefObject<String[]> tempRef_arry12 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry12, b1, b2, len, timem);
arry = tempRef_arry12.argvalue;
b1 = "惠新西街南口";
b2 = "立水桥";
len = "8.6";
timem = "20";
RefObject<String[]> tempRef_arry13 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry13, b1, b2, len, timem);
arry = tempRef_arry13.argvalue;
b1 = "惠新西街南口";
b2 = "雍和宫";
len = "3.3";
timem = "10";
RefObject<String[]> tempRef_arry14 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry14, b1, b2, len, timem);
arry = tempRef_arry14.argvalue;
b1 = "东四";
b2 = "雍和宫";
len = "2.7";
timem = "10";
RefObject<String[]> tempRef_arry15 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry15, b1, b2, len, timem);
arry = tempRef_arry15.argvalue;
b1 = "东四";
b2 = "东单";
len = "1.8";
timem = "10";
RefObject<String[]> tempRef_arry16 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry16, b1, b2, len, timem);
arry = tempRef_arry16.argvalue;
b1 = "崇文门";
b2 = "东单";
len = "0.887";
timem = "5";
RefObject<String[]> tempRef_arry17 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry17, b1, b2, len, timem);
arry = tempRef_arry17.argvalue;
b1 = "崇文门";
b2 = "磁器口";
len = "0.8";
timem = "2";
RefObject<String[]> tempRef_arry18 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry18, b1, b2, len, timem);
arry = tempRef_arry18.argvalue;
b1 = "磁器口";
b2 = "菜市口";
len = "3.6";
timem = "4";
RefObject<String[]> tempRef_arry19 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry19, b1, b2, len, timem);
arry = tempRef_arry19.argvalue;
b1 = "磁器口";
b2 = "双井";
len = "4.6";
timem = "3";
RefObject<String[]> tempRef_arry20 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry20, b1, b2, len, timem);
arry = tempRef_arry20.argvalue;
b1 = "磁器口";
b2 = "蒲黄榆";
len = "3.1";
timem = "6";
RefObject<String[]> tempRef_arry21 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry21, b1, b2, len, timem);
arry = tempRef_arry21.argvalue;
b1 = "北京南站";
b2 = "蒲黄榆";
len = "6.1";
timem = "5";
RefObject<String[]> tempRef_arry22 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry22, b1, b2, len, timem);
arry = tempRef_arry22.argvalue;
b1 = "宋家庄";
b2 = "蒲黄榆";
len = "2.7";
timem = "5";
RefObject<String[]> tempRef_arry23 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry23, b1, b2, len, timem);
arry = tempRef_arry23.argvalue;
//5号线end
//5号线 ,8号线, 13号线 ,昌平线 ,2
b1 = "西直门";
b2 = "鼓楼大街";
len = "3.7";
timem = "10";
RefObject<String[]> tempRef_arry24 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry24, b1, b2, len, timem);
arry = tempRef_arry24.argvalue;
b1 = "雍和宫";
b2 = "鼓楼大街";
len = "2";
timem = "4";
RefObject<String[]> tempRef_arry25 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry25, b1, b2, len, timem);
arry = tempRef_arry25.argvalue;
b1 = "雍和宫";
b2 = "东直门";
len = "2.3";
timem = "4";
RefObject<String[]> tempRef_arry26 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry26, b1, b2, len, timem);
arry = tempRef_arry26.argvalue;
b1 = "朝阳门";
b2 = "东直门";
len = "1.9";
timem = "4";
RefObject<String[]> tempRef_arry27 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry27, b1, b2, len, timem);
arry = tempRef_arry27.argvalue;
b1 = "朝阳门";
b2 = "建国门";
len = "2.5";
timem = "4";
RefObject<String[]> tempRef_arry28 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry28, b1, b2, len, timem);
arry = tempRef_arry28.argvalue;
b1 = "崇文门";
b2 = "建国门";
len = "2.8";
timem = "4";
RefObject<String[]> tempRef_arry29 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry29, b1, b2, len, timem);
arry = tempRef_arry29.argvalue;
b1 = "崇文门";
b2 = "宣武门";
len = "3.7";
timem = "7";
RefObject<String[]> tempRef_arry30 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry30, b1, b2, len, timem);
arry = tempRef_arry30.argvalue;
b1 = "复兴门";
b2 = "宣武门";
len = "2.2";
timem = "4";
RefObject<String[]> tempRef_arry31 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry31, b1, b2, len, timem);
arry = tempRef_arry31.argvalue;
b1 = "复兴门";
b2 = "车公庄庄";
len = "2.8";
timem = "5";
RefObject<String[]> tempRef_arry32 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry32, b1, b2, len, timem);
arry = tempRef_arry32.argvalue;
b1 = "西直门";
b2 = "车公庄庄";
len = "0.837";
timem = "2";
RefObject<String[]> tempRef_arry33 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry33, b1, b2, len, timem);
arry = tempRef_arry33.argvalue;
////5号线 ,8号线, 13号线 ,昌平线 ,2 : 2号线end////5号线 ,8号线, 13号线 ,昌平线 ,2 : 4号线begin
b1 = "安河桥北";
b2 = "海淀黄庄";
len = "7.4";
timem = "14";
RefObject<String[]> tempRef_arry34 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry34, b1, b2, len, timem);
arry = tempRef_arry34.argvalue;
b1 = "国家图书馆";
b2 = "海淀黄庄";
len = "3.7";
timem = "7";
RefObject<String[]> tempRef_arry35 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry35, b1, b2, len, timem);
arry = tempRef_arry35.argvalue;
b1 = "国家图书馆";
b2 = "西直门";
len = "3";
timem = "6";
RefObject<String[]> tempRef_arry36 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry36, b1, b2, len, timem);
arry = tempRef_arry36.argvalue;
b1 = "平安里";
b2 = "西直门";
len = "2.2";
timem = "5";
RefObject<String[]> tempRef_arry37 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry37, b1, b2, len, timem);
arry = tempRef_arry37.argvalue;
b1 = "平安里";
b2 = "西单";
len = "2.9";
timem = "5";
RefObject<String[]> tempRef_arry38 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry38, b1, b2, len, timem);
arry = tempRef_arry38.argvalue;
b1 = "宣武门";
b2 = "西单";
len = "0.828";
timem = "2";
RefObject<String[]> tempRef_arry39 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry39, b1, b2, len, timem);
arry = tempRef_arry39.argvalue;
b1 = "宣武门";
b2 = "菜市口";
len = "1.2";
timem = "4";
RefObject<String[]> tempRef_arry40 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry40, b1, b2, len, timem);
arry = tempRef_arry40.argvalue;
b1 = "北京南站";
b2 = "菜市口";
len = "2.8";
timem = "5";
RefObject<String[]> tempRef_arry41 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry41, b1, b2, len, timem);
arry = tempRef_arry41.argvalue;
b1 = "北京南站";
b2 = "角门西";
len = "2.5";
timem = "5";
RefObject<String[]> tempRef_arry42 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry42, b1, b2, len, timem);
arry = tempRef_arry42.argvalue;
b1 = "天宫院";
b2 = "角门西";
len = "22.9";
timem = "38";
RefObject<String[]> tempRef_arry43 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry43, b1, b2, len, timem);
arry = tempRef_arry43.argvalue;
////5号线 ,8号线, 13号线 ,昌平线 ,2 ,4 : 4号线end////5号线 ,8号线, 13号线 ,昌平线 ,2 ,4, : 10号线begin
b1 = "西局";
b2 = "六里桥";
len = "1.6";
timem = "3";
RefObject<String[]> tempRef_arry44 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry44, b1, b2, len, timem);
arry = tempRef_arry44.argvalue;
b1 = "公主坟";
b2 = "六里桥";
len = "3.4";
timem = "6";
RefObject<String[]> tempRef_arry45 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry45, b1, b2, len, timem);
arry = tempRef_arry45.argvalue;
b1 = "公主坟";
b2 = "慈寿寺";
len = "3.4";
timem = "6";
RefObject<String[]> tempRef_arry46 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry46, b1, b2, len, timem);
arry = tempRef_arry46.argvalue;
b1 = "海淀黄庄";
b2 = "慈寿寺";
len = "7.3";
timem = "14";
RefObject<String[]> tempRef_arry47 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry47, b1, b2, len, timem);
arry = tempRef_arry47.argvalue;
b1 = "海淀黄庄";
b2 = "知春路";
len = "2.1";
timem = "4";
RefObject<String[]> tempRef_arry48 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry48, b1, b2, len, timem);
arry = tempRef_arry48.argvalue;
b1 = "北土城";
b2 = "知春路";
len = "4.4";
timem = "9";
RefObject<String[]> tempRef_arry49 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry49, b1, b2, len, timem);
arry = tempRef_arry49.argvalue;
b1 = "北土城";
b2 = "惠新西街南口";
len = "2";
timem = "4";
RefObject<String[]> tempRef_arry50 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry50, b1, b2, len, timem);
arry = tempRef_arry50.argvalue;
b1 = "芍药居";
b2 = "惠新西街南口";
len = "1.7";
timem = "3";
RefObject<String[]> tempRef_arry51 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry51, b1, b2, len, timem);
arry = tempRef_arry51.argvalue;
b1 = "芍药居";
b2 = "三元桥";
len = "2.7";
timem = "5";
RefObject<String[]> tempRef_arry52 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry52, b1, b2, len, timem);
arry = tempRef_arry52.argvalue;
b1 = "呼家楼";
b2 = "三元桥";
len = "4.4";
timem = "9";
RefObject<String[]> tempRef_arry53 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry53, b1, b2, len, timem);
arry = tempRef_arry53.argvalue;
b1 = "呼家楼";
b2 = "国贸";
len = "1.6";
timem = "4";
RefObject<String[]> tempRef_arry54 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry54, b1, b2, len, timem);
arry = tempRef_arry54.argvalue;
b1 = "宋家庄";
b2 = "十里河";
len = "4.2";
timem = "8";
RefObject<String[]> tempRef_arry55 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry55, b1, b2, len, timem);
arry = tempRef_arry55.argvalue;
b1 = "蒲黄榆";
b2 = "十里河";
len = "2.3";
timem = "3";
RefObject<String[]> tempRef_arry56 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry56, b1, b2, len, timem);
arry = tempRef_arry56.argvalue;
b1 = "宋家庄";
b2 = "角门西";
len = "4.9";
timem = "9";
RefObject<String[]> tempRef_arry57 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry57, b1, b2, len, timem);
arry = tempRef_arry57.argvalue;
b1 = "西局";
b2 = "角门西";
len = "7.9";
timem = "14";
RefObject<String[]> tempRef_arry58 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry58, b1, b2, len, timem);
arry = tempRef_arry58.argvalue;
////5号线 ,8号线, 13号线 ,昌平线 ,2 ,4, : 10号线end////昌平线,1,2,4,5,8,10,13, :1号线开始
b1 = "苹果园";
b2 = "公主坟";
len = "12.7";
timem = "22";
RefObject<String[]> tempRef_arry59 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry59, b1, b2, len, timem);
arry = tempRef_arry59.argvalue;
b1 = "复兴门";
b2 = "公主坟";
len = "4";
timem = "8";
RefObject<String[]> tempRef_arry60 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry60, b1, b2, len, timem);
arry = tempRef_arry60.argvalue;
b1 = "复兴门";
b2 = "西单";
len = "1.7";
timem = "3";
RefObject<String[]> tempRef_arry61 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry61, b1, b2, len, timem);
arry = tempRef_arry61.argvalue;
b1 = "东单";
b2 = "西单";
len = "3.6";
timem = "8";
RefObject<String[]> tempRef_arry62 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry62, b1, b2, len, timem);
arry = tempRef_arry62.argvalue;
b1 = "东单";
b2 = "建国门";
len = "2.3";
timem = "3";
RefObject<String[]> tempRef_arry63 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry63, b1, b2, len, timem);
arry = tempRef_arry63.argvalue;
b1 = "国贸";
b2 = "建国门";
len = "2.8";
timem = "4";
RefObject<String[]> tempRef_arry64 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry64, b1, b2, len, timem);
arry = tempRef_arry64.argvalue;
b1 = "国贸";
b2 = "大望路";
len = "1.4";
timem = "3";
RefObject<String[]> tempRef_arry65 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry65, b1, b2, len, timem);
arry = tempRef_arry65.argvalue;
b1 = "国贸";
b2 = "双井";
len = "1.7";
timem = "3";
RefObject<String[]> tempRef_arry66 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry66, b1, b2, len, timem);
arry = tempRef_arry66.argvalue;
b1 = "十里河";
b2 = "双井";
len = "3.1";
timem = "6";
RefObject<String[]> tempRef_arry67 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry67, b1, b2, len, timem);
arry = tempRef_arry67.argvalue;
b1 = "大望路";
b2 = "四惠惠";
len = "1.6";
timem = "3";
RefObject<String[]> tempRef_arry68 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry68, b1, b2, len, timem);
arry = tempRef_arry68.argvalue;
b1 = "四惠东";
b2 = "四惠惠";
len = "1.7";
timem = "3";
RefObject<String[]> tempRef_arry69 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry69, b1, b2, len, timem);
arry = tempRef_arry69.argvalue;
////昌平线,1,2,4,5,8,10,13, :1号线end////昌平线,1,2,4,5,6,8,10,13, :6号线begin
b1 = "海淀五路居";
b2 = "慈寿寺";
len = "1.5";
timem = "3";
RefObject<String[]> tempRef_arry70 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry70, b1, b2, len, timem);
arry = tempRef_arry70.argvalue;
b1 = "白石桥南";
b2 = "慈寿寺";
len = "2.7";
timem = "5";
RefObject<String[]> tempRef_arry71 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry71, b1, b2, len, timem);
arry = tempRef_arry71.argvalue;
b1 = "白石桥南";
b2 = "车公庄庄";
len = "2.5";
timem = "5";
RefObject<String[]> tempRef_arry72 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry72, b1, b2, len, timem);
arry = tempRef_arry72.argvalue;
b1 = "平安里";
b2 = "车公庄庄";
len = "1.5";
timem = "3";
RefObject<String[]> tempRef_arry73 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry73, b1, b2, len, timem);
arry = tempRef_arry73.argvalue;
b1 = "平安里";
b2 = "南锣鼓巷";
len = "2.7";
timem = "5";
RefObject<String[]> tempRef_arry74 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry74, b1, b2, len, timem);
arry = tempRef_arry74.argvalue;
b1 = "东四";
b2 = "南锣鼓巷";
len = "1.9";
timem = "4";
RefObject<String[]> tempRef_arry75 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry75, b1, b2, len, timem);
arry = tempRef_arry75.argvalue;
b1 = "朝阳门";
b2 = "东四";
len = "2.6";
timem = "3";
RefObject<String[]> tempRef_arry76 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry76, b1, b2, len, timem);
arry = tempRef_arry76.argvalue;
b1 = "朝阳门";
b2 = "呼家楼";
len = "2.3";
timem = "5";
RefObject<String[]> tempRef_arry77 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry77, b1, b2, len, timem);
arry = tempRef_arry77.argvalue;
b1 = "草房";
b2 = "呼家楼";
len = "13.2";
timem = "22";
RefObject<String[]> tempRef_arry78 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry78, b1, b2, len, timem);
arry = tempRef_arry78.argvalue;
////昌平线,1,2,4,5,6,8,10,13, :6号线end////"昌平线","1","2","4","5","6","8","9","10","13", 9 begin
b1 = "国家图书馆";
b2 = "白石桥南";
len = "1.1";
timem = "3";
RefObject<String[]> tempRef_arry79 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry79, b1, b2, len, timem);
arry = tempRef_arry79.argvalue;
b1 = "北京西站";
b2 = "白石桥南";
len = "4.4";
timem = "9";
RefObject<String[]> tempRef_arry80 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry80, b1, b2, len, timem);
arry = tempRef_arry80.argvalue;
b1 = "六里桥";
b2 = "郭公庄";
len = "7.7";
timem = "14";
RefObject<String[]> tempRef_arry81 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry81, b1, b2, len, timem);
arry = tempRef_arry81.argvalue;
////"昌平线","1","2","4","5","6","8","9","10","13", 9 end////"昌平线","房山线","1","2","4","5","6","8","9","10","13", 房山线 begin
b1 = "苏庄";
b2 = "郭公庄";
len = "23.1";
timem = "38";
RefObject<String[]> tempRef_arry82 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry82, b1, b2, len, timem);
arry = tempRef_arry82.argvalue;
////"昌平线","房山线","1","2","4","5","6","8","9","10","13", 房山线end////"昌平线","房山线","1","2","4","5","6","8","9","10","13" "15", 15 begin
b1 = "望京西";
b2 = "俸伯";
len = "30.4";
timem = "48";
RefObject<String[]> tempRef_arry83 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry83, b1, b2, len, timem);
arry = tempRef_arry83.argvalue;
////"昌平线","房山线","1","2","4","5","6","8","9","10","13","15", 15end////"昌平线","房山线","1","2","4","5","6","8","9","10","13" "15","亦庄线" 亦庄线 begin
b1 = "宋家庄";
b2 = "次渠";
len = "21.7";
timem = "37";
RefObject<String[]> tempRef_arry84 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry84, b1, b2, len, timem);
arry = tempRef_arry84.argvalue;
////"昌平线","房山线","1","2","4","5","6","8","9","10","13","15","亦庄线" 亦庄线end////"昌平线","房山线","1","2","4","5","6","8","9","10","13" "15","亦庄线" ,"八通线" 八通线 begin
b1 = "四惠东";
b2 = "土桥";
len = "16.6";
timem = "29";
RefObject<String[]> tempRef_arry85 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry85, b1, b2, len, timem);
arry = tempRef_arry85.argvalue;
////"昌平线","房山线","1","2","4","5","6","8","9","10","13" "15","亦庄线" ,"八通线" 八通线 end////"昌平线","房山线","1","2","4","5","6","8","9","10","13" "15","亦庄线" ,"八通线" 14 begin
b1 = "西局";
b2 = "张郭庄";
len = "11";
timem = "18";
RefObject<String[]> tempRef_arry86 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry86, b1, b2, len, timem);
arry = tempRef_arry86.argvalue;
////"昌平线","房山线","1","2","4","5","6","8","9","10","13" "15","亦庄线" ,"八通线" 14 end
b1 = "西局";
b2 = "北京南站";
len = "7";
timem = "10";
RefObject<String[]> tempRef_arry87 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry87, b1, b2, len, timem);
arry = tempRef_arry87.argvalue;
b1 = "鼓楼大街";
b2 = "南锣鼓巷";
len = "2.5";
timem = "9";
RefObject<String[]> tempRef_arry88 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry88, b1, b2, len, timem);
arry = tempRef_arry88.argvalue;
b1 = "北京西站";
b2 = "六里桥";
len = "2.6";
timem = "5";
RefObject<String[]> tempRef_arry89 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry89, b1, b2, len, timem);
arry = tempRef_arry89.argvalue;
b1 = "北京西站";
b2 = "菜市口";
len = "5";
timem = "7";
RefObject<String[]> tempRef_arry90 = new RefObject<String[]>(arry);
SWAP(backlist, tempRef_arry90, b1, b2, len, timem);
arry = tempRef_arry90.argvalue;
return backlist;
}
}
接着是AllLines、连接线的属性关系。
/*
* Project Name:BeiJingS
* File Name:
* Package Name:
* Date:2012年11月2日下午2:05:31
* Copyright (c) 2017, xx@163.com xx Rights Reserved.
*
*/
package
cn.chenfei.WeidghtAD;
/*
*@author xx
*@version 1.0.0
*/
public
class
AllLines
{
public
AllLines()
{
}
public
static java.util.HashSet<String> GetPreOrNextNode(String stationname)
{
java.util.ArrayList<String[]> liststr = new java.util.ArrayList<String[]>();
java.util.ArrayList<int[]> listint = new java.util.ArrayList<int[]>();
String[] Lin1 = { "苹果园", "古城", "八角游乐园", "八宝山", "玉泉路", "五棵松", "万寿路", "公主坟", "军事博物馆", "木樨地", "南礼士路", "复兴门", "西单", "天安门西", "天安门东", "王府井", "东单", "建国门", "永安里", "国贸", "大望路", "四惠", "四惠东" };
int[] Lin1isnode = { 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 10, 1, 1 };
liststr.add(Lin1);
listint.add(Lin1isnode);
String[] Lin2 = { "车公庄", "阜成门", "复兴门", "长椿街", "宣武门", "和平门", "前门", "崇文门", "北京站", "建国门", "朝阳门", "东四十条", "东直门", "雍和宫", "安定门", "鼓楼大街", "积水潭", "西直门" };
int[] Lin2isnode = { 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1 };
liststr.add(Lin2);
listint.add(Lin2isnode);
String[] Line4 = { "安河桥北", "北宫门", "西苑", "圆明园", "北京大学东门", "中关村", "海淀黄庄", "人民大学", "魏公村", "国家图书馆", "动物园", "西直门", "新街口", "平安里", "西四", "灵境胡同", "西单", "宣武门", "菜市口", "陶然亭", "北京南站", "马家堡", "角门西", "公益西桥", "新宫", "西红门", "高米店北", "高米店南", "枣园", "清源路", "黄村西大街", "黄村火车站", "义和庄", "生物医药基地", "天宫院" };
int[] Line4node = { 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 };
liststr.add(Line4);
listint.add(Line4node);
//checked line nodes begin
String[] Line5 = { "宋家庄", "刘家窑", "蒲黄榆", "天坛东门", "磁器口", "崇文门", "东单", "灯市口", "东四", "张自忠路", "北新桥", "雍和宫", "和平里北街", "和平西桥", "惠新西街南口", "惠新西街北口", "大屯路东", "北苑路北", "立水桥南", "立水桥", "天通苑南", "天通苑", "天通苑北" };
int[] Line5node = { 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1 };
liststr.add(Line5);
listint.add(Line5node);
String[] Line6 = { "海淀五路居", "慈寿寺", "花园桥", "白石桥南", "车公庄西", "车公庄", "平安里", "北海北", "南锣鼓巷", "东四", "朝阳门", "东大桥", "呼家楼", "金台路", "十里堡", "青年路", "褡裢坡", "黄渠", "常营", "草房" };
int[] Line6node = { 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1 };
liststr.add(Line6);
listint.add(Line6node);
String[] Line8 = { "鼓楼大街", "安华桥", "北土城", "奥体中心", "奥林匹克公园", "森林公园南门", "林萃桥", "永泰庄", "西小口", "育新", "霍营", "回龙观东大街" };
int[] Line8node = { 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1 };
liststr.add(Line8);
listint.add(Line8node);
String[] Line9 = { "郭公庄", "丰台科技园", "科怡路", "丰台南路", "丰台东大街", "七里庄", "六里桥", "六里桥东", "北京西站", "白堆子", "白石桥南", "国家图书馆" };
int[] Line9node = { 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1 };
liststr.add(Line9);
listint.add(Line9node);
String[] Line10 = { "慈寿寺", "车道沟", "长春桥", "火器营", "巴沟", "苏州街", "海淀黄庄", "知春里", "知春路", "西土城", "牡丹园", "健德门", "北土城", "安贞门", "惠新西街南口", "芍药居", "太阳宫", "三元桥", "亮马桥", "农业展览馆", "团结湖", "呼家楼", "金台夕照", "国贸", "双井", "劲松", "潘家园", "十里河", "分钟寺", "成寿寺", "宋家庄", "石榴庄", "大红门", "角门东", "角门西", "草桥", "纪家庙", "首经贸", "丰台站", "泥洼", "西局", "六里桥", "莲花桥", "公主坟", "西钓鱼台" };
int[] Linen10node = { 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1 };
liststr.add(Line10);
listint.add(Linen10node);
String[] Line13 = { "东直门", "柳芳", "光熙门", "芍药居", "望京西", "北苑", "立水桥", "霍营", "回龙观", "龙泽", "西二旗", "上地", "五道口", "知春路", "大钟寺", "西直门" };
int[] Line13node = { 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1 };
liststr.add(Line13);
listint.add(Line13node);
String[] Line14 = { "西局", "大井", "郭庄子", "大瓦窑", "园博园", "张郭庄" };
int[] Line14node = { 1, 0, 0, 0, 0, 1 };
liststr.add(Line14);
listint.add(Line14node);
String[] Line15 = { "俸伯", "顺义", "石门", "南法信", "后沙峪", "花梨坎", "国展", "孙河", "马泉营", "崔各庄", "望京", "望京西" };
int[] Line15node = { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 };
liststr.add(Line15);
listint.add(Line15node);
String[] Linebt = { "土桥", "临河里", "梨园", "九棵树", "果园", "通州北苑", "八里桥", "管庄", "双桥", "传媒大学", "高碑店", "四惠东", "四惠" };
int[] Linebtnode = { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1 };
liststr.add(Linebt);
listint.add(Linebtnode);
String[] Linecp = { "西二旗", "生命科学园", "朱辛庄", "巩华城", "沙河", "沙河高教园", "南邵" };
int[] Linecpnode = { 1, 0, 0, 0, 0, 0, 1 };
liststr.add(Linecp);
listint.add(Linecpnode);
String[] Lineyz = { "宋家庄", "肖村", "小红门", "旧宫", "亦庄桥", "亦庄文化园", "万源街", "荣京东街", "荣昌东街", "同济南路", "经海路", "次渠南", "次渠" };
int[] Linezynode = { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 };
liststr.add(Lineyz);
listint.add(Linezynode);
String[] Linefs = { "苏庄", "良乡南关", "良乡大学城西", "良乡大学城", "良乡大学城北", "广阳城", "篱笆房", "长阳", "稻田", "大葆台", "郭公庄" };
int[] Linefsnode = { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 };
liststr.add(Linefs);
listint.add(Linefsnode);
String[] tempstr = null;
int b = -1;
int a = -1;
int isend = 0;
java.util.HashSet<String> hs = null;
for (int x = 0; x < liststr.size(); x++)
{
if (isend == 1)
{
break;
}
tempstr = liststr.get(x);
hs = new java.util.HashSet<String>();
//新增for (String s : tempstr) {
if(!hs.contains(s))
hs.add(s);
}
/**
* O(1)
*/if (hs.contains(stationname) == true)
{
hs = null;
for (int y = 0; y < tempstr.length; y++)
{
if (stationname.equals(tempstr[y]))
{
a = x;
b = y; //find out the index values
isend = 1;
break;
}
}
}
else
{
hs = null;
continue;
}
tempstr = null;
}
int[] tint = listint.get(a);
int pre = b;
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;
}
java.util.HashSet<String> hr = new java.util.HashSet<String>();
hr.add(liststr.get(a)[pre]);
hr.add(liststr.get(a)[next]);
return hr;
}
}
再则是换乘的算法dal类代码
/*
* Project Name:BeiJingS
* File Name:
* Package Name:
* Date:2012年11月2日下午2:05:31
* Copyright (c) 2017, xx@163.com xx Rights Reserved.
*
*/
package
cn.chenfei.WeidghtAD;
/*
*@author xx
*@version 1.0.0
*/
public
class
DAL {
private java.util.HashSet<String[]> maindata = null;
private java.util.Hashtable<String, double[]> DCht = null; //换乘站privateint isend = 1;
private java.util.HashSet<String> fresult = new java.util.HashSet<String>(); //查找符合的路线private java.util.Hashtable<String, String> mainht = new java.util.Hashtable<String, String>(); //换乘站集合A-B,A-Cprivate String begin = "";
private String end = "";
private String temp = "";
private String beginpre = "";
private String endnext = "";
private String toto = "";
public String Search(String b,String e)
{
begin=b;
end=e;
toto = begin + ">" + end + ":";
DCht = Data.LoadDC(); ///加载换乘站坐标if (DCht.containsKey(RepsIN(begin)) == false || DCht.containsKey(RepsIN(end)) == false)
{
//获取开始点和结束点的最近的两个换乘站
java.util.HashSet<String> beginhs = null;//begin node obj
java.util.HashSet<String> endsshs = null;//end node objif (DCht.containsKey(RepsIN(begin)) == false)
{
beginpre = begin + "-";
beginhs = AllLines.GetPreOrNextNode(begin);
}
if (DCht.containsKey(RepsIN(end)) == false)
{
endnext = "-" + end;
endsshs = AllLines.GetPreOrNextNode(end);
}
//开始节点就是换乘站if (beginhs == null)
{
beginhs = new java.util.HashSet<String>();
beginhs.add(begin);
}
//结束点就是换乘节点if (endsshs == null)
{
endsshs = new java.util.HashSet<String>();
endsshs.add(end);
}
java.util.ArrayList<String> be = GetShortestPath(beginhs, endsshs);
beginhs = null;
endsshs = null;
//不需要换乘if (be == null)
{
toto=toto+begin + endnext;
return toto;
}
begin = be.get(0);//获取开始节点至结束点最近的起始节点
end = be.get(1);//获取距离最近的结束点的结束点
//相遇if (be.get(0).equals(be.get(1)))
{
toto=toto+beginpre + begin + endnext;
return toto;
}
}
//RefObject<String> tempRef_begin = new RefObject<String>(begin);
// RefObject<String> tempRef_end = new RefObject<String>(end);
String resultendString= SearchWrite(begin, end);
return resultendString;
}
//获取两点之间最短距离private java.util.ArrayList<String> GetShortestPath(java.util.HashSet<String> begin, java.util.HashSet<String> end)
{
/*
for(String s : begin)
System.out.println("xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx"+s);
for(String s : end)
System.out.println("yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy"+s);
*/int recount = 0;
java.util.ArrayList<String> rehs = null;//返回最近的坐标double tem = 0;
double min = -1;
double[] bd = null;
double[] ed = null;
for (String a : begin)//遍历开始节点附近最近的换乘节点 {
bd = DCht.get(RepsIN(a));//获取该坐标for (String b : end)//遍历结束节点附近最近的换乘节点 {
if (a.equals(b))
{
recount += 1;
}
ed = DCht.get(RepsIN(b));
tem = Math.pow((bd[0] - ed[0]), 2) + Math.pow((bd[1] - ed[1]), 2);
if (min == -1)
{
min = tem;
rehs = new java.util.ArrayList<String>();
rehs.add(a);
rehs.add(b);
}
elseif (min > tem)
{
min = tem;
rehs = new java.util.ArrayList<String>();
rehs.add(a);
rehs.add(b);
}
}
}
if (recount == 2)
{
returnnull;//未找到 }
return rehs;
}
private String SearchWrite(String begin, String end)
{
begin = RepsIN(begin);
end = RepsIN(end);
LoadData(begin, end);
java.util.HashSet<String> beginlist = new java.util.HashSet<String>();
beginlist.add(begin);
GetF(beginlist);
toto=toto+"最短换乘路线为:" + GetMinQuk(fresult);
return RepsOUT(toto);
}
private String RepsOUT(String s)
{
if (s.contains("沙河高教园"))
{
return s.replace("车公庄庄", "车公庄").replace("四惠惠", "四惠");
}
return s.replace("车公庄庄", "车公庄").replace("高教园", "沙河高教园").replace("四惠惠", "四惠");
}
private String RepsIN(String s)
{
if (s.equals("四惠东"))
{
return s;
}
if (s.equals("车公庄庄"))
{
return s;
}
return s.replace("车公庄", "车公庄庄").replace("沙河高教园", "高教园").replace("四惠", "四惠惠");
}
private String GetMinQuk(java.util.HashSet<String> nage)
{
String resultsrt = "";
String[] nagearry = null;
java.text.DecimalFormat df=new java.text.DecimalFormat("#.##");
double val, minval = Integer.MAX_VALUE;
for (String s : nage)
{
nagearry = s.split("[-]", -1); //s个数组
val = GetVal(nagearry);
if (val < minval)
{
minval = val;
resultsrt = beginpre + s + endnext +"-"+ df.format(val);
}
nagearry = null;
}
return resultsrt;
}
privatedouble GetVal(String[] findarry)
{
double val = 0;
for (int ss = 0; ss < findarry.length - 1; ss = ss + 1)
{
for (String[] aa : maindata)
{
if (findarry[ss].equals(aa[0]) && findarry[ss + 1].equals(aa[1]))
{
val += Double.parseDouble(aa[2]);
break;
}
}
}
return val;
}
privateboolean isadd = false;
private java.util.HashSet<String> returnlist = null;
private String[] earry = null;
privatedouble[] bxy = null;
privatedouble[] exy = null;
private String temgstr = "";
/**
* 时间复杂度比较复杂，因为换乘结点的关系导致的
最坏情况下(每个站之间都有连线，但是地铁线路图实际上是不存在次情况的):O(2^n)
相反
最优情况下(之间只有唯一的连接点,次情况下也不是很现实的，有的地铁换乘是多个换乘点都在同一条线上的)
此时用hashtable所以是:O(1)
*/private java.util.HashSet<String> GetF(java.util.HashSet<String> beginlist)
{
if (mainht == null || mainht.isEmpty())
{
returnnull;
}
returnlist = new java.util.HashSet<String>();
if (beginlist.isEmpty())
{
isend = 1;
}
else
{
for (String f : beginlist) ///O(n) {
if (f.indexOf(end) > -1) //线路包含目的地e {
temp = f.substring(0, f.lastIndexOf(end) + end.length());
if (fresult.contains(temp) == false) ///O(1) {
fresult.add(temp);
}
}
elseif (endchxy.indexOf(‘-‘) > -1) //线路不包含目的地 并且目的地有连接结点 {
temp = f.substring(f.lastIndexOf(‘-‘) + 1);
if (temp.equals(endchxy.substring(0, endchxy.indexOf(‘-‘))))
{
temp = f + endchxy.substring(endchxy.indexOf(‘-‘));
if (fresult.contains(temp) == false) ///O(1) {
fresult.add(temp);
}
}
}
}
/**O(n)
*/for (String strbegin : beginlist)
{
if (strbegin.indexOf("-") == -1 && mainht.containsKey(strbegin) == true) //have this key and first load data {
bxy = DCht.get(strbegin);
earry = mainht.get(strbegin).toString().split("[,]", -1);
for (String ar : earry)
{
exy = DCht.get(ar);
isadd = CK(isadd, bxy, exy);
if (isadd == true)
{
returnlist.add(strbegin + "-" + ar);
isend = 0;
}
}
}
elseif (strbegin.indexOf("-") > -1 && mainht.containsKey(strbegin.substring(strbegin.lastIndexOf("-") + 1)) == true)
{
temgstr = strbegin.substring(strbegin.lastIndexOf("-") + 1);
bxy = DCht.get(temgstr);
earry = mainht.get(temgstr).toString().split("[,]", -1); //exchange nodefor (String ar : earry)
{
exy = DCht.get(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);
}
else
{
returnnull;
}
}
//East South West North Northeast Northwest Southeast Southwestprivateboolean CK(boolean 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;
}
elseif (dx >= 0 && dy <= 0 && exy[0] >= bxy[0] && exy[1] <= bxy[1] && exy[0] <= ex && exy[1] >= ey) //2 x增大y减小 {
isadd = true;
}
elseif (dx <= 0 && dy >= 0 && exy[0] <= bxy[0] && exy[1] >= bxy[1] && exy[0] >= ex && exy[1] <= ey) //3 x减小y增大 {
isadd = true;
}
elseif (dx <= 0 && dy <= 0 && exy[0] <= bxy[0] && exy[1] <= bxy[1] && exy[0] >= ex && exy[1] >= ey) //4 x减小y减小 {
isadd = true;
}
elseif (dx >= 0 && dy == 0 && exy[0] >= bxy[0] && exy[1] == bxy[1] && exy[1] == ey && exy[0] <= ex) //5 x增大y不变 {
isadd = true;
}
elseif (dx == 0 && dy >= 0 && exy[0] == bxy[0] && exy[1] >= bxy[1] && exy[0] == ex && exy[1] <= ey) //6 x不变y增大 {
isadd = true;
}
elseif (dx <= 0 && dy == 0 && exy[0] <= bxy[0] && exy[1] == bxy[1] && exy[1] == by && exy[0] >= ex) //7 x减小y不变 {
isadd = true;
}
elseif (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;
}
privatedouble bx, by, ex, ey;
privatedouble dx, dy;
private String endchxy;
privateint ChxyE(String stationname)
{
endchxy = stationname;
String[] arr = null;
double[] xy = null;
if (stationname.indexOf("-") == -1)
{
arr = mainht.get(stationname).toString().split("[,]", -1);
xy = DCht.get(stationname); //获取坐标
ex = xy[0];
ey = xy[1];
}
else
{
arr = mainht.get(stationname.substring(0, stationname.indexOf("-"))).toString().split("[,]", -1);
xy = DCht.get(stationname.substring(0, stationname.indexOf("-"))); //获取坐标 }
java.util.ArrayList<String> lis = new java.util.ArrayList<String>();
for (int s = 0; s < arr.length; s++)
{
if (!stationname.contains(arr[s]))
{
lis.add(arr[s]);
}
}
if (lis.size() == 1)
{
xy = DCht.get(arr[0]); //获取坐标
ex = xy[0];
ey = xy[1];
xy = null;
stationname = arr[0] + "-" + stationname;
return ChxyE(stationname);
}
else
{
xy = null;
return -1;
}
}
privateint ChxyB(String stationname)
{
String[] arr = null;
double[] xy = null;
if (stationname.indexOf("-") == -1)
{
arr = mainht.get(stationname).toString().split("[,]", -1);
xy = DCht.get(stationname); //获取坐标 }
else
{
arr = mainht.get(stationname.substring(stationname.lastIndexOf("-") + 1)).toString().split("[,]", -1);
xy = DCht.get(stationname.substring(stationname.lastIndexOf("-") + 1)); //获取坐标 }
bx = xy[0];
by = xy[1];
for (int s = 0; s < arr.length; s++)
{
if (stationname.equals(arr[s]))
{
arr[s] = null;
}
}
if (arr.length == 1)
{
xy = DCht.get(arr[0]); //获取坐标
bx = xy[0];
by = xy[1];
xy = null;
stationname = stationname + "-" + arr[0];
return ChxyB(stationname);
}
else
{
xy = null;
return -1;
}
}
privatevoid LoadData(String beginp, String endp)
{
maindata = Data.LoadDD(); ///加载换乘结点之间的关系数据
//O(n^2)for (String[] sa : maindata)
{
if (mainht.containsKey(sa[0])) //含有此键值 {
continue;
}
for (String[] sd : maindata)
{
if (sa[0].equals(sd[0]))
{
if (mainht.containsKey(sa[0])) //含有此键值 {
mainht.put(sa[0], mainht.get(sa[0]) + "," + sd[1]);
}
else//新增 {
mainht.put(sa[0], sd[1]);
}
}
}
}
ChxyB(beginp); //处理开始点
ChxyE(endp); //处理结束点
dx = ex - bx; //目的坐标-起始坐标
dy = ey - by; //目的坐标-起始坐标 }
}
还有就是RefObject<T>
/*
* Project Name:BeiJingS
* File Name:
* Package Name:
* Date:2012年11月2日下午2:05:31
* Copyright (c) 2017, xx@163.com xx Rights Reserved.
*
*/
package
cn.chenfei.WeidghtAD;
/*
*@author xx
*@version 1.0.0
*/
//
----------------------------------------------------------------------------------------
//
Copyright ? 2006 - 2010 Tangible Software Solutions Inc.
//
This class can be used by anyone provided that the copyright notice remains intact.
//
//
This class is used to simulate the ability to pass arguments by reference in Java.
//
----------------------------------------------------------------------------------------
public
final
class RefObject<T>
{
public T argvalue;
public RefObject(T refarg)
{
argvalue = refarg;
}
}
最后是activity的class代码
/*
* Project Name:BeiJingS
* File Name:
* Package Name:
* Date:2012年11月2日下午2:05:31
* Copyright (c) 2017, xx@163.com xx Rights Reserved.
*
*/
package
cn.chenfei.WeidghtAD;
import
android.app.Activity;
import
android.os.Bundle;
import
android.view.View;
import
android.view.View.OnClickListener;
import
android.view.Window;
import
android.view.WindowManager;
import
android.widget.Button;
import
android.widget.EditText;
import
android.widget.ListView;
import
android.widget.Toast;
import
android.widget.ArrayAdapter;
import
java.util.ArrayList;
/*
*@author xx
*@version 1.0.0
*/
public
class WeidghtADActivity extends Activity {
private EditText b, e;
private Button btn1,btn2;
private ListView listv;
private ArrayList<String> arrayList=new ArrayList<String>();
/** Called when the activity is first created. */
@Override
publicvoid onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
//全屏 代码必须加在onCreate和setContentView之间this.requestWindowFeature(Window.FEATURE_NO_TITLE);
this.getWindow().setFlags(WindowManager.LayoutParams.FLAG_FULLSCREEN,
WindowManager.LayoutParams.FLAG_FULLSCREEN);
setContentView(R.layout.main);
b=(EditText)this.findViewById(R.id.txtb);
e=(EditText)this.findViewById(R.id.txte);
btn1=(Button)this.findViewById(R.id.btn1);
btn2=(Button)this.findViewById(R.id.btn2);
listv= (ListView)findViewById(R.id.MyListView);
btn2.setOnClickListener(new OnClickListener() {
@Override
publicvoid onClick(View v) {
System.exit(0);
}
});
btn1.setOnClickListener(new OnClickListener() {
@Override
publicvoid onClick(View v) {
String beginString = b.getText().toString();
String endString = e.getText().toString();
if (beginString.equals("")) {
MSG("请输入起点!");
return;
} elseif (endString.equals("")) {
MSG("请输入终点!");
return;
}
elseif(beginString.equals(endString)){
MSG("请不要输入相同的起始点!");
return;
}
elseif(beginString.equals("北京大学东门")&&endString.equals("立水桥"))
{
beginString = e.getText().toString();
endString = b.getText().toString();
}
try
{
DAL dal = new DAL();
String resultString = dal.Search(beginString, endString);
dal=null;
Opreatestring(resultString);
}
catch (Exception e) {
// TODO: handle exception
MSG("未查询到符合条件的路线!");
}
}
});
}
// 显示消息privatevoid MSG(String msg) {
Toast.makeText(WeidghtADActivity.this, msg, Toast.LENGTH_SHORT).show();
}
//处理返回来的字符串privatevoid Opreatestring(String s)
{
if(s.length()<1)
return;
s=s+"-AAA";//不然会少一个数据
String sa=s.substring(s.lastIndexOf(":")+1).trim();
String[] array= sa.split("[-]", -1);
arrayList.clear();
int i=1;
for(String temps :array)
{
if(!temps.trim().equals("AAA"))
{
arrayList.add(temps.trim());
}
i++;
}
ArrayList<String> arrayList2=new ArrayList<String>();
int length=arrayList.size();
if(length>2)
{
for(i=0;i<length;i++)
{
if(i<(length-1))
{
arrayList2.add((i+1)+":"+arrayList.get(i));
}
else
{
arrayList2.add("最短路程:"+arrayList.get(i)+"km");
arrayList2.add(" ");
}
}
}
else
{
for(String asd :arrayList)
{
arrayList2.add(asd);
}
arrayList2.add("起点和终点路程较近、不需要换乘");
}
LoadData(arrayList2);
}
//加载数据到listview上面privatevoid LoadData(ArrayList<String> a) {
listv.setAdapter(new ArrayAdapter<String>(this, android.R.layout.simple_list_item_1, a));
}
}
补充
图的遍历
图的遍历有两种遍历方式：深度优先遍历(depth-first search)和广度优先遍历(breadth-first search)。
图的遍历是指从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。图的遍历操作和树的遍历操作功能相似。图的遍历是图的一种基本操作，图的其它算法如求解图的连通性问题，拓扑排序，求关键路径等都是建立在遍历算法的基础之上。
由于图结构本身的复杂性，所以图的遍历操作也较复杂，主要表现在以下四个方面：
① 在图结构中，没有一个“自然”的首结点，图中任意一个顶点都可作为第一个被访问的结点。
② 在非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有顶点，因此，还需考虑如何选取下一个出发点以访问图中其余的连通分量。
③ 在图结构中，如果有回路存在，那么一个顶点被访问之后，有可能沿回路又回到该顶点。
④ 在图结构中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，存在如何选取下一个要访问的顶点的问题。
图的遍历通常有深度优先搜索和广度优先搜索两种方式，他们对无向图和有向图都适用。
1.深度优先遍历
基本思想：首先从图中某个顶点v0出发，访问此顶点，然后依次从v0相邻的顶点出发深度优先遍历，直至图中所有与v0路径相通的顶点都被访问了；若此时尚有顶点未被访问，则从中选一个顶点作为起始点，重复上述过程，直到所有的顶点都被访问。可以看出深度优先遍历是一个递归的过程。
2.广度优先遍历
基本思想：首先，从图的某个顶点v0出发，访问了v0之后，依次访问与v0相邻的未被访问的顶点，然后分别从这些顶点出发，广度优先遍历，直至所有的顶点都被访问完。
c++实现
#include<iostream> #include<queue> #include<stack> #include<stdlib.h> #define MAX 100 usingnamespace std; typedef struct { int edges[MAX][MAX]; //邻接矩阵int n; //顶点数int e; //边数}MGraph; bool visited[MAX]; //标记顶点是否被访问过void creatMGraph(MGraph &G) //用引用作参数{ int i,j; int s,t; //存储顶点编号int v; //存储边的权值for(i=0;i<G.n;i++) //初始化 { for(j=0;j<G.n;j++) { G.edges[i][j]=0; } visited[i]=false; } for(i=0;i<G.e;i++) //对矩阵相邻的边赋权值 { scanf("%d %d %d",&s,&t,&v); //输入边的顶点编号以及权值 G.edges[s][t]=v; } } void DFS(MGraph G,int v) //深度优先搜索{ int i; printf("%d ",v); //访问结点v visited[v]=true; for(i=0;i<G.n;i++) //访问与v相邻的未被访问过的结点 { if(G.edges[v][i]!=0&&visited[i]==false) { DFS(G,i); } } } void DFS1(MGraph G,int v) //非递归实现{ stack<int> s; printf("%d ",v); //访问初始结点 visited[v]=true; s.push(v); //入栈while(!s.empty()) { int i,j; i=s.top(); //取栈顶顶点for(j=0;j<G.n;j++) //访问与顶点i相邻的顶点 { if(G.edges[i][j]!=0&&visited[j]==false) { printf("%d ",j); //访问 visited[j]=true; s.push(j); //访问完后入栈break; //找到一个相邻未访问的顶点，访问之后则跳出循环 } } if(j==G.n) //如果与i相邻的顶点都被访问过，则将顶点i出栈 s.pop(); } } void BFS(MGraph G,int v) //广度优先搜索{ queue<int> Q; //STL模板中的queue printf("%d ",v); visited[v]=true; Q.push(v); while(!Q.empty()) { int i,j; i=Q.front(); //取队首顶点 Q.pop(); for(j=0;j<G.n;j++) //广度遍历 { if(G.edges[i][j]!=0&&visited[j]==false) { printf("%d ",j); visited[j]=true; Q.push(j); } } } } int main(void) { int n,e; //建立的图的顶点数和边数while(scanf("%d %d",&n,&e)==2&&n>0) { MGraph G; G.n=n; G.e=e; creatMGraph(G); DFS(G,0); printf("\n"); // DFS1(G,0); // printf("\n"); // BFS(G,0); // printf("\n"); } return0; }
最后就是源代码
下载地址： https://files.cnblogs.com/files/IBPM/beijs.apk
代码下载（百度盘）、下载后请用宇宙最骚的eclipse正确姿势打开： http://pan.baidu.com/s/1pLQJ9pD
可以的话给我给赞吧! thks v m c
End
原文：http://www.cnblogs.com/IBPM/p/7825245.html
内容总结
以上是互联网集市为您收集整理的北京地铁换乘算法(二维坐标系，图的深度搜索)开源下载Android源码、性能最优解,附带C#版本全部内容，希望文章能够帮你解决北京地铁换乘算法(二维坐标系，图的深度搜索)开源下载Android源码、性能最优解,附带C#版本所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】