最短路径查询是图数据管理中非常重要的一类问题,本文研究了基于某些约束的最短路径查询问题,不同的约束条件对应于不同的问题,它们是一类特殊的最短路径查询问题。本文中,基于约束的最短路径是指:给定必经点集,返回的最短路径经过必经点集中的所有点且路径满足约束条件。目前已有的工作侧重于空间数据集(两点之间的最短距离用欧氏距离表示)上的最短路径问题,它采用穷举的方式列出所有满足约束的路径,然后选择长度最小的路径作为问题的解。然而,在实际的道路交通网中,两点之间的距离等于两点之间的最短路径的长度,它往往大于两点之间的欧氏距离,此外,已有的算法求解此类问题相当于枚举出所有满足约束条件的必经点的排列,然而,大部分排列对于求解最短路径来说是冗余的,采用穷举的方式会造成大量重复的计算。本文对每个问题设计了相应的求解算法,具体的工作如下:1、基于点约束的最短路径查询问题,即给定一些必经的点,寻找一条从起点到终点且经过所给必经点的最短路径。对于此问题,本文的主要工作有:提出了一种新的有效的算法,并对此算法设计了两种优化技术来寻找具有顶点约束的最短路径;设计了可以应用于大规模图上的多项式时间的近似算法,并且证明了近似算法的近似比为3;在几个真实数据集上进行了实验验证,并将本文的算法与最先进的算法进行比较,实验结果验证了算法的有效性。2、基于规则的最短路径查询问题,即给定起点和终点,寻找一条从起点到终点的最短路径,使得此路径经过用户指定点集中的所有点且某些点的访问要满足一定的先后顺序。对于此问题,本文的主要工作有:提出广义规则树的概念,设计了生成广义规则树的算法,并利用广义规则树来判断算法是否找到一条基于规则的最短路径;设计了一个基于最优子路径的前向扩展算法,该算法可以快速求解基于规则的最短路径问题,并设计了前向扩展算法的改进算法–基于最短优先策略的前向扩展算法;在真实的数据集上设计了大量的实验,并与已有的性能最好的算法做比较,实验结果验证了本文算法的有效性。本文主要研究基于某些约束的最短路径查询问题,并围绕不同的约束所对应的不同问题,分别设计了相应的求解算法,本文所设计的算法与同类问题中已有的算法相比均具有较好的查询性能。