小弟在做毕业设计,关于公交查询的,现在到最后一个阶段了,就是公交换乘的实现,我知道这比较难,可能还会涉及到最短路径算法,现在小弟的表结构如下:
Line_ID Stop_Name Orders
1 火车站 1
1 长岛路口 2
1 韭菜园 3
1 乔庄 4
2 火车站 1
2 曙光路口 2
2 韭菜园 3
3 博物馆 1
3 新华门 2
3 乔庄 3
. ..... .
希望哪位高手帮我用C#写一下这个实现的代码,我只要做到最多两次换乘就可以了,我在论坛上看到跟我这个类似的有很多,但都是SQL语句,我希望哪位高手帮我弄成C#实现的代码,小弟不胜感激!!
参考的帖子有http://topic.csdn.net/u/20070829/10/a617b2c9-39a2-440a-a193-bddb91a07b93.html
和http://topic.csdn.net/t/20050107/13/3706990.html 表结构基本和我的一样,我做的是C/S的,数据库是SQL Server 2000
Line_ID Stop_Name Orders
1 火车站 1
1 长岛路口 2
1 韭菜园 3
1 乔庄 4
2 火车站 1
2 曙光路口 2
2 韭菜园 3
3 博物馆 1
3 新华门 2
3 乔庄 3
. ..... .
希望哪位高手帮我用C#写一下这个实现的代码,我只要做到最多两次换乘就可以了,我在论坛上看到跟我这个类似的有很多,但都是SQL语句,我希望哪位高手帮我弄成C#实现的代码,小弟不胜感激!!
参考的帖子有http://topic.csdn.net/u/20070829/10/a617b2c9-39a2-440a-a193-bddb91a07b93.html
和http://topic.csdn.net/t/20050107/13/3706990.html 表结构基本和我的一样,我做的是C/S的,数据库是SQL Server 2000
用流程图,做一个流程下来,一步步的实现就可以了.
用一个邻接表有向图来表示一个公交系统
如果乘坐某辆公交车能从站点u到达站点v而不需要换线、调头,那么添加一条有向边e=(u,v),并且在边e上附加信息:从u到v的距离(即该边的权值)、该边所属的公交车编号、该边在该公交线路的哪个方向上(因为有可能同一条公交线路两个方向经过不同的站点)
之所以用邻接表是因为这样的图是有重边的
当查询从节点i到节点j的换乘线路时,用dijkstra找出i和j之间的最短路径,那么根据这条路径上的边的附加信息就知道要怎么换乘了 另外,如果需要知道路径最短的基础上怎样换乘的次数最少(也就是在上述的图中经过的边数最少),可对dijkstra作少量调整,对于图中的每个点u,除了记录当前找到的到该点的最短距离dis[u]以及该点的前趋pi[u],还要记录在这样的最短距离和前趋下从起点到该点经过的最少的边数min_edge[u]
那么作dijkstra的时候,对于当前刚找到的路径最短的点u,以及从点u出发的某条边e=(u,v),如果dis[u]+e.length==dis[v] && min_edge[u]+1<min_edge[v](也就是经过边(u,v)与原先的到v的最短路径长度相同但是经过(u,v)可以得到边数更少的路径,那么也要采用(u,v)) 回溯是效率非常低的算法,如果没有非常好的优化方案,没事少用link url
http://zhidao.baidu.com/question/33275213.html
要算的就是给出两个地名,查找最短路径就行了吧?
不过不用SQL似乎不现实,总不能全部取到内存进行查找吧
S1 S2 S3 S4 S5 S6
-----------------------------------------------------------------
B1 + + +
-----------------------------------------------------------------
B2 + +
-----------------------------------------------------------------
B3 +
-----------------------------------------------------------------
B4 + +
-----------------------------------------------------------------
B5 + +先从 S6 看,S6 停靠的只有 B5,然后判断 B5 不到 S1,经搜索得到 B5 和 B2、B3 有共站(S5),这两辆车也不到 S1,然后判断 B4 和 B2 有共站(S4),
依次类推,最后得到:B1 -- B4 -- B2 -- B5
S1 S2 S3 S4 S5 S6
-----------------------------------------------------------------
B1 + + +
-----------------------------------------------------------------
B2 + +
-----------------------------------------------------------------
B3 +
-----------------------------------------------------------------
B4 + +
-----------------------------------------------------------------
B5 + +
static list<Line_ID> 方案;
static Line_ID
void 得到解决方案(A,B){
if(A==B){
方案队列.add(方案);
}else{
foreach(Line_ID){
if(Line_ID到A && 当前方案.contains(Line_ID)==false){
当前方案.add(Line_ID);
foreach(站点 C in Line_ID的所有站点){
得到解决方案(C,B);
}
当前方案.remove(Line_ID);
}
}
}
}这样"方案队列"中就存放了所有的换乘方案(1.可能没有方案,也可能至少换乘3次以上 2.不会包含循环的方案比如A-C-A-C-B ),然后再根据条件判断最佳方案.
根据楼主的条件,可以循环"方案队列"中的"方案",然后取"方案"中count数最小的.ps:如果想得到所有方案,除非可以根据距离等其他因素智做出能的判断,否则上述算法已基本为最优算法.