线路 经过站
100路 : A站,B站,C站,D站,E站
101路 : F站,G站,H站,I站,G站
102路 : A站,P站,Q站,R站,S站
103路 : K站,L站,M站,N站,O站
104路 : I,M,Z站现在要从A站到Z站，且路程最短改如何写算法呢，请给出思路和详细代码
100路 : A站,B站,C站,D站,E站
101路 : F站,G站,H站,I站,G站
102路 : A站,P站,Q站,R站,S站
103路 : K站,L站,M站,N站,O站
104路 : I,M,Z站现在要从A站到Z站，且路程最短改如何写算法呢，请给出思路和详细代码
100路 : A站,B站,C站,D站,E站
101路 : F站,E站,H站,I站,G站
102路 : A站,P站,G站,R站,S站
103路 : K站,I站,M站,G站,O站
104路 : I,M,Z站现在要从A站到Z站，且路程最短改如何写算法呢，请给出思路和详细代码
[url=http://www.phpclasses.org/search.html?words=Dijkstra+algorithm&restrict[0]=C&restrict[1]=B&restrict[2]=D&forums=F&go_search=1&advanced=1]http://www.phpclasses.org/search.html?words=Dijkstra+algorithm&restrict[0]=C&restrict[1]=B&restrict[2]=D&forums=F&go_search=1&advanced=1[/url]
http://www.algolist.com/code/php/Dijkstra%27s_algorithm
1，站点表stop(stop_id,stop_name)
2，路线表line(line_id,line_name)
3，路线站点表(点线路关系表)linestops( line_id, stop_id, seq )此处的seq指某站点在某线路中的顺序。
现在分析算法：
1，直达线路
首先根据两个站点名获取两个站点各自的id，这里定义为id1,id2
然后查询
select line_id from
(select line_id from linestops where stop_id = id1) A,
(select line_id from linestops where stop_id = id2) B
where A.line_id = B.line_id
即得到可直达的线路列表2,一次换乘
首先根据两个站点名获取两个站点各自的id，这里定义为id1,id2
然后搜寻两个站点通过直达方式各自能够到达的站点集合，最后他们的交集就是我们所需要的换乘站点。
select stop_id from
(
select distinct stop_id from linestops where line_id in
(select line_id from linestops where stop_id = id1)
)A,
(
select distinct stop_id from linestops where line_id in
(select line_id from linestops where stop_id = id1)
)B
where A.stop_id= B.stop_id
得到换乘站（可能有多个或0个）后，剩下的就是显示能够到达换乘站的两边线路，这通过前面的直达查询即可。3，二次换乘
首先根据两个站点名获取两个站点各自的id，这里定义为id1,id2
算法的中心思想是：站点1能够通过直达到达的所有站点集合A，站点2能够通过直达到达的所有站点集合B，A和B之间有直达的线路。
一步一步来：
站点1能够通过直达到达的所有站点集合A：
select distinct stop_id from linestops where line_id in
(select line_id from linestops where stop_id = id1)
站点2能够通过直达到达的所有站点集合B：
select distinct stop_id from linestops where line_id in
(select line_id from linestops where stop_id = id2)
而直达的查询是
select line_id from
(select line_id from linestops where stop_id = id1) C,
(select line_id from linestops where stop_id = id2) D
where C.line_id = D.line_id我们把=id1和=id2换成 in (select ....)A 和 in (select ...)B这样最后我们的查询是
select line_id from
(select distinct line_id from linestops where stop_id in 【A】) C,
(select distinct line_id from linestops where stop_id in 【B】) D
where C.line_id = D.line_id
其中【A】是
（select distinct stop_id from linestops where line_id in
(select line_id from linestops where stop_id = id1))
其中【B】是
（select distinct stop_id from linestops where line_id in
(select line_id from linestops where stop_id = id2))
这样子我们找到了作为中间换乘的线路（可能有多条或者0条），对列举的的每一条假设命名为X线，下一步就是找出可以从站点1到达X任意一个站点的直达线路、和可以从站点2到达X任意一个站点的直达线路即可。
那么与前面的算法相似，我们在站点1所有能够到达的站点中去寻找和线路X相交的站点，然后再去找这两个点的线路
select stop_id from
(select distinct stop_id from linestops where line_id in
(select line_id from linestops where stop_id = id1))A,
(select stop_id from linestops where line_id = X ) B
where A.stop_id = B.stop_id
找到站点了，下面就是根据已经解决的直达查询找线路了。
站点2类似。
以上的算法有一个优点，全部是sql完成搜寻，所以asp代码只需寥寥几行循环而已。
但是缺点是：慢,毕竟可能涉及了数百次sql查询。而且只是用最简单的sql方法去算出所有可以换乘的方案，不涉及最优/最短的算法。如果是最短路径，那得用特殊结构和算法。另外:根据出行者输入的起点和终点，确定出行要选择的起始公交站点A和目的公交站点B。搜索数据库，查询站点A和站点B之间是否有相同的车经过，如果有一条或几条直达线路，通过比较选择距离最短的公交线路推荐给出行者。如果没有，则计算站点A和站点B之间有没有一个公共站点C，从站点C可以换乘到达站点B。这就有两种情况：(1)如果有，属于一次换乘。计算站点A和公共站点C之间有没有相同的公交车经过并存入集合X；同样，计算站点B和公共站点C之间有没有相同的公交车经过并存入集合Y。将这两个集合比较后就可以得到从站点A经过公共站点C到达站点B的公交线路，在这些线路中进行比较，选择距离最短的推荐给出行者。（2）如果没有公共站点C，就出现了要换乘两次的情况。将经过站点A的每条公交线路的所有站点存入集合O；同样，经过站点B的每条线路的所有站点存入集合P。比较这两个集合，先乘经过站点A的某一路车到达某一站点D，计算站点D与站点B之间有没有公共站点E,如果有则站点D、E为换乘站点。这种方案可能有多种，比较选择距离最短的推荐给出行者。如果不存在公共站点E，说明经过两次换乘无法从站点A到达站点B，停止搜索计算。公交出行最优路线具体算法：1） 输入起始站点A和目的站点B；2） 搜索系统数据库，经过起始站点A的公交线路存为X(i)(i=1,2,3…,m,m为正整数)，经过目的站点B的公交线路存为Y(j)(j=1,2,3,…n,.n为正整数)；3） 判断是否有X(i)=Y(j)，将满足条件的存入Z。若Z＝1，则该条公交线路X(i)即Y(j)为从站点A到站点B的直达最优线路，输出结果并结束运算。Z≥1，计算Z中各条线路的距离，选择一条距离最短的线路，输出结果并结束运算；4） 搜索系统数据库，公交线路X(i)所包含的站点存为O(i,u)(u=1,2,3…,g,g为正整数)公交线路Y(j)所包含的站点存为P(j,v)(v=1,2,3…,h,h为正整数)；5） 判断是否有O(i,u)= P(j,v)，将满足条件的存入W。若W＝1，则站点O(i,u)即P(j,v)为从站点A到站点B的一次换乘站点，公交线路X(i)，Y(j)为换乘一次的最优路线，输出结果并结束运算。若W≥1，分别计算每条换乘路线的距离，选择一条距离最短的线路，输出结果并结束运算；6） 搜索系统数据库，经过站点O(i,u)的公交线路存为R(k)(k=1,2,3…,p,p为正整数)，公交线路R(k)所包含的站点存为G(k,t)(t=1,2,3…,q,q为正整数)；7）判断是否有G(k,t)=P(j,v)，将满足条件的存入S。若S＝1，则站点G(k,t)即P(j,v)为从站点A到站点B的二次换乘站点，公交线路X (i)，R(k)，Y(j)为换乘二次的最优路线，输出结果并结束运算。若S≥1，分别计算每条换乘二次的路线距离，选择一条距离最短的线路，输出结果并结束运算；8） 以上步骤没有找到合适的公交线路,输出“没有找到换乘次数不超过两次的最优公交线路”，结束运算。
但实际上很简单，尤其是用 php 实现class bus {
var $d = array(
100 => array('A', 'B', 'C', 'D', 'E'),
101 => array('F', 'E', 'H', 'I', 'G'),
102 => array('A', 'P', 'G', 'R', 'S'),
103 => array('K', 'I', 'M', 'G', 'O'),
104 => array('I', 'M', 'Z'),
);
var $ex = array(); function find($s, $e) {
$res = $this->find_back($s, $e);
if($res) $res = array($s => $res);
return $this->format($res);
}
function format($ar) {
$res = array();
foreach($ar as $p=>$r) {
if(! is_array($r)) return array($p);
foreach($r as $l=>$c) {
foreach($this->format($c) as $v) {
$res[] = "$p - [$l] - $v";
}
}
}
return $res;
}
function find_back($s, $e, $ex=array()) {
$res = array();
$d = $this->filter($s, $ex);
$ex = array_merge($ex, array_keys($d));
foreach($d as $k=>$r) {
if(in_array($e, $r)) {
$res[$k] = array($e => $k);
}
foreach($r as $v) {
$t = $this->find_back($v, $e, $ex);
if($t) $res[$k][$v] = $t;
}
}
return $res;
}
function filter($a, $ex) {
$res = array();
foreach($this->d as $k=>$r) {
if(in_array($k, $ex)) continue;
if(in_array($a, $r)) $res[$k] = $r;
}
return $res;
}
}
$p = new bus;
print_r($p->find('A', 'Z'));
Array
(
[0] => A - [100] - E - [101] - I - [104] - Z
[1] => A - [100] - E - [101] - G - [103] - I - [104] - Z
[2] => A - [100] - E - [101] - G - [103] - M - [104] - Z
[3] => A - [102] - G - [101] - I - [104] - Z
[4] => A - [102] - G - [103] - I - [104] - Z
[5] => A - [102] - G - [103] - M - [104] - Z
)
101路 : F站,G站,H站,I站,G站
102路 : A站,P站,Q站,R站,S站
103路 : K站,L站,M站,N站,O站
104路 : I,M,Z站
明显A到B，B到C，F到G的路程不可能一样长，那么时间也不可能一样多，问的是路程最短，大家写的却都是“站最少”，没有对的这个首先要有两站之间的距离，以距离为data，进行运算查询。还有说道算法，把大学学的算法导论学了，就会了。。这是一个简单的求最短路径问题。
这个应该很容易理解的
function filter($a, $ex) {
$res = array();
foreach($this->d as $k=>$r) {
if(in_array($k, $ex)) continue;
if(in_array($a, $r)) $res[$k] = $r;
}
return $res;
}
递归函数，用于找出到达目标站点的路径
function find_back($s, $e, $ex=array()) {
$res = array();
$d = $this->filter($s, $ex);//找到经过$s站的线路
$ex = array_merge($ex, array_keys($d));
foreach($d as $k=>$r) { //对于每条线路
if(in_array($e, $r)) {
$res[$k] = array($e => $k); //找到了目标站点
}
foreach($r as $v) { //对于每个站点
$t = $this->find_back($v, $e, $ex); //递归检查是否能到达目标
if($t) $res[$k][$v] = $t; //能到达就保存
}
}
return $res;
}算法很简单，就是深度优先遍历图
个人认为返回的数据结构很巧妙，你观察一下就知道
对于这个返回结构，我倒是尝试了很久
<?php
$lines = array(
100 => array( 'A' , 'B' , 'C' , 'D' , 'E' ) ,
101 => array( 'F' , 'E' , 'H' , 'I' , 'G' ) ,
102 => array( 'A' , 'P' , 'G' , 'R' , 'S' ) ,
103 => array( 'K' , 'I' , 'M' , 'G' , 'O' ) ,
104 => array( 'I' , 'M' , 'Z')
);function get_line( $position1 , $position2 , $lines )
{
$collection = array();
foreach( $lines as $k => $v )
{
if( in_array( $position1 , $v ) )
{
foreach( $v as $kk => $vv )
{
if( $position1 == $vv )
{
continue ;
} if( $vv == $position2 )
{
return array( $k => $vv ) ;
}
else
{
unset( $lines[$k] );
$sub_collection = get_line( $vv , $position2 , $lines );
if( !empty( $sub_collection ) )
{
$collection[$k] = array( $vv , $sub_collection );
}
}
}
}
else
{
continue ;
}
}
return $collection ;
}$line = get_line( 'A' , 'Z' , $lines );
print_r( $line );
?>
(
[100] => Array
(
[0] => E
[1] => Array
(
[101] => Array
(
[0] => G
[1] => Array
(
[103] => Array
(
[0] => M
[1] => Array
(
[104] => Z
) ) ) ) ) ) [102] => Array
(
[0] => G
[1] => Array
(
[101] => Array
(
[0] => I
[1] => Array
(
[104] => Z
) ) [103] => Array
(
[0] => M
[1] => Array
(
[104] => Z
) ) ) ))
$lines = array(
100 => array( 'A' , 'B' , 'C' , 'D' , 'E' ) ,
101 => array( 'F' , 'E' , 'H' , 'I' , 'G' ) ,
102 => array( 'A' , 'P' , 'G' , 'R' , 'S' ) ,
103 => array( 'K' , 'I' , 'M' , 'G' , 'O' ) ,
104 => array( 'I' , 'M' , 'Z')
);
//aeimz
//aeiz
//aegiz
//aegmz
//agimz
//agiz
//agiz
//agmz
function get_line( $position1 , $position2 , $lines )
{
$collection = array();
foreach( $lines as $k => $v )
{
if( in_array( $position1 , $v ) )
{
foreach( $v as $kk => $vv )
{
if( $position1 == $vv )
{
continue ;
}
if( $vv == $position2 )
{
$collection[$k][] = array( $k => $vv ) ;
}
else
{
unset( $lines[$k] );
$sub_collection = get_line( $vv , $position2 , $lines );
if( !empty( $sub_collection ) )
{
$collection[$k][] = array( $vv , $sub_collection );
}
}
}
}
else
{
continue ;
}
}
return $collection ;
}$line = get_line( 'A' , 'Z' , $lines );
print_r( $line );
?>
我觉得这跟统计文章的词出现次数一样啊，
用一个trie tree