存在阻塞路段路网最优路的Dijkstra优化算法

开篇：润墨网以专业的文秘视角，为您筛选了一篇存在阻塞路段路网最优路的Dijkstra优化算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

经典Dijkstra算法用来求解两固定点间的最短路问题，本文的主要内容是给出存在阻塞路段路网的最优路问题的dijkstra优化算法.

一、引言

最优路问题是重要的最优化问题之一，在现实生活中，我们往往需要考虑时间最优，费用最优，最安全等带有附加条件的最优路问题，而不仅仅是距离最短的问题。本文的主要内容就是在经典Dijkstra算法的基础上，给出了存在阻塞路段路网最优路问题的优化算法。

二、存在阻塞路网的路网中最优路的Dijkstra优化算法

（一）Dijkstra算法定义

Dijkstra（迪科斯彻）算法是典型的解决单源最短路径问题的一个贪心算法，用于计算所构成的数学模型中一个节点到其他所有节点的最短路径.节点用顶点集表示，设置顶点集合并不断做贪心选择来扩充这个集合.主要特点是以起始点为中心从选取具有最短特殊路径的顶点向外层层扩展，从而确定从源到的最短路径长度。

（二）存在阻塞路网的路网优化方案

当按算法计划好的路径行驶途中遇到阻塞问题时，通常的解决方法是将所有被阻塞路径的权值修改为，再次使用Dijkstra算法计算从当前所在顶点到终点的最短路径。本文将这种方法称为“直接法”，下面以具有单个堵塞点的路网为例，设发生阻塞的概率为，具体步骤如下：

（1）用Dijkstra算法求出最短路径，其费用为；

（2）用直接法计算出当网络发生阻塞时，改道路径，其费用为；

（3）假设网络中一定会发生阻塞，将阻塞路段的相应权值修改为，用Dijkstra算法求出此时的最短路，其费用为；

（4）比较与的大小：若，则应选择原最短路；若，则应选择路径.

（三）评价

在上述优化算法中，是按照原最短路行使费用的期望，是此时费用的理论平均值，而是按照新最短路行驶费用的期望，同样是此时费用的理论平均值，该优化算法的核心思想是通过对这两种期望值的比较，即通过对理论平均费用值的比较，来确定最佳路线.这种理论平均费用的比较从概率意义上讲是合理的，有助于人们作出理性的选择。

三、算法举例

给定赋权有向图如图1所示，假设已知图中只有弧会发生阻塞，其阻塞概率为，求出此种情况下从顶点到顶点的最优路。

解：由Dijkstra算法可知：

从顶点到顶点的最短路径为，

费用为60；

若达到点时，弧发生阻

塞，不能通行，此时用Dijkstra

算法计算知点到点的最短路

为，该段路费用为70，可

知该情况下路径为，总费用为100；

由上可知，，，，.将弧的权值修改为，得如下算法迭代过程：

则，.解不等式，得。于是，当时，应选择路线；当时，应选择路线。

（作者单位：黄淮学院数学科学系）