GIS空间数据库（75）图的最短路径算法

       “最短”可以是距离、时间或其他约束。路径计算有三类：

       （1）单对（single pair）：找出两个顶点间的最优路径。

       （2）单源（single source）：给定一个顶点，找出从该顶点到图中其它所有可达顶点之间的最优路径。

       （3）所有对（all pair）：找出所有顶点对之间的最优路径。

       单对最短路径的Best-first算法

       是一个启发式框架，它通过使用领域相关的语义信息来提高算法的速度。它使用一个评估函数f(v, d)来低估结点v和d之间的最短路径的代价，评估函数还能提供额外的信息，将最短路径的搜索聚焦到目的结点上，减少所需检查的结点数。 A*是Best-first搜索算法的一个具体例子，一般采用欧氏距离作为评估函数。没有评估函数的Best-first搜索算法与Dijkstra算法没有太大区别。

       层次算法

       上面算法只适用于可以将整个空间网络放在主存中的情况，而对于大型空间网络，网络不能全部放在主存中，因此采用层次策略来解决。

       层次算法把一个大的空间图分解成一个边界图和一系列分片图，这些图都比原来的图要小。

       使用层次算法来计算最短路径的基本思想是：把原来的图分解成一系列更小的分片图和一个汇总图（叫做边界图）。通过适当地构建边界图，就可以把一个对原图的最        短路径查询分解为一系列对更小图的最短路径查询。层次算法包括三个步骤：在边界图中找到相关的边界结点对；计算边界路径；扩展边界路径。

       层次算法寻找路径的例子。

       （1）找出源或目的到他们边界结点的代价。

       （2）用穿过分片图的代价来决定哪些边界结点一定在路径上。

       （3）找出通过边界图的路径。

       （4）使用边界路径信息找出最短路径。