最短路径问题是图论中的经典问题，它不仅广泛应用于早期的简单网络，而且在涉及到复杂网络的各个领域中也得到了多方面的应用，例如:在一个给定负载量的交通网络中选择从出发地到目的地耗时最短的路径;在矢量化地图中寻找两地之间的最短路径;在网络中依据网络负载选择最佳路由等等。在复杂网络中，搜索符合最短、最快等条件的路径对于挖掘网络中的关键信息有着重大意义，而且随着近年来互联网的不断发展扩大，以及信息网络规模的飞速膨胀，网络中的最短路径问题又一次成为了研究的焦点问题，而且对算法的可扩展性有了越来越高的要求。　　给定一个有向无环带权图，在图中任选两点作为起点和终点，最短路径查询将给出这两点之间的一条最短路径。最短路径查询算法中的经典之一是Dijkstra算法，但是该算法采用的是宽度优先的方式，只能解决单源最短路径问题，因此当查询针对任意点之间时，需要进行多次重复计算。同时该算法是典型的内存算法，可扩展性较差，当前的很多研究都对其进行了改进。　　本文首先基于深度优先搜索的方式将区间编码技术引入带边权的有向无环图中，提出了图的TRS结构。通过区间编码，将图中一个连通分支中的边划分为树边和非树边，而非树边又根据其起点和终点所在的分枝是否相同分为S边(Separating Edge)和R边(Remaining Edge)。这样，所有结点的区间编码，结合S边和R边，就构成了这个连通分支的TRS结构。同时，本文还对区间编码进行了改进，使其不仅能够完整保留图的拓扑结构，还能将边权值映射到点权值从而保留权值信息。　　接着，本文基于TRS结构提出了解决最短路径查询的TRS算法。当查询到来时，算法首先根据起点和终点的带权区间编码进行初步计算得到最短路径的上界，然后再结合S边和R边进一步降低上界，直到求得这两点之间的最短路径。通过实验对比，本文很好的证明了TRS算法能够很好的保证查询的时间代价不随图的规模成多项式复杂度上涨。　　由于TRS结构自然的对图进行划分的特性，本文结合层次图框架，将TRS算法扩展到了磁盘图领域。对于一个TRS结构，如果同属于它的两个边界点之间存在最短路径，则将这两点加入到框架图中，并用一条权值等于其最短路径代价的边连接这两点。对每个TRS结构都进行这种计算，就可以得到该TRS结构上的框架图。再把框架图作为新的图进行处理，直至框架图中不存在边界点。当查询到来时，首先在最底层TRS群中找到起点和终点所属的TRS，然后将与它们相关联的边界点找出，然后将这些边界点映射到更高一层的TRS群中，作为新的查询点，重复这种搜索，直至最高层;然后再将每一层中的查询结果返回给下一层，直至最底层。为了验证该扩展算法的正确性和有效性，本文还在采集来的wikipedia数据集上进行了实验。　　本文最后还提出了几个对算法的改进思路，由于在预处理过程中，需要计算出所有同属于一个TRS结构的边界点之间的最短路径，所以可以考虑通过缩小TRS结构的规模来减少它所包含的边界点的数目，进而降低预处理的时间代价。