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）使用边界路径信息找出最短路径。