运筹学C语言实现Dijkstra算法求解图的最短路径

[收稿日期]2021-10-28[基金项目]全国高校、职业院校物流教改教研课题（JZW2021145）；成都文理学院一般项目“应用型本科院校工商管理专业《运筹学》课程教学改革研究”（WLYB2021046）[作者简介]蒲松（1981-），男，四川绵阳人，博士（后），成都工业学院副教授，研究方向：物流管理、运筹优化；夏嫦（1981-），女，成都文理学院副教授，硕士，研究方向：应用数学。

doi:10.3969/j.issn.1005-152X.2022.05.030物流管理专业背景下“运筹学”课程思政的教学设计与探索蒲松1，夏嫦2（1.成都工业学院经济与管理学院，四川成都611730；2.成都文理学院经济与管理学院，四川成都610401）[摘要]以物流管理专业为背景，将知识工具、职业素养与德育价值融通，探索物流管理专业背景下运筹学课程思政的教学设计，不仅使学生掌握专业知识，而且提升其文化自信与民族自豪感，培养其对专业的认同感与使命感，树立正确的人生观、价值观。

[关键词]“运筹学”课程思政；物流管理；知识工具；德育价值；职业素养[中图分类号]G641[文献标识码]A [文章编号]1005-152X(2022)05-0144-04Design and Exploration of Ideological and Political Elements in Operations Research Course forLogistics Management SpecialtyPU Song 1,XIA Chang 2(1.School of Economics &Management,Chengdu Technological University,Chengdu 611730;2.School of Economics &Management,Chengdu College of Arts &Sciences,Chengdu 610401,China)Abstract:In this paper,in the context of the logistics management specialty,and in an attempt to integrate knowledge instrument,professional quality and moral value,we explored the design of the ideological and political elements of the Operations Research course for the logistics management specialty,which aimed not only to enable the students to master professional knowledge,but also enhance their cultural self-confidence and national pride,cultivate their sense of identity and vocational calling,and establish the correct values on life.Keywords:ideological and political element in Operations Research course;logistics management;knowledge instrument;moral value;professional quality0引言随着经济全球化进程的加快和信息社会的来临，网络文化发展迅猛，传统价值观念和话语体系的不断变化，对民族乃至国家精心架构的意识形态樊篱造成巨大冲击[1]。

一、简介迪杰斯特拉(Dijkstra)算法和弗洛伊德(Flyod)算法均是用于求解有向图或无向图从一点到另外一个点最短路径。

二、Dijkstra迪杰斯特拉算法也是图论中的明星算法，主要是其采用的动态规划思想，使其在数据结构、算法、离散数学乃至运筹学中都扮演重要的角色。

以下图为例：以A为起点，首先走一步，共有三条边，分别如下：AB(12),AF(16),AG(14)其中最短的是节点B，将AB(12)放入辅助向量。

接着，各节点均继续向下走，此时可以找出4条边。

ABC(22),ABF(19),AF(16),AG(14),同样找出最小值放入向量中。

{AB(12)，AG(14)}此后步骤完全相同A B C D A 0426B 50∞12C∞∞3ABC(22),ABF(19),AF(16),AGF(23),AGE(22)，选中AF(16)。

同样，接下来的步骤有：ABC(22),AFC(22),AFE(18),AGE(22)，选中AFE(18);ABC(22),AFC(22),AFEC(23),AFED(22)，这种情况随便选取一个最小值，以ABC(22)为例；ABCD(25),AFED(22)选中后者，至此，已经完全找到A 和所有节点之间的最短路径及最短路径的长度。

最短路径向量为{AB(12)，AG(14)，AF(16)，AFE(18)，ABC(22)，AFED(22)}三、Floyd弗洛伊德是另外一种求最短路径的方式，与迪杰斯特拉算法不同，弗洛伊德偏重于多源最短路径的求解，即能迪杰斯特拉能够求一个节点到其余所有节点的最短路径，但是弗洛伊德能够求出任意两个节点的最短路径，当然迪杰斯特拉重复N 次也能达到目标。

两种方式的时间复杂度均为O(n^3)，但弗洛伊德形式上会更简易一些。

以下面的有向有权图为例：老版visio 不知道为啥这么糊？首先写出图的邻接矩阵AdjA B C DD71∞0若想缩短两点间的距离，仅有一种方式，那就是通过第三节点绕行，如果我们假设仅能通过A点绕行，那么仅需判断是否现有的距离Adj[i][j]小于Adj[i][1]+Adj[1][j]的距离，如果有更短的选择，那么进行更新就好了。

南邮运筹学运输问题实验报告南邮运筹学运输问题实验报告1.实验目的：本次实验旨在通过针对不同运输问题的建模和解决过程，掌握运筹学在实际运输问题中的应用方法，提高运筹学实践能力。

2.实验内容：本次实验包括两个部分：单源最短路径问题和车辆路径规划问题。

（1）单源最短路径问题：通过建立带权有向图模型，使用Dijkstra算法和Bellman-Ford算法求解从起点到终点的最短路径及其长度。

（2）车辆路径规划问题：通过建立车辆路径规划模型，使用模拟退火算法和遗传算法求解最短路径和最短时间路径。

3.实验结果：（1）单源最短路径问题：使用Dijkstra算法求解起点到终点的最短路径和长度如下图所示：路径：1->3->4->5->7，路径长度为23。

使用Bellman-Ford算法求解起点到终点的最短路径和长度如下图所示：路径：1->3->4->5->7，路径长度为23。

（2）车辆路径规划问题：使用模拟退火算法求解最短路径和最短时间路径如下图所示：最短路径：1->4->5->2->3->1，路径长度为33；最短时间路径：1->3->4->5->2->1，路径时间为15。

使用遗传算法求解最短路径和最短时间路径如下图所示：最短路径：1->4->5->2->3->1，路径长度为33；最短时间路径：1->3->4->5->2->1，路径时间为15。

4.实验结论：本次实验通过求解单源最短路径问题和车辆路径规划问题，掌握了Dijkstra算法、Bellman-Ford算法、模拟退火算法和遗传算法等运筹学方法在实际运输问题中的应用，提高了运筹学实践能力。

5.反思与改进：在实验过程中，我们发现需求和条件的准确描述很重要。

在建模过程中，不光需要理解题目中提供的条件，还需要利用常识和实际情况对模型进行适当的修正和完善。

网络图形最短路径算法分析与研究湛文红【摘要】着重对求网络图上每一对节点之间最短路径的矩阵算法及Floyed算法进行分析与比较,详述它们的功能、原理及异同点,以求在实际应用中合理选择恰当的算法.【期刊名称】《电脑与电信》【年(卷),期】2010(000)007【总页数】4页(P60-62,73)【关键词】最短路径;算法;Dijkstra;逐次逼近;矩阵;Floyed【作者】湛文红【作者单位】首钢工学院,北京,100144【正文语种】中文1.引言目前，在求网络图形最短路径的问题上主要有四种算法，它们是Dijkstra算法、逐次逼近算法、矩阵算法、Floyed算法，它们分别出现在数据结构、运筹学、图论等课程中。

其中前两种算法都是求图上从某一点至另一点的最短路径，而后两种算法是求出网络图上所有节点之间的最短路径。

由于这些算法分别出现不同的学科课程中，因此人们不易将它们进行统一的归纳总结与分析比较。

Dijkstra算法与逐次逼近算法解决的是从某一个节点到另一节点之间的最短路径问题，算法的时间复杂度是O(n2)。

如果想得到每一对节点之间的最短路径，则需要多次调用算法进行计算。

显然，这种方式对于求网络图中每一对节点之间的最短距离就显得过于麻烦。

矩阵算法与Floyed算法较好地解决了这方面的问题，它可以通过算法的一次调用直接计算出网络中每一对节点之间的最短路径值，因而弥补了前两种算法在这方面的不足。

它们通过一个图的权值矩阵求出每两点间的最短路径矩阵。

从图的带权邻接矩阵A=[a(i，j)]n×n开始，逐渐扩展，最终找到所有节点间的最短路径。

矩阵算法与Floyed算法的时间复杂度是O(n3)。

事实上，许多人混淆了后两种算法，认为它们是同一个算法，原因是它们不但功能相同，而且都是采用矩阵运算的形式进行最短路径的求解。

其实，它们在处理方法上还是有很大区别的，在此基础上分析它们的附加功能也是不同的。

本文将着重对这两种算法进行分析与讨论，以求在实际应用中对读者起到参考借鉴的作用。

运筹学试卷及参考答案运筹学试卷一、选择题（每小题2分，共20分）1、下列哪个不是线性规划的标准形式？（） A. min z = 3x1 + 2x2B. max z = -4x1 - 3x2C. s.t. 2x1 - x2 <= 1D. s.t. x1 + x2 >= 0答案：C2、以下哪个是最小生成树的Prim算法？（） A. 按照权值从小到大的顺序选择顶点 B. 按照权值从大到小的顺序选择顶点 C. 按照距离从小到大的顺序选择顶点 D. 按照距离从大到小的顺序选择顶点答案：B3、下列哪个不是网络流模型的典型应用？（） A. 道路交通流量优化 B. 人员部署 C. 最短路径问题 D. 生产计划答案：C4、下列哪个是最小化问题中常用的动态规划解法？（） A. 自顶向下的递推求解 B. 自底向上的递推求解 C. 分治算法 D. 回溯法答案：A5、下列哪个是最大流问题的 Ford-Fulkerson 算法？（） A. 增广路径的寻找采用深度优先搜索 B. 增广路径的寻找采用广度优先搜索 C. 初始流采用最大边的二分法求解 D. 初始流采用最小边的二分法求解答案：B二、简答题（每小题10分，共40分）1、请简述运筹学在现实生活中的应用。

答案：运筹学在现实生活中的应用非常广泛。

例如，线性规划可以用于生产计划、货物运输和资源配置等问题；网络流模型可以用于解决道路交通流量优化、人员部署和生产计划等问题；动态规划可以用于解决最短路径、货物存储和序列安排等问题；图论模型可以用于解决最大流、最短路径和最小生成树等问题。

此外，运筹学还可以用于医疗资源管理、金融风险管理、军事战略规划等领域。

总之，运筹学的理论和方法可以帮助人们更好地解决实际生活中的问题，提高决策的效率和准确性。

2、请简述单纯形法求解线性规划的过程。

答案：单纯形法是一种求解线性规划问题的常用方法。

它通过不断迭代和修改可行解，最终找到最优解。

具体步骤如下： (1) 将线性规划问题转化为标准形式； (2) 根据标准形式构造初始可行基，通常选取一个非基变量，使其取值为零，其余非基变量的取值均为零； (3) 根据目标函数的系数，计算出目标函数值； (4) 通过比较目标函数值和已选取的非基变量的取值，选取最优的非基变量进行迭代； (5) 在迭代过程中，不断修正基变量和非基变量的取值，直到找到最优解或确定无解为止。

Dijkstra算法求解单源最短路径问题一、单源最短路径问题描述给定一个带权有向图G=(V,E),其中每条边的权都是非负数。

给定V中的一个顶点，称为源。

计算从源到所有其他定点的最短路径长度。

这里的路径长度就是指各边权之和。

该问题称为单源最短路径问题（Single-Source Shortest Paths）。

二、Dijkstra算法思想将图G中所有的顶点V分成两个顶点集合S和T。

以v为源点已经确定了最短路径的终点并入S集合中，S初始时只含顶点v, T则是尚未确定到源点v最短路径的顶点集合。

然后每次从T集合中选择S集合点中到T路径最短的那个点，并加入到集合S中，并把这个点从集合T删除。

直到T集合为空为止。

三、算法描述（步骤）1、选一顶点v为源点，并视从源点v出发的所有边为到各顶点的最短路径：①记录从源点v到其它各顶点的路径长度数组dist[],开始时，dist是源点v到顶点i的直接边长度，即dist中记录的是邻接阵的第v行。

②设一个用来记录从源点到其它顶点的路径数组path[]，path中存放路径上第i个顶点的前驱顶点。

2、在上述的最短路径dist[]中选一条最短的，并将其终点（即<v,k>）k加入到集合s中。

3、调整T中各顶点到源点v的最短路径。

因为当顶点k加入到集合s中后，源点v到T中剩余的其它顶点j就又增加了经过顶点k到达j的路径,这条路径可能要比源点v到j原来的最短的还要短。

调整方法是比较dist[k]+g[k,j]与dist[j]，取其中的较小者。

4、再选出一个到源点v路径长度最小的顶点k,从T中删去后加入S中，再回去到第三步，如此重复，直到集合S中的包含图G的所有顶点。

四、算法实现（数据结构）1、算法实现输入：一个大于1的整数n.输出：●一个随机生成的有向图G=（V，E），对于每一条边，有一个非负数字c(u，v)与之相关。

●对于每个顶点v∈V,得到从v0到v的最短路径的长度。

matlab dijkstra算法求解最短路径例题Dijkstra算法是一种用于在带有非负权值的图中找到单源最短路径的算法。

以下是一个用MATLAB实现Dijkstra算法求解最短路径的简单例子：function [shortestDistances, predecessors] = dijkstra(graph, startNode)% 输入参数：% - graph: 表示图的邻接矩阵，graph(i, j) 表示节点i 到节点 j 的权值，如果没有直接连接则为 inf。

% - startNode: 起始节点的索引。

numNodes = size(graph, 1);% 初始化距离数组，表示从起始节点到每个节点的最短距离 shortestDistances = inf(1, numNodes);shortestDistances(startNode) = 0;% 初始化前驱节点数组predecessors = zeros(1, numNodes);% 未访问的节点集合unvisitedNodes = 1:numNodes;while ~isempty(unvisitedNodes)% 选择当前最短距离的节点[~, currentNodeIndex] = min(shortestDistances(unvisitedNodes));currentNode = unvisitedNodes(currentNodeIndex);% 从未访问节点集合中移除当前节点unvisitedNodes(currentNodeIndex) = [];% 更新与当前节点相邻节点的距离for neighbor = unvisitedNodesif graph(currentNode, neighbor) + shortestDistances(currentNode) < shortestDistances(neighbor) shortestDistances(neighbor) = graph(currentNode, neighbor) + shortestDistances(currentNode);predecessors(neighbor) = currentNode;endendendend现在，让我们使用一个简单的例子来测试这个算法：% 创建一个邻接矩阵表示图graph = [0, 2, 0, 4, 0;2, 0, 3, 7, 0;0, 3, 0, 1, 0;4, 7, 1, 0, 5;0, 0, 0, 5, 0];startNode = 1; % 起始节点% 调用Dijkstra算法[shortestDistances, predecessors] = dijkstra(graph, startNode);% 显示结果disp('最短距离：');disp(shortestDistances);disp('前驱节点：');disp(predecessors);这个例子中，graph 表示一个带有权值的图的邻接矩阵，startNode 是起始节点的索引。

Dijkstra( 迪杰斯特拉算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。

主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

Dijkstra 算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。

Dijkstra 算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。

其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。

一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。

初始时，S中仅含有源。

设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。

Dijkstra 算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S 中，同时对数组dist作必要的修改。

一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。

例如，对下图中的有向图，应用Dijkstra 算法计算从源顶点1到其它顶点间最短路径的过程列在下表中。

Dijkstra 算法的迭代过程:主题好好理解上图!以下是具体的实现（C/C++:A ]***************************************2.* About: 有向图的Dijkstra 算法实现3. * Author: Tanky Woo4. * Blog: 6.7. #i nclude8. using n amespace std;9.9. con st i nt maxnum = 100;10. con st i nt maxi nt = 999999;12.13.11. void Dijkstra(i nt n, int v, int *dist, int *prev, int c[max nu m][max num]12. {13. bool s[maxnum]; // 判断是否已存入该点到 S 集合中14. for(i nt i=1; i<=n; ++i15. {16. dist[i] = c[v][i];17. s[i] = 0; // 初始都未用过该点18. if(dist[i] == maxi nt19. prev[i] = 0;20. else21. prev[i] = v;22. }23. dist[v] = 0;24. s[v] = 1;28.29. // 依次将未放入S 集合的结点中，取 dist[] 最小值的结点，放入结合 S 中5. *************************************30. // 一旦S包含了所有V中顶点，dist就记录了从源点到所有其他顶点之间的最短路径长度31.for(i nt i=2; i<=n; ++i32.{33.i nt tmp = maxi nt;34.i nt u = v;35.// 找出当前未使用的点j的dist[j] 最小值36.for(int j=1; j<=n; ++j37.if((!s[j] && dist[j]38.{39.u = j; // u 保存当前邻接点中距离最小的点的号码40.tmp = dist[j];41.}42.s[u] = 1; // 表示u点已存入S集合中43.43.// 更新dist44.for(i nt j=1; j<=n; ++j45.if((!s[j] && c[u][j]46.{47.int newdist = dist[u] + c[u][j];48.if( newdist < dist[j]49.{50.dist[j] = n ewdist;51.prev[j] = u;52.}53.}54.}55.}58.void searchPath(i nt *prev,i nt v, int u59.{60.int que[max nu m];61.i nt tot = 1;62.que[tot] = u;63.tot++;64.int tmp = prev[u];65.while(tmp != v66.{67.que[tot] = tmp;68.tot++;69.tmp = prev[tmp];70.}71.que[tot] = v;72.for(int i=tot; i>=1; --i73.if(i != 174.cout << que[i] << "-> ";75.else76.cout << que[i] << en dl;77.}78.78.int main(79.{80.freopen("input.txt", "r", stdin;81.II各数组都从下标1开始82.i nt dist[max num]; II 表示当前点到源点的最短路径长度83.i nt prev[max nu m]; II 记录当前点的前一个结点记录图的两点间路径长度84.i nt c[max nu m][max nu m]; II87.88. II输入结点数89. cin >> n;90. II输入路径数91. cin >> line;92. i nt p, q, le n; II 输入p, q93.94. II 初始化c[][] 为maxi nt95. for(i nt i=1; i<=n; ++i96. for(i nt j=1; j<=n; ++j97. c[i][j] = maxi nt;98.99. for(i nt i=1; i<=li ne; ++i100. {101. cin >> p >> q >> len;102. if(len < c[p][q] II 有重边103. {104. c[p][q] = le n; II p 指向q 105. c[q][p] = le n; II q指向p，106. }107. }108.109. for(int i=1; i<=n; ++i110. dist[i] = maxi nt;111. for(i nt i=1; i<=n; ++i112. {113. for(i nt j=1; j<=n; ++j 两点及其路径长度这样表示无向图114.printf("%8d", c[i][j];115.prin tf("\n";116.}117.117.Dijkstra(n, 1, dist, prev, c;119.118.// 最短路径长度119.cout << " 源点到最后一个顶点的最短路径长度:"<< dist[ n] << endl;122.120.// 路径121.cout << " 源点到最后一个顶点的路径为："；122.searchPath(prev, 1, n;123.}复制代码输入数据：571 2 101 4 301 5 1002 3 503 5 104 3 204 5 60输出数据：999999 10 999999 30 10010 999999 50 999999 999999 999999 50 999999 20 1030 999999 20 999999 60100 999999 10 60 999999源点到最后一个顶点的最短路径长度: 60 源点到最后一个顶点的路径为: 1 -> 4 -> 3 -> 5。

改进的Dijkstra最短路径算法及其应用研究一、本文概述本文旨在探讨和研究一种改进的Dijkstra最短路径算法，以及其在不同领域的应用。

Dijkstra算法是一种经典的最短路径求解算法，自1956年由荷兰计算机科学家艾兹格·迪杰斯特拉提出以来，已在图论、运筹学、计算机网络等领域得到了广泛应用。

然而，随着数据规模的不断扩大和应用场景的日益复杂，传统的Dijkstra算法在某些情况下表现出了计算效率不高、内存消耗大等问题。

因此，本文致力于通过改进Dijkstra算法，提高其在处理大规模图数据时的性能，并探索其在不同领域中的实际应用。

本文首先将对传统的Dijkstra算法进行详细介绍，分析其基本原理、计算过程以及存在的问题。

在此基础上，提出一种针对大规模图数据的改进Dijkstra算法，包括算法的具体实现步骤、优化策略以及复杂度分析。

接着，本文将通过一系列实验验证改进算法的有效性和性能优势，包括在不同规模图数据上的测试、与其他最短路径算法的比较等。

本文还将探讨改进Dijkstra算法在不同领域的应用。

例如，在交通网络中，可以利用该算法快速找到两点之间的最短路径，为导航、物流等领域提供有力支持；在社交网络分析中，可以利用该算法识别用户之间的最短路径，进而分析社交关系的传播和影响；在图像处理领域，可以利用该算法进行像素间的最短路径计算，实现图像分割、边缘检测等功能。

本文将对改进的Dijkstra最短路径算法进行深入研究和探讨，旨在提高算法性能、拓展应用领域，为相关领域的研究和实践提供有益的参考和借鉴。

二、Dijkstra算法的基本原理与实现Dijkstra算法是一种用于在加权图中查找单源最短路径的算法。

该算法由荷兰计算机科学家艾兹格·迪杰斯特拉在1956年发明，并因此得名。

Dijkstra算法采用贪心策略，逐步找到从源点到其他所有顶点的最短路径。

算法的基本思想是以起始点为中心向外层层扩展，直到扩展到终点为止。

收稿日期:2006-05-24作者简介:章永龙(1976-),男,江西高安人,助教,硕士.文章编号:1006-4869(2006)03-0030-04D ij kstra 最短路径算法优化章永龙(扬州大学信息工程学院,江苏扬州225009)摘 要:传统D ijkstra 算法在求解节点间最短路径时,对已标识节点以外的大量节点进行了计算,从而影响了算法的速度.在对传统D ijkstra 算法分析的基础上,对其进行了优化,优化算法只对最短路径上节点的邻居做了处理,而不涉及到其他节点.因此,在优化算法中计算的节点数大幅减少,提高了算法的速度.关键词:最短路径;D ij kstra 算法;优化中图分类号:TP301.6文献标识码:AOpti m izati on of D ijkstra A lgorith mZ HANG Yong -long(Co llege of I nfor m ation Eng i n neering ,Un i v ersity ofY angzhou ,Y angzhou 225009,Ch i n a)Abst ract :W hen a shortest path bet w een nodes is searched w ith D ij k stra algo rithm ,a l o t of nodes a w ay fro m lagged nodes are invo lved ,so that the effic i e ncy of D ij k stra a l g orithm is lo w.An opti m ization algo -rit h m is presented i n this paper based on analysis of D ijkstra algor ithm .Only these nodes that the ne i g h -bor of nodes i n t h e shortest path are processed ,and other nodes aren t pr ocessed .Therefore ,the number of pr ocessed nodes is large ly reduced in the opti m izati o n a l g orithm,and efficiency o f the opti m izati o n a-l gorith m is i m proved .K ey w ords :the shortest path ;D ij k stra a l g orit h m;opti m ization0 引 言实际生活中的许多问题都可归结于图论中的最短路径问题,如:电子导航、交通旅游、公交出行等.这里的最短路径不仅仅指地理意义上的距离最短,可引申为最少费用、最短时间、延时最短、吞吐量最大等约束条件.传统的最短路径算法,如D ij k stra 算法[1]用来求解图上从任一节点(源点)到其余各节点的最短路径.其时间复杂度为O(N 2);采用邻接矩阵存储网络拓扑结构,需要(N N )的存储空间,随着节点数N 的增大,其计算效率和存储效率越低.针对此问题,提出了D ij k stra 算法的改进[2-5],本文在对传统D ij k stra 算法分析的基础上,对其进行了优化,优化算法只对最短路径上节点的邻居做处理,而不涉及到其他节点.1 传统D ij kstra 算法最短路径问题是指在一个非负权值图中找出两个指定节点间的一条权值和最小的路径.D ij k stra 算法是经典的解决最短路径问题的算法,它可以找出指定节点到其他各个节点间的最短路径,其主要思想是首先从第25卷第3期2006年8月南昌工程学院学报Journal o fN anchang Institute o f T echno l ogy V o.l 25N o .3Aug .2006源点求出长度最短的一条路径,然后通过对路径长度迭代得到从源点到其他各目标节点的最短路径.设w j 是从源点s 到节点j 的最短路径长度;p j 是从s 到j 的最短路径中j 点的前一节点.S 是标识集合;T 是未标识集合;M 是节点集合.d ij 是节点i 到节点j 的距离(i 与j 直接相连,否则d ij = ).算法步骤如下[1]:S tep0:S={s};T=M -S ;w j =d sj (j T ,s 与j 直接相连)或w j = (j T ,s 与j 不直接相连).S tep1:在T 中找到节点i ,使s 到i 的距离最小,并将i 划归到S .(可从与s 直接相连的j 中考虑)若d si =m in j T d s j j 与s 直接相连,则将i 划归到S 中,即S={s ,i},T=T -{i};p i =s .S tep2:修改T 中j 节点的w j 值:w j =m i n j Ti S(w j ,w i +d ij );若w j 值改变,则p j =i .S tep3:选定所有的w j 最小值,并将其划归到S 中:w i =m in j Tw j ;S=S {i };T =T-{i};若|S |=n ,所有节点已标识,则算法终止,否则,转入Step2.由以上算法步骤可知,用标记法实现D ij k stra 算法的主要步骤是从未标记的节点中选择一个权值最小的链路作为下一个转接点,而要选择一个权值最小的链路就必须把所有节点都扫描一遍,在大数量节点的情况下,这往往成为制约算法计算效率的关键因素.2 D ij kstra 算法的优化2.1 算法优化思路通过分析传统D ij k stra 算法的基本思路,传统D ijkstra 算法存在如下两点不足:(1)当从未标记节点集合T 中选定一个节点k 作为转接点后时,需扫描未标记节点集合T 中的节点j 并更新其w j 值,而未标记节点集合T 中往往包含大量与转接节点k 不直接相连的节点i(即d ki = );(2)在未标记节点集合T 中选择一个w 值最小的节点作为下一个转接节点,然而下一个转接节点往往是与标记节点集合S 中的节点直接相连的.基于上述两点不足,本文对传统D ijkstra 算法进行了优化,算法优化思路为:首先从源点s 的邻居集合NB s (与s 直接相连的节点集合)中选择距离最小的邻居节点k 作为转接点,同时将k 划归到标识集合S(初始时,S 为{s}).然后对k 邻居集合与标识集合的差集(NB k -S )中节点j 的w j 值进行更新,从标识集合S 中所有节点的邻居集合的并集与标识集合S 的差集( NB i -S ,i S )中选择一个w k 值最小的节点作为下一个转接点,并划归到标识集合S 中.重复上述过程,直到所有的节点都被标识过,即|S |=n,算法结束.2.2 优化算法描述设NB i 为节点i 的邻居集合;S 为标识集合;w j 是从源点s 到节点j 的最短路径长度;p j 是从s 到j 的最短路径中j 点的前一节点;d ij 是节点i 到节点j 的距离.算法步骤如下:S tep0:初始化S={s};w i =d si (i NB s );否则w i = (i NB s );p i =s .S tep1:若d s k =m in j N Bsd sj ,则S=S {k }.S tep2:修改NB k -S 中的w j 值:w j =m in j NB k-S{w j ,w k +d kj };若w j 值改变,则p j =k .S tep3:选定NB i -S (i S )中的w j 最小值,并将其划归到S 中:w k =m i n j NB i -Si Sw j ;S=S {k };若|S |=n 若,所有节点已标识,则算法终止,否则,转到Step2.用Pascal 程序设计语言描述的优化D ijkstra 算法如下:PROCEDURE Odij k stra(ver num:integer ;star:t i n teger ;VAR Ne i g hbor :ARRAY [vernum ]of se;tVAR W e i g h:t ARRAY [SIZE]of rea;l VAR W:ARRAY [vernum ]of rea l);/*ver num 为网络拓扑的节点数;start 为指定节点;N eighbor 为节点的邻居集合;W eigh t 为链路的权值;W为从指定节点到该节点的最短路径长度;S 为标识集合;P 为节点最短路径上的前一个节点;SIZE =ver -31第3期章永龙:D ij kstra 最短路径算法优化nu m *(ver num +1)/2,在这里采用压缩存储网络拓扑的关联矩阵.*/BEG I NFOR :i =1TO ver num DOBEG I N //初始化W 和PI F (i I N N eighbor[start])THEN BEG I N W [i]:=W eight[k];P[i]:=star;tE ND //k=*i (i-1)/2+start-1(i>=start);k=star*t (start-1)/2+i-1(start>i)ELSE W [i]:=m ax i n ;t //m ax i n t 为计算机允许的最大值E ND ;S:=[start];k :=star;tCS :=[];//S 中所有元素邻居集合的并集与S 的差集,初始为空集.FOR n :=1TO ver nu m -1DOBEG I N//从S 中所有元素邻居集合的并集与S 的差集中选择一个W 值最小的节点CS :=CS+Ne i g hbor[k]-S-[k];FOR :j =1TO LE N (CS)TH E N //LE N ()为求集合中元素个数的函数.BEG I NI F (W [CS[j]]<m in)THEN //m i n :=-1;BEG I N m i n =W [CS[j]];v=;j END;E ND ;k :=CS[v];//k 为选定点S :=S+[k];//将节点k 划归到S 中//更新k 节点的邻居集合中元素的W 值FOR :j =1TO LE N (Ne i g hbor[k])DO BEG I NI F (W [N eighbor[k][j]]>W [k]+W eight[m ])TH E NBEG I N W [N eighbo r[k][j]]:=W [k]+W ei g ht[m ];P[Ne i g hbor[k][j]]:=k ;END;//m =*j (j-1)/2+k-1(j>=k);m =k *(k-1)/2+j-1(k>j)图1 非负权值图E ND ;END;E ND .图1为带权值的无向图G 7,对G 7施行优化D ij k stra 算法,则可得从v 1到其余各节点的最短路径,以及运算过程中的选定点、w 值、邻居集合及邻居集合节点并集与S 的差集的变化状况,如表1所示.3 算法分析传统D ij k stra 算法基于广度优先的搜索策略,从指定节点出发,通过权值迭代遍历所有其他节点后,最后得到从指定节点到其他各节点的最短路径树.它采用线性数组结构存储其关联矩阵,在提取最短路径节点时需要访问所有的未标记节点,算法的运行时间为O(N 2);而本文提出的优化算法在更新最短路径值与选择最短路径值最小的节点时,仅仅涉及到节点的邻居集合及已标识集合中所有节点的邻居集合与已标识集合的差集,其运行时间取决于转接点的邻居集合的元素数量多少32南昌工程学院学报2006年(而该数量值往往小于未标识集合中的元素个数).当网络拓扑结构图具有的节点数N 较大且其关联矩阵为一个稀疏矩阵时,相对传统D ij k stra 算法,优化算法大大减少了计算次数与比较次数,在一定程度上提高了运算速度.表1 优化的D ij kstra 算法求解v 1到其他各节点最短路径的过程迭代次数v 1v 2v 3v 4v 5v 6v 7选定点w i NB iSNB i -SUNB i -S (i S )00251 v 1w 1=0(v 2,v 3,v 4)(v 1)125① v 4w 4=1(v 1,v 2,v 3,v 5)(v 1,v 4)(v 2,v 3,v 5)(v 2,v 3,v 5)2②42v 2w 2=2(v 1,v 3,v 4)(v 1,v 2,v 4)(v 3)(v 3,v 5)34②v 5w 5=2(v 3,v 4,v 6,v 7)(v 1,v 2,v 4,v 5)(v 3,v 6,v 7)(v 3,v 6,v 7)4③34v 3w 3=3(v 1,v 2,v 4,v 5,v 6)(v 1,v 2,v 3,v 4,v 5)(v 6)(v 6,v 7)5③4v 6w 6=3(v 3,v 5,v 7)(v 1,v 2,v 3,v 4,v 5,v 6)(v 7)(v 7)6④v 7w 7=4(v 5,v 6)(v 1,v 2,v 3,v 4,v 5,v 6,v 7)5 结束语在分析传统D ijkstra 算法的基础上,针对传统D ijkstra 算法存在的两点不足之处,对其进行了优化处理.当网络的规模较大及其关联矩阵为一个稀疏矩阵时,本文提出的优化算法,与传统D ij k stra 算法相比,能大大减少了计算次数及比较次数,提高了运算效率.参考文献:[1]石文孝.通信网理论基础[M ].吉林:吉林大学出版社,2001.[2]李 峰,张建中.网络最短路径算法的改进及实现[J].厦门大学学报(自然科学版),2005,(44):40-42[3]乐阳等.D ij kstra 最短路径算法的一种高效率实现.武汉测绘科技大学学报,1999,24(3):62:64[4]蒲在毅,任建军.用标号法实现单源最短路径问题的迪杰斯特(d ij kstra)算法[J].四川师范学院学报(自然科学版),2003,(24):52-54[5]靳晓强.双向D ijkstra 算法及中间链表加速方法[J].计算机仿真,2004,(21):93-95(上接第14页)(2)为减弱爆破地震波向洞顶传播,布设减震孔;(3)采用微差爆破,寻找最优间隔时间,使爆破震动强度最小;(4)优化爆破参数,降低单位炸药耗量,不耦合装药,限制一次爆破最大起爆药量.通过采取有效的降低爆破地震波的措施,既节约了工程投资,又保证了工程施工进度,为按期完成本工程奠定了良好的基础,同时,为类似工程的施工提供了可借鉴的依据.参考文献:[1]李存国,王润生,王 玲.爆破地震效应临近建筑物的影响[J].云南冶金,2006,(3):10-17.[2]张 丹,段恒建,曾福洪.分段爆破地震强度的试验研究[J].爆炸与冲击,2006,(3):279-283.[3]G B6722 2003,爆破安全规程[S].2003.[4]吴 立,陈建平,舒家华.论爆破的地震效应[J].爆炸器材,1999,(5):24-27.33第3期章永龙:D ij kstra 最短路径算法优化。