考虑禁行路线路网的最优路径求解

为了解决含有禁行路线路网中的最优路径求解问题．研究了含有装行路线路网的特点．建立了数学模型。通过路网转化法把含有禁行路线的路网转化为不含禁行路线的路网．降低了最优路径求解的难度。采用邻接结点关系矩阵和邻接结点权矩阵表达路网中结点和路段的拓扑关系，减少了路网的存储空间。用动态邻接结点关系矩阵和邻接结点权矩阵对经典的Dijkstra算法进行了改进，节省了计算机存储空间、提高了计算效率．并给出了基本算法。将所研究的路网转化方法和改进的Dijkstra算法应用于所研发的车辆诱导系统软件，并进行了实际测试。测试结果表明．府用该方法能够在含有禁行路线的路网中求解最优路径．且运算效率较高。

Solution to Optimal Path in Road Network with Restricted Routes

In order to solve the optimal path in road network with restricted routes, this paper analyzed the characteristics of road network with restricted routes, and constructed its mathematic model. The road network with restricted routes was translated into the road network without restricted routes according to the studied method, which reduced the complexity of the optimal path solution. The topological relationship of nodes and road sections in road network was expressed By adjacent node relation matrix and adjacent node weight matrix, which saved the storage space. The traditional Dijkstra algorithm was optimized with dynamic adjacent node relation matrix and adjacent node weight matrix, which reduced the storage space and improved the calculation efficiency, and the corresponding algorithm was given. A vehicle guidance system was developed with the optimized Dijkstra algorithm to find the optimal path in the restricted road network. Test results indicated that the method for transforming road network and optimized Dijkstra algorithm was efficient in calculating the optimal path in the road network with restricted routes.