管理运筹学中最短路径问题Dijkstra算法改进研究

陆毅 崔玉朴 汪坤 姚学勤

摘  要：Dijkstra算法是求解运筹学最短路问题的重要方法之一。文章在分析传统Dijkstra算法思想的基础上寻求其优化途径，发现可以使用堆结构来优化传统算法在查找最小值时重复查找标记的遍历过程。经理论分析与具体实验测试，改进后的算法在时间效率方面明显优于传统算法，提高了该算法的效率和性能，具有较好的适用性。

关键词：最短路径;Dijkstra;堆;运筹学

中图分类号：TP301.6     文献标识码：A文章编号：2096-4706（2021）13-0084-03

The Reaserch on Improvement of Dijkstra Algorithm for Shortest Path Problem in Management Operations Reaserch

LU Yi， CUI Yupu， WANG Kun， YAO Xueqin

（Department of  Management，Wanjiang College of Anhui Normal University， Wuhu  241008， China）

Abstract： Dijkstra algorithm is one of the important methods to solve the shortest path problem in operational research. Based on the analysis of the idea of the traditional Dijkstra algorithm， this paper seeks it’s optimization approach， and finds that the heap structure can be used to optimize the traversal process of the traditional algorithm to repeatedly find the tag when looking for the minimum value. Through theoretical analysis and specific experimental tests， the improved algorithm is significantly better than the traditional algorithm in time efficiency， improves the efficiency and performance of the algorithm， and has good applicability.

Keywords： shortest path; Dijkstra; heap; operations research

0  引  言

最短路径问题是运筹学网络理论中应用最广泛的问题之一，在交通运输、城市规划、物流运输、电子导航等方面都发挥了重要的作用。在实际运用中，如码头集装箱调度、物流运输线路、旅游路径选择等都可以使用这个模型。在求解无负权网络最短路径问题时，目前公认的最好的求解方法是Dijkstra算法，至今仍在广泛运用。近年来随着信息数据的爆发，大规模数据网络最短路径计算的需求大大增加。如导航系统、救援系统都需要在尽可能短的时间内得出合适的路径。这就要求最短路径算法要有更高的效率与性能。

堆是一类数据结构，是维护数据的一个集合。在排序的问题中，可以快速对数据进行排序，时间复杂度为O（logn），并可以以O（1）的时间复杂度获取最小值，时间效率较高。使用堆结构来优化传统算法为获取最小值时重复查找遍历的过程可以减少此过程的运算次数，降低算法的时间复杂度。

在传统Dijkstra算法中，设具有n个顶点与m条边无负权回路的有向图G，算法的时间复杂度为0（n2），当n的规模较大时，算法的时间效率较低，仍具有较大的提升空间。

1  传统Dijkstra算法思想

Dijkstra算法适用于求解无负权回路网络中单源最短路的最短路径问题，用于计算网络图中某个节点到其他所有节点的最短路径代价。下面以一个具体例子来描述传统Dijkstra算法的实现过程。给定一个具有n个顶点m条边所有边权w均为正值的有向图G。求出开始节点（1号节点）到n号节点的最短距离，若开始节点到n号节点无通路，输出-1。使用二维数组g[N][N]模拟邻接矩阵来存储具有n个节点的有向图，使用一维数组dist[N]来存储1号节点到i号节点的最短距离。设集合S为当前已经确定最短路径的节点，并用布尔数组st[N]表示集合S。N大于顶点数n。下面是具体的步骤：

（1）对dist数组进行初始化。将1号节点的距离初始化为0，其余各节点距1号节点的距离初始化为无穷大或一个较大的数。dist[1]=0，dist[i]=Inf。

（2）找出未确定最短路的节点t并将其加入集合S中。

（3）使用节点t到1號节点的距离更新其他节点到1号节点的最短距离。若i节点直接到1号节点的距离大于节点i经过节点t到1号节点的距离，则用节点t更新到1号节点的距离，即dist[i]>dist[t]+g[t][i]，则dist[i] = dist[t]+g[t][i]。

（4）重复步骤2、步骤3的操作，直到S包含所有节点，算法结束，输出结果。下面给出传统Dijkstra算法函数的C++代码实现：

int Dijkstra（）  {

memset（dist， 0x3f， sizeof dist）;

dist[1] = 0;

for （int i = 0; i < n - 1; i++）  {

int t = -1;

for （int j = 1; j <= n; j++）

if （！st[j] && （t == -1 || dist[t] > dist[j]））  t = j;

for （int j = 1; j <= n; j++）

dist[j] = min（dist[j]， dist[t] + g[t][j]）;

st[t] = true;  }

if （dist[n] == 0x3f3f3f3f）  return -1;

return dist[n];  }

在上述算法中，关键的步骤2需要找出不在集合S中的与1号节点距离最近的节点t。当边权值w存放在数组、链表等线性结构时，数据在结构中的存储顺序是乱序的，为了找出最小节点t，需要遍历所有节点。该步骤的时间复杂度为O（n2），进行了大量的循环计算，当n的规模较大时，这无疑是一个制约算法运算速度的瓶颈。步骤3需要对图的m条边进行判断，其时间复杂度为O（m）。图中共有n个节点，将n个节点加入集合S中的时间复杂度为O（n）。因此传统Dijkstra算法的时间复杂度为O（n2）。当n大于10 000量级时，普通计算机并不能在1 s之内得出正确结果。这样高的时间复杂度并不能满足大规模数据网络及时性的需求，因此对传统算法进行优化是有必要的。

2  堆优化Dijkstra算法

传统Dijkstra算法固然经典，但当n的规模较大时，算法效率受限，不能满足大规模数据网络最短路径实时计算的需求，利用堆结构思想可实现有效改进。

2.1  堆（小根堆）

堆是一个维护数据的集合，若将集合T中所有的元素按照完全二叉树的顺序储存在一个一维数组中便构建出了堆。其本质是一棵完全二叉树，又根据堆顶元素为所有元素的最大值或最小值分为大根堆与小根堆。其中小根堆具有以下性质：其父节点的值小于等于子节点的值，堆顶的值是堆中最小的。这样的性质完全可以满足传统Dijkstra算法查找最小节点t的需求，优化传统算法中遍历的过程。因此可以选择采用小根堆结构来优化传统Dijkstra算法。用一维数组heap[N]来存储堆元素，设根节点的下标为x，则根节点左子节点的下标为2x，右子节点的下标为2·x+1。heap[1]为堆顶。

2.2  堆在Dijkstra算法中的应用

堆有两种基本操作，up操作与down操作。当某个节点的值大于其子节点的值或小于其父节点的值时，便需要up操作或down操作来进行调整，以此来维持堆的性质。下面简要介绍两种操作：

up操作：比较子节点与父节点值的大小，若子节点的值小于父节点，则对两个节点的值进行一次交换，直到heap[x]找到合适的位置。即若heap[2·x]（或heap[2·x+1]）

down操作：比较父节点与左右子节点值的大小，取元素值较小的路径。若父节点的值大于子节点，则对两个节点的值进行一次交换，直到heap[x]找到合适的位置。即若heap[x]> min（heap[2·x]，heap[2·x+1]），swap（heap[x]，min（heap[2·x]，heap[2·x+1]）。

在Dijkstra算法中，除了這两种基础操作外，还需要算法支持修改节点元素值、插入节点和删除节点等操作：

修改节点元素值：直接修改该节点元素值，再根据需求进行up操作与down操作将其调整到合适的位置。

插入节点：增加一个节点位，将该节点放入堆中最后的一个位置，再进行up操作将其调整到合适的位置。

删除节点：用堆中最后一个元素替代该节点，删除最后一个元素的节点位，再根据需求进行up操作与down操作将其调整到合适的位置。

这些操作，均可以使用up操作和down操作来完成实现。

根据堆的性质，无论是父节点元素值大于左右子节点元素值还是左右子节点元素值小于父节点元素值，up操作与down操作只可能运行其中一个。为了降低代码的复杂度，可以省略判断元素值部分的代码使代码更具有简明性，增加程序的鲁棒性。x为当前需要操作的节点下标，size为当前堆的大小，m为赋给待修改节点的元素值。

修改节点元素值：heap[x] = m; up（x）; down（x）;

插入节点：heap[++size] = x; up（size）;

删除节点：heap[x] = heap[size]; size--; up（x）; down（x）;

2.3  优先队列（Priority Queue）实现堆优化Dijkstra算法

在具体代码实现中，手写堆结构较为复杂。在C++语言的STL库中封装了priority_queue结构，为了减少代码复杂度，选择使用优先队列来完善算法的具体代码。在优先队列中，元素会被赋予不同的优先级，当访问元素时，具有最高优先级的元素优先出队。给予队列元素值最小为优先级时，队头则为所需求的元素最小值。在数据量较大时，如果采用邻接矩阵来存储网络图，空间复杂度较高，存储空间占用量较大，使用一维数组模拟邻接表存储网络图，可降低算法的空间复杂度，减少计算机存储空间的使用。h数组、e数组与ne数组构成邻接表来存储图，w数组存储边权值。改进后的Dijkstra函数C++代码为：

typedef pair<int， int> PII;

int Dijkstra（）  {

memset（dist， 0x3f， sizeof dist）;

dist[1] = 0;

priority_queue<PII， vector<PII>， greater<PII> > heap;

heap.push （{0， 1}）;

while （heap.size（）） {

PII t = heap.top（）;

heap.pop（）;

int dis = t.first， int v = t.second;

if （st[v]）  continue;

st[v] = true;

for （int i = h[v]; i ！= -1; i = ne[i]） {

int j = e[i];

if （dist[j] > dist[v] + w[i]） {

dist[j] = dist[v] + w[i];

heap.push（{dist[j]， j}）;  }}}

if （dist[n] == 0x3f3f3f3f） return -1;

return dist[n];  }

2.4  堆优化Dijkstra算法时间复杂度分析

在传统Dijkstra算法中，遍历查找最小值为算法瓶颈，时间复杂度为O（n2）。在优化后的算法中，查找最小值这一过程被优先队列结构代替。优先队列又为堆结构实现。获取最小值，即用堆中最后一个元素代替堆顶元素，再进行down操作进行调整，其时间复杂度为O（logn）。共有n个节点，总时间复杂度为O（nlogn）。对m条边进行判断，其时间复杂度为O（m）。因此优化后的Dijkstra算法的时间复杂度为O（nlogn）。相较于传统Dijkstra算法O（n2）的时间复杂度有了较大的进步。即使n为1 000 000的量级时，也可在1 s内得出结果。

3  两种算法大规模数据运行测试

为了检验改进后的Dijkstra算法，对算法采用较大规模的数据量进行测试。进而比较传统Dijkstra算法与堆优化Dijkstra算法在实际运行中的时间效率。分别取顶点数n为100，1 000，5 000，10 000，20 000，100 000，1 000 000来进行测试。接下来的实验中，将統一使用这些数据进行测试，以此来对比两种算法在时间效率方面的优劣。使用C++语言中<ctime>标准库中的clock（）函数来进行计时，测试两种算法中Dijkstra函数的运行时间。所用计算机为惠普笔记本电脑，测试环境为Dev-C++ IDE 5.4.0，操作系统为Win 10家庭中文版，CPU为Intel（R） Core（TM） i5-8300H CPU @ 2.30 GHz，内存为16 GB DDR4。其测试结果如表1所示。

由表1的试验测试结果来看，随着n的规模不断增大，堆优化Dijkstra算法的运行时间愈发短暂，远优于传统算法。传统算法当n大于10 000时，程序的运行时间急剧增加。n为20 000时就需要几秒钟的时间来进行运算，而堆优化Dijkstra算法仍只需要几毫秒便可以得出结果，时间效率远优于传统算法。这样的时间效率完全可以满足较大数据规模网络图计算最短路径的问题，可以应用于对及时性要求较高的导航、救援等系统。这也说明了使用堆结构来优化传统Dijkstra算法是完全可行的。

4  结  论

本文在传统算法的基础上，使用堆结构来优化传统算法查找最小值时重复查找标记的遍历过程，并具体实现了堆优化Dijkstra算法。相对于传统算法使用遍历算法来查找最短路径的节点，使用堆结构只需要比较相邻节点的值，并可直接获取最小值，减少了程序运行时的计算次数，提高了算法的时间效率。使用了大规模数据进行测试，研究比较了传统Dijkstra算法与堆优化Dijkstra算法的时间复杂度与运行时间。将传统Dijkstra算法O（n2）阶的时间复杂度降低至O（nlogn）阶。实验结果显示，堆优化Dijkstra算法在时间效率方面远优于传统算法，大大提高了传统算法的效率与性能。

参考文献：

[1] 张翰林，关爱薇，傅珂，等.Dijkstra最短路径算法的堆优化实验研究 [J].软件，2017，38（5）：15-21.

[2] 王志和，凌云.Dijkstra最短路径算法的优化及其实现 [J].微计算机信息，2007，（33）：275-277.

[3] 邱慧，黄解宇，黄丽丹.管理运筹学中最短路问题的两种算法研究 [J].运城学院学报，2014，32（2）：89-91.

[4] 严蔚敏，吴伟民.数据结构（C语言版） [M].北京：清华大学出版社，2002.

[5] 李健.基于Dijkstra最短路径算法的优化研究 [J].渭南师范学院学报，2009，24（5）：61-64.

[6] 韩伟一.基于固定序的Bellman-Ford算法的改进 [J].运筹与管理，2015，24（4）：111-115.

[7] DIJKSTRA E W. A note on two problems in connexion with graphs [J].Numerical Mathematics，1959，1（1）：269-271.

[8] 胡运权，郭耀煌.运筹学教程 [M].北京：清华大学出版社，1998.

[9] 曲大鹏，侯振桓，宣伟宏，等.最小生成树相关算法在计算机程序设计竞赛中的研究 [J].辽宁大学学报（自然科学版），2020，47（2）：118-123.

作者简介：陆毅（2000—），男，汉族，安徽蚌埠人，本科在读，研究方向：运筹学。