最短路问题的多种解法

最短路问题的多种解法摘要：本文研究的是用动态规划的方法、Dijkstra算法以及结合求最小树的Kruskal算法和破圈运算，给出求一类最短路问题的一种简单算法来解决最短路问题，通过对问题的求解，分析这三种方法各自的要求以及特点。关键词：最短路问题；动态规划；Dijkstra算法；Kruskal算法；破圈运算Different

Methods

of

the

Shortest

Ways

ProblemsAbstract:The

thesis

focus

on

finding

an

easy

solution

to

solvethe

shortest

way

problems

by

using

dynamic

programming

method,Dijkstra

algorithm

and

the

minium

tree

Kruskal

algorithm

andbroken

ring

operator.It

will

analyze

the

requirements

and

characteristics

of

the

three

ways

by

solving

problemsKeywords:theshortestwayproblems；dynamicprogrammingmethod；Dijkstraalgorithm；Kruskalalgorithm；brokenringoperator最短路问题是经济管理中经常遇到的问题，如煤气管道铺设，交通运输等等，求解最短路的算法有很多种，本文中就应用动态规划的方法,，Dijkstra算法以及结合求最小树的Kruskal算法和破圈运算，给出求一类最短路问题的一种简单算法来解决遇到的最短路问题。问题的提出对于煤气管道铺设问题，我们把它归结为图1所表示的网络，联结各点的线段上的数字表示它们之间的弧长。求A点到E点的最短路程。5533134123524115213图1问题的分析图1可视为一定阶段最短路问题的标准模型，图1可划分为4个阶段，即n=4.从A点出发到B点为第一阶段，这时有3个选择，一是到，一是到，一是到，假设选择到，那么就是第1阶段决策的结果，它即是这一阶段的路线的终点，又是下一个阶段路线的始点。在第2阶段，再从出发，对于点，有一个可供选择的终点集合,假设选择由至为第2阶段的决策，那么就是第2阶段的终点，同时又是第3阶段的始点，以此类推。模型的建立与求解方法一：动态规划法根据动态规划的正向思维法，从A点开始计算逐步移至E点设表示第k个阶段的状态变量，表示第k个阶段的决策，表示第k个阶段到起点A的最短路那么：，，，这其中当时，；时，；，；当时，；时，；当时，；时，；时，；当时，；综上，可得此问题的最短路为：，此最短路的长度为8方法二：Dijkstra算法I表示已标号的点的集合，J表示未标号点的集合，M表示始点标号终点未标号的边的集合，一次记A点到点分别为1,2,3……8,9，记点E为u点，表示i点到j点的最短路的长度，表示i点到j点的距离。给起点A的标号为(0，s)，；；所以：那么：给边中未标号的点标以(1,1)(3)，；所以那么：给边中未标号的点标以(2,1)(4)，；；所以；；那么：；给边中未标号的点标以(3，1)；给边中未标号的点标以(3，3)；(5)，；；所以：；；；；那么：给边中未标号的点标以(4，5)(6)，；；所以：；那么；给边中未标号的点标以(5，3)；给边中未标号的点标以(5，5)；(7)，；；所以：；那么：；给边中未标号的点标以(8，5)；给边中未标号的点标以(8，7)；综上，可以从标号中找到最短路为：，最短距离为8方法三：结合求最小树的Kruskal算法和破圈运算产生的一种新型算法算法步骤：开始把边按权的大小从小到大排列并标号；权最小的边标为1号，权次小的标为2号，以此类推，将剩余的边分别标为3号、4号、....〔权相同的边标号相同〕记i=1；选取i号边，观察从A到E点是否存在通路；假设没有路，置i=i+1，转第一步；否那么，转第四步；假设仅有一条路，停止。这条路即为所求；否那么，转第五步；破除所有的圈，转第四步。求解文中例题：按照以上步骤，如下图：111111111111222111111122233331111122233说明：在圈中，去掉最长边；在圈中，去掉最长边；在圈中，去掉最长边。至此得到最短路为：，最短路程为8结论对于动态规划法：这种方法的解题步骤为：从最后一个阶段开始，从始点向终点方向逐阶段顺推，找出各点到终点的最短路，当逆推到始点时，也就找到了从始点到终点的全过程的最短路。它的最大特点在于它不仅可求出全过程的最短路，还可求出图上任一点到终点的最短路。但是此种方法解决的问题也有其局限性。它要求最短路问题能明晰地分成几个阶段，且阶段间不交叉，即每一条路都要经过相同的阶段，有固定的步骤。对于Dijkstra算法：此算法的特点在于不仅能找到始点到终点的最短路及距离，还能根据各点的标点找到始点到各点的最短路及距离。而且对于一般的每条弧的赋权数Cij≥0的最短路问题它都能求解。对于新型算法：简单易懂，容易操作，直观性很强。而且简便了运算。三种方法相比拟可知：可知三种解答方法结果一致。最短路问题的解法各有其优点，动态规划的的方法不仅可求出全过程的最短路，还可同时求出图上任一点到终点的最短路；Dijkstra算法不仅能找到始点到终点的最短路及距离，还能根据各点的标点找到始点到各点的最短路及距离。相比拟而言Dijkstra算法适用范围更广些。动态规划法解决例题要用15次加法运算,以及8次比拟运算，而用新型方法所给算法只需3次迭代，3次破圈运算。由此可知，新型算法在算法复杂性上要比动态规划要好，在广泛性上，Dijkstra算要比动态规划要广。参考文献[1]卢开澄.图论及其应用[M].北京：清华大学出版社,1981.[2]韩伯棠.管理运筹学[M].北京：高等教