第19次课 运输路线选择（最优、最短问题）

第7章运输决策第19次课运输路线选择（最优、最短问题）3知识点1最优路线问题-破圈法知识点2最短路径问题-D算法（Dijkstra算法）主要知识点（重难点）4问题思考学习启示1.什么是“三段式”教学模式（方法）？2.什么是“三段式”学习模式（方法）？写写画画：进行数字计算，数字如何计算得来？（关键：步骤一，一通百通）2.

画图，画出示意图、位置图。7.2运输路线选择（最优、最短问题）

运输路线的选择影响到运输设备和人员的利用，正确地确定合理的运输路线可以降低运输成本，因此运输路线的确定是运输决策的一个重要领域。7.2运输路线选择（最优、最短问题）

7.2.1最优路线问题

对分离的、单个始发点和终点的网络运输路线选择问题，最简单和直观的方法是最短路线法。网络图G由节点和线组成，点与点之间由线连接，线代表点与点之间运行的成本（距离、时间或时间和距离加权的组合）。

初始，除始发点外，所有节点都被认为是未解的，即均未确定是否在选定的运输路线上。始发点作为已解的点，计算从原点开始。7.2运输路线选择（最优、最短问题）

7.2.1最优路线问题

1.破圈法

破圈法的求解步骤：

（1）在G中任取一个圈，从圈中去掉一条权值最大的边（如果有两条或两条以上的边都是权最大的边，则任意去掉其中一条）；

（2）在余下的图中重复上述步骤，直至剩余的图中不再含圈为止，此时得到的路线即为最短路线（或费用最省路线）。如果用点表示研究对象，用边表示对象之间的联系，则图G可以定义为点和边的集合，记作G=(V,E)

式中，V是点的集合或顶点的集合，E是边的集合。注意上面定义的图G区别于几何学中的图。在几何学中，图中的点的位置、线的长度和斜率都十分重要，而这里只关心图中有多少个点以及哪些点之间有线相连。求最短路径例题：用破圈法求最短路径图7‑2（1）原路径图步骤一：从图7-2中任取一回路，如为DETD，去掉最大边ET，得N1。步骤二：从N1中任取一回路，如为BDEB，去掉最大边BD，得N2。依此类推，详细过程如图7-2所示。图7-2（2）改进步骤图

7.2运输路线选择（最优、最短问题）

7.2.2最短路径问题

最短路径问题，是求从指定的起点vs至终点vt的多条路径中总权值最小的路径。比如，如图7-3所示，从v1至v8存在多条路，其中总权值最小的路径成为最短路径。

寻找最短路径常用的方法为Dijkstra算法，简称D算法（也称为双标号法）。该方法可用于求解指定的两点vs（起点）和vt（终点）间的最短路线和指定起点vs到其余各点的最短路径。该算法是目前求解权值非负的网络图的最短路问题的最优方法。

D算法的基本原理：若序列（vs,v1,v2,.......,vi-1,vi）是从起点vs到终点vi的最短路，则序列（vs,v1,v2,.......,vi-1,vi）必为vs到vi-1的最短路。7.2运输路线选择（最优、最短问题）

7.2.2最短路径问题

D算法的求解方法：

对所有的点赋予两种标号，一种为T标号，T标号即临时性标号（TemporaryLabel）用T（vi）表示；另一种为P标号，P标号即永久性标号（PermanentLabel），用P（vi）表示。当赋予某点vi一个标号值，是表示从vs至vi的可能的最短路的总权值的上界，是一种暂时性的赋值，所有未赋予P标号的点均有一个T标号；当赋予某点vi一个P标号值时，表示从起点vs至vi的最短路的总权值已求出，为P（vi），此后，vi的标号不再改变。算法的每一步都会选择一个T标号的点，将其改为P标号。当终点vt得到P标号值时，全部计算结束。

对于有n个顶点的图，最多经过（n-1）步计算，便可以得到从起点至终点和其余各点的最短路。另外，为了方便找出最短路线，T标号和P标号均分为两部分，前面的值表示最短路的总权值，后面是指针，表示最短路的路线，用L（vi）表示。7.2运输路线选择（最优、最短问题）

7.2.2最短路径问题

D算法的求解步骤：（1）初始化：赋予起点vs一个P的标号，即令P（vs）=0，并给予其最短路线的指针L（vs），令L（vs）=0；赋予除vs之外的其他所有点一个T值，令T（vi）=∞，L（vi）=0。（2）对于最新的P标号点vi，考查满足如下条件的点vj：（vi,vj）∈A（A是所有弧的集合），且vj为T标号点vi，wij为弧（vi，vj）的权值。对于vj如下计算和处理：如果T（vj）>P（vi）+wij，令T（vj）=P（vi）+wij；L（vj）=vj，否则维持T（vj）和L（vj）不变。考查起点vs至vj的最短路线是否经过P标点vi，如果经过vi的路线比原来的路线更短，则用经过vi的路线取代原来的路线。其中，L（vj）=vi表示vs至vj的可能最短路线经过vi，最后可通过这个指针反向追踪起点至某点的最短路线。7.2运输路线选择（最优、最短问题）

7.2.2最短路径问题

D算法的求解步骤：（3）比较所有仍为T标号的点的T值，将T值最小者改为P标号，即：P（vi）=T（vi），其中T（vi）=min{T（vj）|vj为T标号点}如果终点vt已标号，或所有仍为T标号的点的T值为∞，则算法结束，否则，转回步骤（2）。7.2运输路线选择（最优、最短问题）

7.2.2最短路径问题

从D算法中我们可以得出结论：（1）D算法可以求出任何两点之间的最短路，只要将两点分别看作路线的起点及终点，然后标号即可。（2）两点之间的最短路线可能不是唯一的。（3）D算法的适用条件是弧的权值非负，且问题是求最小值，对于最大值问题和弧权值为负的情况，该算法不适用。本课小结本课讲授知识点，主要包括：知识点1最优路线问题-破圈法知识点2最短路径问题-D算法（Dijkstra算法）26复习思考题一、简答题1.求解最优路线问题，简述破圈法的求解步骤？2.求解最短路径问题，简述D算法的求解步骤？