！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分钟通话, 中国电信官方发货

改变数据库字符集编码可以用:ALTER DATABASE database
COLLATE ....
《数据结构》里那个什么Dijkstra算法看过了，最短路径问题还行，可是拿来做这个我搞不出来。
回复allan2002(丸子) :
如能找到，贴出来也算你的功劳。
其实可以不用图的,实现如下(delphi):type
  Tbus=record
     no:Integr;       //车号
     da:Boolean;      //单还是复（true单、false复）
     name:TStringList;//该车经过的站
   end;  Pbus=array of Tbus;var
  start,end:String;//分别存放起始和终止点站
  bus:Pbus;
  i,findex,eindex,count:Integer;
  Index:Integer;//用来记录要乘哪一辆车
begin
  //假设所有的车信息都记录在bus中了
  count:=10000; //开始时赋一个相对大的数;
  Index:=-1;
  for i:=low(bus) to high(bus) do
  begin
    findex:=bus[i].name.indexof(start);
    eindex:=bus[i].name.indexof(end);
    if (findex=-1) or (eindex=-1) then  //先判断这辆车是否有这两个站
      continue;
    if bus[i].da then
    begin//单
     if findex>eindex then
        continue
     else if eindex-findex<count then
     begin
      count;=eindex-findex;
      Index:=i;
     end
    end
    else if eindex-findex<count then//复
    begin
      count;=eindex-findex;
      Index:=i;
    end;
  end;
  if count=-1 then
    showmessage('没有车')
  else
    showmessage('是'+bus[index].no+'路车');
end;
這個比最短路徑的實現要簡單得多,以下用 BCB 語法描述
1、數據定義：
class TStation  //定義每一個汽車站
{
String Name ;  //站名
int ID ;       //對應地圖中站點。應該要用到，可你的題目沒要求用到，
//因為你只要求轉車最少就行了，不要求路程最短，時間最快或要求最省錢的乘車方案
//所以不需要有地圖，不需要有路程表，也不需要有速度表。相對簡單得多
};
TStation *AllStation ; //這裡有全部的站點,用NULL結束
class TBusRoute  //定義每一路車
{
String Name ;  //名稱
TStation *StartStation, *EndStation ; //起點站與終點站
TList *Routes;      //路線：途經的所有站點,這裡用TList
int RouteID ;       //車次
bool IsDouble ;     //true為雙行線，false為單行線.
};
TBusRoute *AllBusRoutes ; //這裡有所有的路線,用NULL結束
//初始化代碼這裡不寫了，要求按上述描述正確初始化。
問題描述：
起點站 : TStation *mySTART ;
目的站 : TStation *myEND ;
乘車策略：中转车次最少
實現函數：void FindmyRoute(TStation *mySTART,TStation *myEND,TStrings *Result);
//說明TStrings *Result ; 用於顯示結果的地方。
//以下是偽代碼：
void FindmyRoute(TStation *mySTART,TStation *myEND,TStrings *Result)
{
//1、檢查起點站，目的站是否在全局站點中，如果不在將引起異常
assert(mySTART);
assert(myEND);
//2、找出經過起點站的所有車次,將其放入myStartRoutes中,目的站放入myEndRoutes。
TList *myStartRoutes = new TList;
TList *myEndRoutes = new TList;
TBusRoute *pRoute = AllBusRoutes ;
while(pRoute)
  {
   for(int i=0 ; i < pRoute->Routes->Count ; ++i)
     {
      TStation *tmpStation = (TStation *)pRoute->Routes->Item[i];
      if(tmpStation == mySTART)
         myStartRoutes->Add(tmpStation);
      else if(tmpStation == myEND)
         myEndRoutes->Add(tmpStation);
     }
  }
//下面開始找答案：
//3、在集合myStartRoutes與myEndRoutes，同時出現的路線是一個解。
bool OK = false ; //找到答案:OK = true ;
Result->Items->Clear(); //清空結果
Result->Items->Add("答案是：");
  for(int i=0;i< myStartRoutes->Count; ++i)
  for(int j=0;j< myEndRoutes->Count; ++j)
    {
     if(myStartRoutes->Item[i] == myEndRoutes->Item[j])
        {
         OK = true ;
         Result->Items->Add(
           "請乘坐"+((TBusRoutes *)(myStartRoutes->Item[i]))->Name)+
           ",在“"+ mySTART->Name +"”上車" +
           "在“"+ myEND->Name +"”下車。" );
         //break;這裡沒加這行，是要把所有符合條件的解都給出。
        }
     }
if(OK) return ;
//4、在集合myStartRoutes的每一路車的站點中尋找目標與myEndRoutes集合中出現的車次。
/*
如果找到，則只要轉一次車就行了，這裡不寫了，這兩個規則能應付大部分查找，因為一般情況下只要轉一次車。下面的程序是最壞的情況，不知要轉多少次車，只要兩個站點都在全局站點表中，那是不可能無解的，這點請注意。
//5、尋找方法：
1)、在通過目標站點找出所有通過該站點的路線myEndRoutes1
2)、在myEndRoutes1集合中整理出現的站點，找出能通向目標站點的集合。
3)、在起始站點也同目標站點作同樣的處理。
4)、通向目標站點的集合，通向起始站點的集合中，找出重合的站點，這就是解。
5)、遞歸實現上述過程就可以了。因為無解的情況已經被剔除，所以不必擔心找不到解。
*/
}
我想到一个算法，谁能把它变为代码？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项编成一个过程，然后递归调用，我为了说明得更清楚，所以没有用递归，而是每一步骤都给出，便于大家理解。
呵呵
这个是我的数据结构的课程设计的题目，刚开始我们老师说这个题目太难，不想让我搞，但是我还是搞了，但是有个毛病就是他只能转一次车，把代码贴出啦对楼主你也许有帮助。（本程序在vc6.0＋win2k server下调试通过）
#include<iostream.h>
#include<stdlib.h>
typedef struct{
int *ceci;
int *zhandian;
int length;
int listsize;
int incrementsize;
}moni;
void initlist(moni &l,int maxsize,int incresize);//初始化线性表
int locatezhandian(moni l,int e);//查询站点
moni link(moni l1,moni l2);//线性表连接
int * jiaoji(moni l1,moni l2);//求两线性表的交集，即转车地
void main()
{
moni one,two,three,four,five;
moni t;
moni r;
int szd;//所在地
int mdd;//目的地
int i(0);
int k(0);
int suozaidi[5];//用来记录经过所在地的车次。
int mudidi[5];//用来记录经过目的地的车次。
initlist(one,100,10);
initlist(two,100,10);
initlist(three,100,10);
initlist(four,100,10);
initlist(five,100,10);
initlist(t,100,10);
initlist(r,100,10);
for(int length=0;length<8;length++)
one.ceci[length]=1;//表示本路车为1路
one.zhandian[0]=1;
one.zhandian[1]=3;
one.zhandian[2]=6;
one.zhandian[3]=9;
one.zhandian[4]=13;
one.zhandian[5]=17;
one.zhandian[6]=11;
one.zhandian[7]=27;
one.length=8;
    for(length=0;length<8;length++)
two.ceci[length]=2;//表示本路车为2路
     two.zhandian[0]=1;
two.zhandian[1]=4;
two.zhandian[2]=7;
two.zhandian[3]=9;
two.zhandian[4]=16;
two.zhandian[5]=18;
two.zhandian[6]=22;
two.zhandian[7]=30; for(length=0;length<8;length++)
three.ceci[length]=3;//表示本路车为3路
     three.zhandian[0]=2;
three.zhandian[1]=9;
three.zhandian[2]=10;
three.zhandian[3]=14;
three.zhandian[4]=17;
three.zhandian[5]=19;
three.zhandian[6]=23;
three.zhandian[7]=29;
     for(length=0;length<8;length++)
four.ceci[length]=4;//表示本路车为4路
     four.zhandian[0]=3;
four.zhandian[1]=8;
four.zhandian[2]=12;
four.zhandian[3]=15;
four.zhandian[4]=19;
four.zhandian[5]=20;
four.zhandian[6]=24;
four.zhandian[7]=28;
for(length=0;length<8;length++)
five.ceci[length]=5;//表示本路车为5路
     five.zhandian[0]=1;
five.zhandian[1]=5;
five.zhandian[2]=7;
five.zhandian[3]=9;
five.zhandian[4]=15;
five.zhandian[5]=18;
five.zhandian[6]=21;
five.zhandian[7]=30;
cout<<"请输入您现在所在地点的代码：";
     cin>>szd;
cout<<"请输入您想前往的地方的代码：";
cin>>mdd;
if(szd<1 || szd>30)
{cout<<"所在地点代码错误！！";
     exit(1);
}
if(mdd<0 || mdd>30)
{ cout<<"目的地点代码错误！！";
exit(1);
}
if(locatezhandian(one,szd)!=-1)
suozaidi[0]=1;
else
suozaidi[0]=0;
if(locatezhandian(two,szd)!=-1)
suozaidi[1]=2;
else
suozaidi[1]=0;
if(locatezhandian(three,szd)!=-1)
         suozaidi[2]=3;
else
suozaidi[2]=0;
if(locatezhandian(four,szd)!=-1)
suozaidi[3]=4;
else
suozaidi[3]=0;
if(locatezhandian(five,szd)!=-1)
         suozaidi[4]=5;
else
suozaidi[4]=0;
if(locatezhandian(one,szd)!=-1 && locatezhandian(one,mdd)!=-1)
{ cout<<"您可以在您现在所在的地方乘坐1路公共汽车到您的目的地下车即可";
exit(1);
}
else
if(locatezhandian(one,mdd)!=-1)
mudidi[0]=1;
else
mudidi[0]=0;    if(locatezhandian(two,szd)!=-1 && locatezhandian(two,mdd)!=-1)
{cout<<"您可以在您现在所在的地方乘坐2路公共汽车到您的目的地下车即可";
exit(1);
}
else
if(locatezhandian(two,mdd)!=-1)
mudidi[1]=2;
else
mudidi[1]=0;   if(locatezhandian(three,szd)!=-1 && locatezhandian(three,mdd)!=-1)
   {cout<<"您可以在您现在所在的地方乘坐3路公共汽车到您的目的地下车即可";
   exit(1);
   }
else
if(locatezhandian(three,mdd)!=-1)
mudidi[2]=3;
else
mudidi[2]=0;   if(locatezhandian(four,szd)!=-1 && locatezhandian(four,mdd)!=-1)
   {cout<<"您可以在您现在所在的地方乘坐4路公共汽车到您的目的地下车即可!";
   exit(1);
   }
else
if(locatezhandian(four,mdd)!=-1)
mudidi[3]=4;
else
mudidi[3]=0;
   if(locatezhandian(five,szd)!=-1 && locatezhandian(five,mdd)!=-1)
   {cout<<"您可以在您现在所在的地方乘坐5路公共汽车到您的目的地下车即可!";
   exit(1);
   }
else
if(locatezhandian(five,mdd)!=-1)
mudidi[4]=5;
else
mudidi[4]=0;for(k=0;k<5;k++)
  if(suozaidi[k])
    for(int s=0;s<5;s++)
      if(mudidi[s])
  {
     switch (suozaidi[k])
{
          case 1: t=one;break;
          case 2: t=two;break;
          case 3: t=three;break;
          case 4: t=four;break;
          case 5: t=five;break;
}
        switch (mudidi[s])
{
         case 1: r=one;break;
         case 2: r=two;break;
         case 3: r=three;break;
         case 4: r=four;break;
         case 5: r=five;break;
}
  }
  int *g;
g=jiaoji(t,r);
  cout<<"你可以从你所在地点乘坐"<<g[0]<<"路车到"<<g[1]
  <<"转"<<g[2]<<"路车到您的目的地下车即可！";
}void initlist(moni &l,int maxsize,int incresize)//初始化线性表
{
l.ceci=new int[maxsize];
l.zhandian=new int[maxsize];
l.length=8;
l.listsize=maxsize;
l.incrementsize=incresize;
}int locatezhandian(moni l,int e)//查询站点
{
  int i=0;
  int *p=l.zhandian;
  while (i<l.length && *p++!=e)
  i++;
    if(i<l.length)
   return i;
  else
  return -1;
}moni link(moni l1,moni l2)//线性表连接
{
int i;
i=l1.length+l2.length;
moni l3;
initlist(l3,i,10);
for(i=0;i<l1.length;i++)
{
l3.ceci[i]=l1.ceci[i];
l3.zhandian[i]=l1.zhandian[i];
l3.length++;
};
int k=0;
while(i<=l1.length+l2.length)
{
    if(!locatezhandian(l3,l2.zhandian[k])){
l3.ceci[i]=l2.ceci[k];
l3.zhandian[i]=l2.zhandian[k];
l3.length++;
i++;
};
k++;
}
return l3;
}int * jiaoji(moni l1,moni l2)//求两线性表的交集，即转车地点
{
int *fanhui;
int i;
fanhui=new int [4];
for(i=0;i<4;i++)
fanhui[i]=0;
for(i=0;i<l1.length;i++)
{
if(locatezhandian(l2,l1.zhandian[i])!=-1){
fanhui[0]=l1.ceci[i];
fanhui[1]=l1.zhandian[i];
        fanhui[2]=l2.ceci[locatezhandian(l2,l1.zhandian[i])];
fanhui[3]=l2.zhandian[locatezhandian(l2,l1.zhandian[i])];
break;
}
}
if(i<l1.length)
return fanhui;
else return 0;
}
用一条SQL语句就能查询出来。在那个面示里面见过，好象就是要求用一条查询语句作答。
本贴结了，请以下同志向我索取分数：
billyqiao(如冰) 200分
ljc_zy(彷徨) 200分
haoco(程序员) 100分
PPower(榜榜榜...XunSun) 100分
ALNG(?) 300分
xwffwx() 100分