！1000分！我要一个算法，使用任何高级语言描述都行，要快！答对给1000分，UP的同志则平分100分。

请给出这样一个算法:某城市有公交车路线：
1路：001站->002站->003站->005站->003站->002站->001站（复线）
2路：001站->005站->009站->002站->009站->005站->001站（复线）
3路：004站->006站->007站->009站->008站（单线）
4路：004站->010站->011站->008站->011站->010站->004站（复线）
……
（随手写的，其实按照公交路线地图还可以写得更多）请给出中转车次最少的路线方案。
如：起点start：001，终点end：005；路线方案path[i]：1路车
起点：011，终点：002；路线方案：4路车->004站->3路车->009站->2路车本题可以使用任何一种高级语言描述其算法。1000分。动作要快。
UP的同志则可平分本贴100分。

解决方案 »

免费领取超大流量手机卡，每月29元包185G流量+100分钟通话, 中国电信官方发货

回复billyqiao(如冰) :
呵呵，要求是必须用数组来存储的，没有数据库。回复JennyVenus() ( ) :
早就去发了。回复qqqdong() ( ) &lxcc(虫莲) ( ):
教科书都翻烂了。《数据结构》里那个什么Dijkstra算法看过了，最短路径问题还行，可是拿来做这个我搞不出来。
回复xing0091() :
只能用数组来装公交车路线。怎么设计随你的喜欢。
1、找出所有从“起点”出发的线路，设为RecordsetFrom；
2、找出所有到达“终点”的线路，设为RecordsetTo；
3、首先找“直达”，如果一条线路即出现在RecordsetFrom，又出现在RecordsetTo，则该条线路为“直达”，即中转为0次。
4、再找中转1次的。首先将直达线路从RecordsetFrom和RecordsetTo中移除。遍历RecordsetFrom中的每一条线路，设为“线路A”，再遍历这条线路中除“起点”外的每一个站名，设为“中转站”。找出所有从“中转站”出发的线路，设为RecordsetMid。如果一条线路即出现在RecordMid，又出现在RecordsetTo，则该条线路为“线路B”，即：起点-〉线路A-〉中转站-〉线路B-〉终点。
5、中转多次的算法就是上述算法的循环套接，描述起来比较复杂，而且就公交出行来说中转2次以上的线路实用性不大。这样的描述你应该可以明白了吧？
如果需要以上具体算法的话，给我发站内消息。
具体代码现在一时没有，不过给个基本思路还可以：
这是个典型的最优路线问题：
一、第一个接点（第一站）连接的站点有多少个n1，就是第一步确定的最多有多少条路线step1=n1
    第二批站点连接的站点有多少个，并除掉第一个站点得到n2，就确定了到第二站后最多有多少条路线：step2=n2*step1,如果第二批站点中有目的站点，则结束
......................
    第m批站点连接的站点有多少个，并除掉第m-1个站点得到nm，就确定了到第m站后最多有多少条路线：stepm=m*step(m-1)，如果第m批站点中有目的站点，则结束，如果没有，判断记录的路线中是否有回到该路线以往站点的情况，如果有，说明循环行使，清除该路线
...............
呵呵，这个思路如果用数组来解决，比如：青岛市公交路线有300条，平均每条有20站，且都是复线，线路站点的相交比率为10%，这样的情况下恐怕是会死机的，还请高手指点吧
回复 onlineboy(stame) :
你的思路简直就和我的一样，可是算到中转2路时，就太复杂了，3路更不用说了。但至少要给出中转到2路，才有实际意义嘛。
回复onlineboy(stame) ( )  :
因为条件限制，没有数据库可用。
up，gz
下班回去写，翻翻数据结构书
请你到太原公交网上去查一下，http://www.tybus.com/，那个线路查询是我做的，绝对高效，功能比你需要的还强大，你看看好吗，如果觉得合适的话，我可以详细给你解决，OK？？？
回复CounterKing(King) :
甚好！不过速度好慢，估计是遍历了所有路线吧，我只关心最佳方案，即http://www.tybus.com/查询系统给出的第一个方案。希望能参考你的设计思想。
我也给个思路吧，要是真的写程序起码好几天.
1.编写函数
函数 a（起点，终点）
输出参数：线路名
代码：查找所有线路，找出包含终点和起点名的线路。2.查找直达：调用函数a(起点,终点)
3.转一次车：调用函数a(起点,起点),取出返回的线路中所有站点，循环调用函数a(站点,终点)。
4.转两次车：调用函数a(终点,终点),取出返回的线路中所有站点，同步骤3中的所有站点做两重循环调用函数a(站点，站点).实际应用中线路一般在几百条，不会很多。函数a也不必查找所有线路，上面的每个步骤都不用查找上面步骤中找过的线路。
我想到一个算法，谁能把它变为代码？1000分就属他（她）。1.从起点站s开始，记转车次数=0，
2.查询含有s的所有车次n，
3.对于车次n，查找s站能到达的所有站点s1，
4.逐个排查s1中是否有终点站e：
  a.如果有，即找到了路径，记录在path数组中，跳到output；
  b.如果没有，则记录下已经查找过的车次数组f，下次无需再排查此车次，到下一步查找1次中转；5.从中转站s1开始，记转车次数=1，
6.查询含有s1的所有车次n，
7.对于车次n，查找s站能到达的所有站点s2（无需查找f），
8.逐个排查s2中是否有终点站e：
  a.如果有，即找到了路径，记录在path数组中，跳到***
  b.如果没有，则记录下已经查找过的车次数组f，下次无需再排查此车次，到下一步查找1次中转；9.从中转站s2开始，记转车次数=2，
10.查询含有s2的所有车次n，
11.对于车次n，查找s站能到达的所有站点s3（无需查找f），
12.逐个排查s3中是否有终点站e：
  a.如果有，即找到了路径，记录在path数组中，跳到***
  b.如果没有，则记录下已经查找过的车次数组f，下次无需再排查此车次，到下一步查找1次中转；13.从中转站s3开始，记转车次数=3，
14.查询含有s3的所有车次n，
15.对于车次n，查找s站能到达的所有站点s4（无需查找f），
16.逐个排查s4中是否有终点站e：
  a.如果有，即找到了路径，记录在path数组中，跳到***
  b.如果没有，则记录下已经查找过的车次数组f，下次无需再排查此车次，到下一步查找1次中转；
……如此循环下去，当然，可以把每4项编成一个过程，然后递归调用，我为了说明得更清楚，所以没有用递归，而是每一步骤都给出，便于大家理解。
给一个思路，抛砖引玉。
假定每一条路线都是复线的情况下：即对于线路上的a,b两个站点 a->b 和b->a存在。
考虑线路小于等于32条，更多也是一样的处理。那么每个站点有一个唯一的集合，它用一个32位变量表示。
如1路：001站->002站->003站->005站->003站->002站->001站（复线）
2路：001站->005站->009站->002站->009站->005站->001站（复线）
3路：004站->006站->007站->009站->008站（单线）
4路：004站->010站->011站->008站->011站->010站->004站（复线）
001 站的对应的集合为{1,2}变量为11000000000000000000000000000000，也就是说001站出现在
1路和2路，所以它对应的位被设置为1，其它位被设置为0 。
求最优路线的问题就变成求集合的交集，要求满足两个集合相交时，中间的集合数量最小。
首先，看出发站点的所在集合(a)与终点站的集合(b)是否相交，方法很简单
如果  a xor b <>0 则两个集合相交，说明两个站点在同一条线路上，此时显然是最优的。
如果不成立，列出a中的所有路线中的其他站点的集合，求这些集合与b是否相交。
方法是将每个站点对应的集合与a求并
即  a=a or c 'c为满足条件的站点对应的集合
   然后看a 与b是否相交，如果相交，此时为需要转车一次的路线
否则列出b中的所有路线中的其他站点的集合，求这些集合与a是否相交。
即  b=b or c 'c为满足条件的站点对应的集合
   然后看a 与b是否相交，如果相交，此时为需要转车两次的路线
那么同理，直到所有站点对应的集合都列入，而不相交说明两个站点无法通过换车到达。
或者a和b两个集合相交，就是我们要求的路线。
这样做的话，我们只需要为每个站点设置一个32变量，以及每条路线包含的站点信息
就可以了。
操作简单，简单按位逻辑运算。
回复ljc_zy(彷徨) :
很好的思路！
楼主，算法已经有了，程序也简单，运算量很小，速度很快，你真的能兑现1000分吗？把Mail地址贴出来，两天内给你一个编译过的文件。
回复billyqiao(如冰):
[email protected]
我也在努力的写代码中……估计很快能出来结果了。
而且代码也不长。
如果真的有1000分的话，呵呵——
用个简单的动态规划可以做出来。
如果有N个站的话，循环次数为N*N*N，应该很快吧。
首先定义个2维数组a，a[i,j]用来存放i站和j站之间最短的换车次数。
最开始的时候，a所有元素置一很大的值，比如200,然后把有车直通的两站间对应元素置1,数组的左上到右下的对角线置0，因为从i到i不需要乘车。
还需要一个数组来放车次信息，这个很简单，自己解决。
for i=1 to n do
for j=1 to n do
for k=1 to n do
{  if a[i,j]>a[i,k]+a[k,j] then
            ------比如说当前走法i到j要转5次，但是从i到k要2次，从k到j要1次，那么i到j就只要1+2=3次就可以了，现在要做的就是把从i到j的乘车方法改成先从i到k，在从k到j。在这里，i是起点，j是终点，k用来做中转站。理解了吗？
         {  a[i,j]=a[i,k]+a[k,j];
             改变乘车方案
         }
等你的分哦：）
用一个表：
站名,1路，2路，... (路数量应该不大)
001站,r01,r02,r03
002站，
003站，
……
将r01,r02,...装入一个表中排序即可，用不了什么程序
dim i as integer
for i = 1 to 1000
form1.caption=form1.caption & "UP"
next i
本贴结了，兑现诺言1000分，请以下同志向我索取分数：
billyqiao(如冰) 200分
ljc_zy(彷徨) 200分
haoco(程序员) 100分
PPower(榜榜榜...XunSun) 100分
ALNG(?) 300分
xwffwx() 100分