应该是一种图结构，如何存储图，我就不知道了。

现在有种叫 Graph database 的可能有帮助。

http://en.wikipedia.org/wiki/Graph_database

一个可行的方法：将任何两个站之间的最短路径和路径长度先计算出来，存在一个类似这样的表中：starting_station_id，targeted_station_id，path_seq，distance，time_cost，毕竟地铁而言这个信息一般是静态不变的。 至于最短路径的计算，Dijkstra 或者保留路径的 Floyd 算法都可以。 只有在计算最短路径的时候需要在内存中用邻接矩阵什么的建图，实际应用中的查询不需要再做建图或者计算，直接在数据库中读出就可以了。

我在想这个是不是直接把信息加载到客户端，然后在客户端计算的。这样不是最简单吗

#4 楼 @jjym 可以把我说的这个表直接存在客户端，比把地铁间的临接信息读到内存再做计算要快的多，占用空间可能都差不多

#5 楼 @paranoyang 我觉得在客户端计算下也无所谓。但是你这个数据量可能有点大。 我认为数据库设计除了保存每条线的站外，再有个保存换乘车站信息的表就够了。直接加载到客户端计算

#6 楼 @jjym 数据量不大，跟保存换乘信息差不多 完全没必要在手机上再做计算 :)

#2 楼 @Rei 我的理解 Graph Database 似乎不是干这个事情的，而是用于处理负责的关联关系，比如好友关系，兴趣关系

大家可以参考一下 android 上的“中国地铁”应用，它就是直接在手机上计算的。数据结构是图，算法是最小路径算法，计算量不大。