消息关闭
    暂无新消息!

全部路径计算法的性能优化

问题作者 : Hookway2017-07-14发布
现有表A:

id   road_id   enter_station_id   exit_station_id    miles    money
1     1              1                             91                    2890     30
2      1             2                             89                   2789       38
......


表A共有7w多条数据,现在要找出出任意两个站之间的所有路径,有什么思路?
如果用路径计算法,每一个节点的路径都遍历一遍,那么每次找任意两站的路径都需要遍历7w*7w=49亿次,存在严重的性能问题。

9个回答

︿ 3
http://blog.csdn.net/lysc_forever/article/details/17500959
像这个blog类似,每一个节点就是一个站点(station_id)
︿ 2
图的遍历有固定算法,相信你在《数据结构》中已经学过
技巧产生于数据组织形式,怎么能说没关系呢?
︿ 2
或者先不说表A现有的数据和字段,就拿这个url里面的图一来讨论。假设表A每一条数据记录了url里图一的一条路径(例如:节点0到节点1),而表A一共有7w多条路径。现在,我想找出表A里面任意2个节点间的全部路径,怎么找?按照url里的算法,性能存在问题。
︿ 1
《数据结构》已经忘记得7788了

数据组织形式,无非就是一个节点由 路id 和 站id组合为一个节点,即 road_id、station_id是组合唯一的。

数据表里面记录的就是每个相邻的节点的连线,例如:id=1记录的就是节点road_id=1 and station_id=1 与 road_id=1 and station=91之间的连线。也可以理解为road_id=1 and station_id=1是节点0,road_id=1 and station=91是节点1。
︿ 0
修正一下表A,少了个字段:
id   enter_road_id   enter_station_id    exit_road_id  exit_station_id    miles    money
1      1                        1                             1                   91                    2890       30
2      1                        2                             2                   89                    2789       38
3      1                        91                           2                    3                     2893       30

例如:假设从enter_road_id=1 and enter_station_id =1 到达exit_road_id=2 and exit_station_id=3
期间经过了这几条路:
1、id=1
2、id=2
︿ 0
修正一下表A,少了个字段:
id   enter_road_id   enter_station_id    exit_road_id  exit_station_id    miles    money
1      1                        1                             1                   91                    2890       30
2      1                        2                             2                   89                    2789       38
3      1                        91                           2                    3                     2893       30

例如:假设从enter_road_id=1 and enter_station_id =1 到达exit_road_id=2 and exit_station_id=3
期间经过了这几条路:
1、id=1
2、id=3