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

摘要

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