《基于一般Dijkstra的改进算法在最短路径问题中的应用》-农学论文，农业论文-论文范文参考-科学狗论文网

标题

基于一般Dijkstra的改进算法在最短路径问题中的应用

范文

岳晓娟

[摘要]首先，本文以一般Dijkstra算法为基础，对一般Dijkstra算法的计算方式进行了改进；然后，通过具体算例将一般Dijkstra算法与其改进算法的具体步骤进行了详细演示；最后，分析了基于一般Dijkstra算法的改进算法在教学过程中体现出的求解步骤更加快捷、方便，最小T标号寻找时间较短且出错率较低，最短路径寻找时间较短及图示算法方便学生理解四方面的优点，期望对《运输与配送》课程中关于最短运输路线问题的教学具有一定的推广意义。

[关键词]最短路径问题；Dijkstra算法；改进

[中图分类号]O157.5 [文献标识码]A

Dijkstra算法作为典型的最短路径算法，用于计算图中一个顶点到其地各顶点的最短路径。Dijkstra算法在物流专业课程《运输与配送》中的最短运输路线选择这部分内容中也有涉及，且内容较为重要，但经过长期教学发现，大多数学生认为一般Dijkstra算法计算步骤较多，计算速度较慢，容易出错，理解不深，难以掌握。因此，笔者改进了一般Dijkstra算法的呈现形式，尝试了以图示法来展示一般Dijkstra算法，更加方便学生理解与教师教学。

1 最短路径问题的描述

对最短路线问题的描述：设G=（V，E）为带权图，V={v0，v1，…，vn-1}，E={e1，e2，…，em}，n个顶点，m条边，图中各边（vi，vj）有权dij（dij=∞，表示vi，vj之间无边），vi，vj为图中任意两点，单源最短路径就是从G中找到源点v0到其余各点的最短路径。

2 最短路径问题的一般Dijkstra算法求解

目前Dijkstra标号法被认为是求无负权网络最短路线问题的最好方法。算法的基本思路基于以下原理：若序列的最短路，则序列的最短路。即若{v0，v1，…，vn-1，vn}是从v0到vn的最短路线，则序列{v0，v1，…，vn-1}必为从v0到vn-1的最短路线。Dijkstra标号法的计算方法如下：

2.1 标号定义

定义两种标号：T标号（临时标号）和P标号（永久标号），给vi点一个P标号，表示从v0到vi点的最短路权，vi点的标号不再改变；给vi点一个T标号，表示v0到vi点的估计最短路权的上界，是一种临时标号，凡没有得到P标号的点都有T标号。算法：每一步都把某一点的T标号改为P标号，当终点vn-1得到P标号时，全部计算结束。

2.2 计算步骤

（1）给v0以P标号，P（v0）=0，其余各点均给T标号，T（vi）=+∞。

（2）若vi点为刚刚得到P标号的点，考虑这样的点vj：（vi，vj）属于E，且vj为T标号。对于vi的T标号进行如下的更改：

T（vj）=min[T（vj），P（vi）+dij]

（3）比較所有具有T标号的点，把最小者T标号改为P标号，即：

P（）=min[T（vi）]

当存在两个以上最小者时，任取一个改为P标号。若终点得到P标号则计算结束，否则用代替vi转回步骤（2）。

3 最短路径问题的改进算法求解

考虑到一般Dijkstra算法求解过程中书写内容过多，容易出错，因此，在一般Dijkstra算法求解步骤的基础上尝试了对一般Dijkstra算法进行改进的图示法。具体步骤如下：

（1）在第一行和第一列依次写上v0，v1，…，vn-1；

（2）从起点v0开始，在第一行v0与第一列v0，交叉的空格内填写0，代表P（v0）=0，并找出与v0直接相连的点vj，并设定T（vj）=d0j，第二行其余各空格均填写+∞，代表T（vi）=+∞；

（3）从第二行中的数据中选择数值最小的（假设最小值为min），并在对应的空格内记为，代表已经找到一条从起点v0出发到达最小数值对应第一列那一顶点（从最小数值垂直向上画线，与第一行交叉的那个顶点）的最短路径，即已将最小数值对应的点修改为P标号；

（4）从刚刚已经得到P标号的点（在数值右上角打了*号的该数值画垂直线与第一行交叉的顶点）出发，找到与该点后续相连的点，并将这些点对应的空格数值进行如下标记：

T（vj）=min[T（vj），P（vi）+dij]

（5）比较所有顶点中未标*的点，给最小者（未标*的所有列中的数字取最小）标注*号；当存在两个以上最小者时，任取一个标注为*号。若终点得到*号则计算结束，否则重复步骤（4）（5）。

4 两种算法的算例比较分析

4.1 给出一个带权图G=（V，E），如图1所示，请找出从起点v0出发到达终点v7的最短路线

4.4 对比分析

通过以上两种方法的算例求解，很显然，基于一般Dijkstra算法的改进算法在方便学生理解与教师教学方面呈现出了较多的优势：

（1）一般Dijkstra算法求解步骤书写较多，而改进算法的求解步骤书写更加快捷、方便；

（2）一般Dijkstra算法求解过程中，每一步在寻找最小T标号数值时需在前面步骤中认真寻找T标号最小的数值，寻找时间较长，且若稍有疏忽极易出错，而改进算法则只需在表中未打*号的列中的数字中选择最小的即可。因此，其选择最小T标号的时间较短，且出错率较低；

（3）一般Dijkstra算法求解过程最后一步倒推最短路线时，需在求解步骤中认真寻找P标号，并将每一步的P标号进行倒推，然后得出最短路线。而改进算法只需从终点开始在表中找到每一步打*号的点，然后将其对应的右下角的角标作为前一个点，即可一次倒推出最短路线，其求解时间较短，且出错率较低。

通过以上结论可得，基于一般Dijkstra算法的改进算法在最短路径问题的求解过程中更加方便、快捷，不仅能够使得学生便于理解，而且有助于教师教学。因此，其在《运输与配送》课程中的最短运输路线问题的求解过程中具有一定的推广意义。

[参考文献]

[1] 陈芳芳，姜忠义，吴春青.运筹学教学中的动态规划求解最短路径问题的一个注记[J].高师理科学刊，2016（09）.

[2] 徐天亮.运输与配送（第2版）[M].北京：中国物资出版社，2012.

随便看

科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。