网络最短路径定界搜索算法

用Dijkstra算法求解大规模网络两顶点间最短路径时,需计算大量与最短路径无关的顶点,效率较低.双向定界搜索算法是首先对网络进行双向搜索,得到一条经任意点的最短路径.一般情况下,这条路径已非常接近、甚至等于最短路径.然后,以此路径的标号(即路径长)作为搜索计算的界,进行双向标号计算,对超过界的顶点不再计算,以提高计算效率.算法分析表明,用该算法可使计算效率提高约一倍.