寻找任意点对之间的最短路径是图数据管理中典型的、重要的基本操作之一。随着各种大型网络数据的不断涌现,实现在线的最短路径查询成为了当前图数据管理领域迫切需要解决的问题。为此,通常需要通过预计算最短路径并将其组织成为合适的索引结构,从而实现常量时间内的最短路径查询(SPQ)回答。然而,直接的最短路径索引方案需要消耗O(N2)的空间代价,这对于大型网络而言是无法承受的。针对这一问题,本文提出了一种基于区间表示的第一跳划分表示方法。经过对该问题的形式化定义和分析,证明了该问题是NP难问题。为了使得算法能应用于大网络,本文提出了多种启发式编码生成方案。按核心算法分类,本文提出的方法可以分为基于旅行商问题的编码生成方法和基于区间树的编码生成方法两类；按编码数量分为单编码方案和多编码方案两类；按算法框架分类分为独立区间编码算法和与其它已知最短路径索引算法整合算法两类。此外,针对两个第一跳划分的距离计算问题,提出了基于划分二部图的第一跳划分距离近似算法,并证明了其算法近似度。模拟网络和真实网络上的实验结果表明,本文所提的算法在索引空间代价以及查询响应时间上都明显优于目前公认的流行算法。此外,本文的方法具有普适性,可以直接应用现有的流行算法,在不损失影响查询效率的同时进一步降低最短路径索引代价。