题目网络的最短路径算法研究学院数学与信息工程学院
专业
班级
学号
学生姓名
指导教师
完成日期
摘要
在现实生活中最短路径的运用非常多，算法也很多，最短路径分析是网络分析最基本的功能之一。近年来，随着网络的不断发展，网络中的最短路径问题具有重要的理论意义和应用价值。当网络规模很大时,求解更加复杂,计算时间和所需的存储空间也大大的增加。本文讨论网络的最短路径算法及其现实问题，其中典型的最短路径算法是Dijkstra算法。Dijkstra算法是一种著名的最短路径算法, 它可为任一源节点找出与其它所有节点的最短路径。Dijkstra 算法是目前公认的较好的最短路径算法，是计算机科学与地理信息科学等领域研究的热点。Dijkstra算法将网络结点分为未标记结点、临时标记结点和永久标记结点，网络中所有结点先初始化为未标记结点，在搜索过程中和最短路径结点相连通的结点为临时标记结点，每次循环都是从临时标记结点中搜索距源点路径长度最短的结点作为永久标记结点，直至找到目标结点或所有结点都成为永久标记结点才结束，这样临时结点无序地存储在无序表中，每次搜索都要遍历到表中的所有临时结点，这样势必会带来很大的计算量，给系统的应用也会带来很大不便．提高算法的效率一方面可以通过对临时结点表建立索引，加快检索速度；另一方面即减少搜索的临时结点的数量，那么效率就可以大幅度的提高。在寻径时要分步由源节点开始一步步地向相邻节点扩展, 直到包含所有网络节点为止。针对如何利用Dijkstra算法来高效地查找图中任意两点之间的最短路径这一问题，应用图中各结点的出入度来简化查找两结点之间的最短路径，再利用以求出的两点之间的最短路径快速获得结点之间的最大路径。主要特点是以起始点为中心向外层扩展，直到扩展到终点为止。通过对Dijkstra算法的了解，能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。本文接着简单介绍了Floyd算法，又称弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。是一种动态规划算法，稠密图效果最佳，边权可正可负，此算法简单有效，容易理解，可以算出任意两个节点之间的最短距离，代码编写简单。然后运用Matlab来实现了这两种经典的算法。最后将两种算法进行了一些对比，得出结论：Dijkstra算法可为任一源节点找出与其它所有节点的最短路径，当网络问题规模增大时，Dijkstra算法会使计算时间复杂度不断增大。而Floyd算法是一种动态算法，此算法简单，容易理解，可以算出任意两个节点之间的最短距离，但是Floyd算法计算最短路径时时间复杂比较高，不适合计算大量数
据。
关键词最短路径；Dijkstra算法；Floyd算法；Matlab
Abstract
The shortest path in real life use of very large, algorithms are also many, the shortest path analysis is the most basic functions of the network analysis.In recent years, as the network continues to develop, the shortest path network has important theoretical significance and application value.When the network size is large, solving the more complex, computation time and required storage space is greatly increased.This article discusses the network's shortest path algorithm and its practical problems, which the typical shortest path algorithm is Dijkstra algorithm.Dijkstra algorithm is a well-known shortest path algorithm, it can be any source node to all other nodes to find the shortest path. Dijkstra algorithm is better recognized as the shortest path algorithm, a computer science and geographic information science and other fields of research.Dijkstra algorithm is divided into a network node is not marked node, the temporary tag and permanently mark nodes nodes, all nodes in the network is initialized to the first unmarked node in the search process and the shortest path through the nodes connected Results point to the temporary tag nodes, each loop nodes are from the temporary tag to search for the shortest path length from the source node node as a permanent marker until you find the destination node or all nodes become permanently labeled nodes Until the end, so that the temporary node to store in disorderly disorderly table, each search must traverse to the table all temporary nodes, so that would certainly bring a great amount of computation, the application will be brought to the system To great inconvenience. Improve the efficiency of the algorithm one node through the temporary table indexing and the retrieval speed; the other hand, a reduction of the search the number of temporary nodes, then the efficiency can dramatically improve. In the routing step when starting from the source node to adjacent nodes, step by step expansion of the network until it contains all the node.For how to use the Dijkstra algorithm to efficiently find the map the shortest path between any two points in this problem, apply the map in and out degree of each node to simplify the two find the shortest path between nodes, and then out of use in order to the shortest path between two points quickly get the maximum path between nodes. Main features is the starting point for the center to the outer expansion, until the extension to the end up. Dijkstra algorithm on the understanding, can come up with the optimal solution of the shortest path, but
because it traverses a lot of computing nodes, so the efficiency is low.This paper then introduces the Floyd algorithm, also known as Floyd algorithm, insertion point method is given for finding a weighted graph algorithm shortest path between vertices. Is a dynamic programming algorithm, dense graph the best, the right side can be positive or negative, this algorithm is simple and effective, easy to understand, you can calculate any of the shortest distance between two nodes, the code to write simple. Then use Matlab to achieve these two classical algorithms. Finally, some comparison of two algorithms, to a conclusion:Dijkstra algorithm can be any source node to all other nodes to find the shortest path problem when the network size increases, Dijkstra algorithm will calculate the time complexity is increasing. The Floyd algorithm is a dynamic algorithm, this algorithm is simple, easy to understand, you can calculate any of the shortest distance between two nodes, but the Floyd shortest path algorithm to calculate the time complexity is relatively high, not suitable for large data calculations.
Keywords
Shortest path; Dijkstra algorithm; Floyd algorithm; Matlab
目录
1. 引言 (1)
2．Dijkstra算法 (2)
2.1 Dijkstra算法概述 (2)
2.2算法描述及基本方法 (3)
3．Dijkstra算法案例分析 (6)
案例1：基于Dijkstra算法在物流配送中的应用 (6)
案例2：货币兑换 (8)
案例3：军事运输 (8)
4．求解最短路的Floyd算法 (9)
5．运用Matlab来进行求解 (10)
5.1．运用Matlab程序实现Dijkstra算法 (10)
5.2．用Matlab程序实现Floyd算法 (11)
6．结束语 (12)
参考文献 (14)
谢词 (15)
网络的最短路径算法研究
Network shortest path algorithm
1.引言
最短路径问题是网络分析中最基本的组合优化问题之一，在公交线网规划中应用十分广泛。尤其是随着我国经济的飞速发展和城市化进程的加快，城市轨道交通已进入大发展时期。轨道交通的衔接规划是基于轨道交通的发展，对其沿线的交通资源配置优化和整合，达到客运交通支援最优化。其中很重要的任务就是对现有城市公交线网进行重新规划。然而在实际进行公交线网优化设计中，最短路径模型往往无法直接应用。路径选择算法一直是计算机网络中的一个重要研究课题。它直接关系到网络效率、传输延迟和吞吐量等主要技术性能指标。
随着社会的不断进步，最短路径算法在人们的日常生活显得越来越重要。比如，每天开车去上班，应该选择哪条公路才能使自己到公司的费用最低、时间最少、这是最短路径的问题；在网络路径中，怎样选择最优的路由路径，这也是最短路径问题；在交通旅游、城市规划以及电网架设中怎样使其耗费的资金最少，这还是最短路径问题。由此可见对最短路径问题的研究是非常有意义的。
最短路径这一重要问题早在20世纪初就已经得到人们的高度重视。当时也有许多科学家研究这一重要问题的求解方法。但直到1959年荷兰计算机科学家Dijkstra（迪杰斯特拉）才给出这一问题求解的基本思想,并给出了算法。后来这个算法就成了众所周知的Dijkstra 算法，也成为了一代经典。当时的Dijkstra提出的这一算法主要解决的问题是从固定的一个点到其他各点的最短路径问题。但是在实际生活中往往要求解决的不只是固定一点到其他点的最短路径，而是要求计算出任意两点之间的最短距离。
2. Dijkstra算法
2.1 Dijkstra算法概述
Dijkstra算法是由荷兰计算机科学家狄克斯特拉于1929年提出的，因此又叫狄克斯特拉算
法。是一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。
其原理是每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没有扩展过的点，所以这个点的距离永远不会在被改变，因而保证了算法的正确性。不过根据这个原理，用Dijkstra 求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能破坏已经更新的点距离不会改变的性质。
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra 算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。Dijkstra 一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE 表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。定义：自然选择总是倾向于使动物最有效地传递其基因，因而也是最有效地从事各种活动，包括使它们活动时的时间分配和能量利用达到最佳状态。
Dijkstra 算法是一种著名的最短路径算法, 它可为任一源节点找出与其它所有节点的最短路径。在寻径时要分步由源节点开始一步步地向相邻节点扩展, 直到包含所有网络节点为止。其方法是：建立一个节点集N, 开始时N 只包含源节点, 每算一步N 中增加一个相邻节点, 直到所有网络节点均进入N 中后才结束计算。算法步骤如下： （1）初始化处理, 定义数组N 它只包含源节点S, {}N S =, 并定义距离
()(,)D v L s v =， v 为非源节点中的其它某个节点, 该距离为节点v 到源节点s 的链路长度, 若v 与s 直接相邻, 则()D v 有一确定值, 若v 与s 不直接相邻, 则()D v =∞。
（2）不断求出数组N 以外的结点F ，使距离()D F 最小，并将结点F 加入原来的数组，对于N 以外的各节点按下式()D V :
()min[(),()(,)]D v D V D F L F V ←+，当()(,)()D F L F V D V +<,则以
()(,D F L F V +代入原()D V ,否则维持原值不变，这一过程重复至所有节点均包含在数组N 内为止。
Dijkstra 算法思想为：设(,)G V E =是一个带权有向图，把图中顶点集合V 分成两组，第一组为已求出最短路径的顶点集合（用S 表示，初始时S 中只有一个源点，以后每求得一条最短路径 , 就将 加入到集合S 中，直到全部顶点都加入到S 中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U 表示），按最短路径长度的递增次序依次
把第二组的顶点加入S 中。在加入的过程中，总保持从源点v 到S 中各顶点的最短路径长度不大于从源点v 到U 中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S 中的顶点的距离就是从v 到此顶点的最短路径长度，U 中的顶点的距离，是从v 到此顶点只包括S 中的顶点为中间顶点的当前最短路径长度。
2.2. 算法描述及基本方法
Dijksta 算法的原理
设(,,)D V A w = 是一个非负权网络, 12(,,...,)n V v v v = 。则D 中(,)i j v v A ∈ 最短路的长满足方程:
10u =
min()(2,3,...,)j k kj u u w j n =+= (1)
如果D 中从顶点1v 到其余各顶点最短路的长按照大小排序为:
12...i i in u u u ≤≤≤
这里11i = , 10i u =，则由(1) 式有
min{}ij ik ikij k j
u u w ≠=+ min{min{},min{}}ik ikij ik ikij k j k j
u w u w <>=++ (2,3,...,)j n = 当k j > 时, ik ij u u ≥,且0ikij w ≥,从而
ij ik ikij u u w ≤+
即min{}ij ik ikij k j
u u w >≤+ 所以min{}ij ik ikij k j
u u w <=+ 容易证明:
10i u =
min{}ij ik ikij k j
u u w <=+的解12(,,...,)i i in u u u 中的ij u 是 D 中最短(,)i j u u 路的长度, 1,2,...,j n =。
这就是Dijkstra 的理论证明。
目前最短路径问题的最成熟算法是Dijkstra 算法。Dijkstra 算法的思想是：先给赋权图的每
一顶点记1个数(称标号)，临时标号(T 标号)或固定标号(P 标号)。T 标号表示从始点到这一点还没有寻找到最短路径；P 标号则表示从始点到这一点已寻找到最短路径。计算的每一步是把某个点的T 标号变成P 标号。这样一旦终点得到P 标号，计算就停止。若寻求从始点到每一点的最短路径，则最多经过1N -步计算，计算就要停止(N 是G 的顶点数)。
算法步骤如下：
stepl ：给始点1v 标上P 标号1()0d v =，给其他各点标上T 标号1()(2,3,...,)j j d v l j N ==； step2：在所有T 标号中取出最小者，比如：00()j ij d v l =，则把该点的T 标号改为P 标号； step3：重新计算具有T 标号的其他各点T 标号：选 点的T 标号与()k j d v l +中较小者作为j v 的新标号。
一般情况下，设P={j v |j v 具有P 标号}，T={j v |j v 具有T 标号}，
\V P (V 为图G 的顶点集合)。令
()min{()}k j v T
d v d v ∈=。 为点的P 标号，于是0k v P ∈把\{}k T v 中的点j v 的T 标号修改为
min{(),()}j k k d v d v l +
step4：重复上述步骤，直到N v P ∈，这时()N d v 是从1v 到N v 的最短路径。
设(,)G P L =是有限图，如果对()L G 中任一条边l ，都规定一个实数(1)w 附在其上，则称G 为有限权图，称(1)w 为边l 的权。规定()0w uu =(其中()u P G ∈）, ()w uv =∞（其中()uv L G ∈）。
如图下图1，()6w AB =，()0w AA =，()w AC =∞，()10w AD =。
图 1边权图
例如，一个描述各城市之间的铁路交通图，图2中的每一边可以用这条边所表示的铁路长度为其权，于是这个铁路交通图就是权图。这个铁路交通图，也可以用每条边所代表的铁路修建费用为其权，这个铁路交通图又是一个权图。
可以想到，在一个权图G 中，任给两点u ，v ，从u 到v 可能有好几条路，在这些路中，求出所带的权达到最小那条路是有实际意义的，这就是图中求最短路问题。这条最短路所带的权称为u 到v 的距离，记为(,)d u v 。
显然两点间的最短路一定简单路，所以在网络中找最短路只需在简单路中找。
如上图4.1.6中，A 到D 的所有简单路有：（1）(,,,)A F E D 长度为6，（2）
(,,,,,)A F E B C D 长度为13，（3）(,,,)A F C D 长度为3，（4）(,,,,,)A F C B E D 长度为14，（5）(,)A D 长度为10，（6）(,,,)A B E D 长度为13，（7）(,,,,,)A B E F C D 长度为14，（8）(,,,)A B C D 长度为12，（9）(,,,,,)A B C F E D 长度为17。所以A 到D 的最短路为(,,,)A F C D ；A 到D 的距离为3。
图 2各城市之间的铁路交通图
上述求最短路的方法是枚举法，对于大的复杂的图，这种方法显然是不现实的，也不易在计算机上实现。需要寻找合适的算法。再例如假设图2表示的是一个公路网，节点表示货车可以停靠的站点，边上的权表示两个站点之间的距离。那么，货车从S 点出发到达T 点，如何选择行驶路线，使所经过的路程最短？
1959年，Dijkstra 给出了一个在权图中求其任意两点间最短路的算法。在介绍该算法之前我们先讨论有限权图中点到点集之间的距离：设G 是有限权图，()S P G ∈，0u S ∈，'S P S =-，定义u 0到'S 的距离
00'
(,')min{(,)}v S d u S d u v ∈= 实现上述距离的路称为u 0到'S 的最短路。不难看出上述点到点集距离的定义等价于
00'
(,')min{(,)(,)}u S v S d u S d u u w u v ∈∈=+ 例如在上图1中，令{,,}S A B F =，则'{,,}S C D E =，求(,')d A S ？
设0u A =，取u A =，则w(AC)=∞，()10w AC =，()w AE =∞，
''
min{()()}min{()}10v S v S d AA w Av w Av ∈∈+== 取u B =，则()6d AB =，()5w BC =，()w BD =∞，()4w BE =，
'
min{()()}6410v S d AB w Bv ∈+=+=； 取u B =，则()1d AF =，()1w FC =，()w FD =∞，()4w FE =，
'
min{()()}112v S d AF w Fv ∈+=+=； 因而(,')2d A S =，A 到'S 的最短路为(,,)A F C 。当然这里的()6d AB =，()1d AF =是预先计算的，没有在这里计算。为实现这种预先的计算，必须进行迭代。Dijkstra 算法恰是这种思想。即不是孤立地求有限权图中两点间的距离与最短路，而是统筹考虑，算法终止时是一次性地求出某一点到所有其余各点之间的距离与最短路。
3. Dijkstra 算法案例分析
案例1：基于Dijkstra 算法在物流配送中的应用
电子商务是依托于互联网和信息技术的一种新型商务活动。目前，我国的电子商务发展势头迅猛，已经成为国民经济中的重要组成部分。相对于新生的电子商务来说，物流配送出现得
比较早，但是真正把它当作一个完整的系统来研究还是在20世纪50年代。
在电子商务尤其是B2C业务开展之初，国内还没有一家物流公司具有电子商务的配送经验，各个电子商务公司之恩那个求助于具有国内最大覆盖的中国邮政速递公司，EMS但是在经历一段时间之后，EMS由于自身体制的僵化分割，管理无法协调，服务水平无法提高，费用居高不下对很多问题都是心有余而力不足，无法满足电子商务发展的快速要求。
鉴于此种情景，国内许多大型电子商务公司都在积极地寻找出路，有的自己投资组建配送队伍，但是要将自己的网点覆盖全国实在太难，投资太大有的积极寻找新近进人电子商务配送领域的配送公司，但是后者的实力和发展迅速着实无法满足需求，也有助传统的第三方物流公司，在电子商务覆盖需求如此广大，服务环节如此复杂，业务特点往往品种多、数量少、利润低等实际问题面前，传统的物流公司往往是望而却步。
商品配送成本过高电子商务公司的配送不仅面向批发商和零售商，还要直接面对大批的最终消费者，况且电子商务不受时间、地域的限制，因此比较难形成集中的、有规模的配送流量，由此造成配送任务复杂而琐碎，成本居高不下，降低配送服务价格，就要解决电子商务公司与物流配送企业之间在配送服务价格之间的矛盾，需要双方的共同努力。
一方面电子商务公司考虑配送成本，尽量网上销售的商品控制在与物流企业协议确定的配送范围之内，并尽量使之相对集中且形成规模。
另一方面，物流配送企业应积极协作，选择最短路径作为配送路径降低配送成本，并加强管理，开源节流，降低物流成本和配送服务的价格，同时还尽可能与电子商务公司建立长期稳定的协作关系，这样做有利于物流企业制定长远投资和服务计划，有利于加快新的物流配送技术的应用，加大配送渠道和设施的建设力度，最终有利于加快实现物流配送系统的信息化、自动化、网络化和智能化。从长远看，有利于持续稳定地降低物流配送的成本和价格。
目前关于物流配送的问题已经有很多方法，大致可分为定性和定量两大类。定性方法是指凭个人或集体的经验来做出决策，它的执行步骤一般是先根据经验评价指标对各待选中心利用评价指标进行优劣性检验，根据检验结果做出决策。定性方法的优点是注重历史经验。简单易行，其缺点是容易犯经验主义和主观主义的错误，并且当可选地点较多时不易做出理想的决策。定量方法是根据各种约束条件和所达到的目标，把选址问题转化为函数，再利用合适的算法进行求解，求出最符合条件的解即具体的地点作为配送路径，基于最短距离改进问题的算法的物流配。
采用图论中的最短路径算法来建立物流配送路径选择模型，它的主要思想是从代表两个顶点的距离开始，每次插入一个顶点比较任意两点之间的已知最短路径和插入顶点作为中间顶点
时，得到的最后的权矩阵就反映了所有顶点间的最短距离信息。最短距离者作为费用最小者，即最佳的选址位置。
案例2：货币兑换
若干个货币兑换点在我们的城市中工作着。每个兑换点只能进行两种指定货币的兑换。不同兑换点兑换的货币有可能相同。每个兑换点有它自己的兑换汇率，货币A 到货币B 的汇率表示要多少单位的货币B 才能兑换到一个单位的货币A 。当然货币兑换要支付一定量的中转费。例如，如果你想将100美元兑换成俄元，汇率是29.75，中转费为0.39，那么你会兑换到(1000.39)29.752963.3975-?=俄元。
城市中流通着(100)N N ≤类货币，用数字1至N 标号表示。每个货币兑换点用6个数字来描述：整数A 和B 是兑换货币的编号，实数RAB ，CAB 表示A 兑换成B 的汇率和中转费用，RBA ，CBA 表示B 兑换成A 的汇率和中转费用。
Nick 有一些第S 类货币，他想在若干次交换后增加他的资金，当然这些资金最终仍是第S 类货币。请你告诉他该想法能否实现。
图构：
将N 种货币看成N 个顶点，将每个兑换点转化为两条有向边。根据兑换公式，目前从A 货币兑换到B 货币的汇率和中转费用为RAB ，CAB ，那么由对应的A 顶点向B 顶点连一条有向边，从A 点得到的B 的可能最大值为：
(A 目前的最大值-CAB)×RAB 。
注意，这里所求的是最大值，为了转化为最短路，我们可以在数字前面加上一个负号。 案例3. 军事运输
军事运输优化有多个目标，以“最短路”为基本模型。设某部队利用公路网机动，在已知每条道路的容量及代价(距离、时间等)时，确定最优运输路线。例如，上级指挥机关需要从甲地运送一批物资到乙地，希望在现有的公路网中确定所走的路线，使距离(或时间)最短。这是一个典型的最短路问题。
最短路问题的一般性表述为：给定一个赋权图G ，对给每一条边(,)i j e v v =,对应权()ij w e w =；又给定G 的两个顶点s v 、t v ，设P 是G 中从s v 到t v 的一条路，定义P 的权为P
中所有边的权之和，记为()()e p
w p w e ∈=∑。
求一条s v 从t v 到的最短路，即求从s v 到t v 的一条权最小的路0p ，使0()min ()p w p w p =。
则称0p 为从s v 到t v 的最短路，0()w p 为从s v 到t v 的距离，记为(,)s t d v v （在有向图中，
(,)s t d v v 与(,)t s d v v 不一定相等）
。最短路问题的经典解法是Dijkstra 方法。 4.求解最短路的Floyd 算法
通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。
从图的带权邻接矩阵[(,)]A a i j n n =?开始，递归地进行n 次更新，即由矩阵(0)D A =，按一个公式，构造出矩阵(1)D ；又用同样地公式由(1)D 构造出(2)D ；……；最后又用同样的公式由(1)D n -构造出矩阵()D n 。矩阵()D n 的i 行j 列元素便是i 号顶点到j 号顶点的最短路径长度，称()D n 为图的距离矩阵，同时还可引入一个后继节点矩阵path 来记录两点间的最短路径。
采用的是松弛技术，对在i 和j 之间的所有其他点进行一次松弛。所以时间复杂度为3
()O n ; 其状态转移方程如下：min[,]min{[,][,],[,]}i j map i k map k j map i j =+ [,]m a p i j 表示
i 到j 的最短距离 K 是穷举i,j 的断点
[,]m a p n n 初值应该为0，或者按照题目意思来做。
当然，如果这条路没有通的话，还必须特殊处理,比如没有[,]map i k 这条路。 把图用邻接矩阵G 表示出来，如果从i V 到j V 有路可达，则[,]G i j d =，d 表示该路的长度；否则[,]G i j =?。
定义一个矩阵D 用来记录所插入点的信息，[,]D i j 表示从i V 到j V 需要经过的点，初始化[,]D i j j =。
把各个顶点插入图中，比较插点后的距离与原来的距离，
[,]min([,],[,][,])G i j G i j G i k G k j =+，如果[,]G i j 的值变小，则[,]D i j k =。 在G 中包含有两点之间最短道路的信息，而在D 中则包含了最短通路径的信息。 比如，要寻找从5V 到1V 的路径。根据D ，假如(5,1)3D =，(3,1)2D =，(2,1)1D =则说明从5V 到1V 经过3V ，从3V 到1V 经过2V ，2V 到1V 直接相连，路径为5321(,,,)V V V V ，如果(5,3)3D =，说明5V 与3V 直接相连，如果(3,1)1D =，说明3V 与1V 直接相连。
5.运用Matlab 来进行求解
利用Matlab 软件来进行求解，当前最流行的数学软件之一就是Matlab 。它是美国MathWorks 公司在1984年推出的数学软件，其具有优秀的数值计算能力和数据可视化能力。该软件不但可以解决数学中的数值计算问题，还可以解决符合演算问题，并且能够方便地绘出各种图形。Maflab 提供的各种函数可以避免在解决问题中做繁琐的数学推导和计算。
5.1运用Matlab 程序实现Dijkstra 算法
function [min,path]=dijkstra(w,start,terminal)
n=size(w,1); label(start)=0; f(start)=start;
for i=1:n
if i~=start
label(i)=inf;
end, end
s(1)=start; u=start;
while length(s) for i=1:n ins=0; for j=1:length(s) if i==s(j) ins=1; end, end if ins==0 v=i; if label(v)>(label(u)+w(u,v)) label(v)=(label(u)+w(u,v)); f(v)=u; end, end, end v1=0; k=inf; for i=1:n ins=0; for j=1:length(s) if i==s(j) ins=1; end, end if ins==0 v=i; if k>label(v) k=label(v); v1=v; end, end, end s(length(s)+1)=v1; u=v1; end min=label(terminal); path(1)=terminal; i=1; while path(i)~=start path(i+1)=f(path(i)); i=i+1 ; end path(i)=start; L=length(path); path=path(L:-1:1); 5.2用Matlab程序实现Floyd算法 function [D,path,min1,path1]=floyd(a,start,terminal) D=a;n=size(D,1);path=zeros(n,n); for i=1:n for j=1:n if D(i,j)~=inf path(i,j)=j; end, end, end for k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j) D(i,j)=D(i,k)+D(k,j); path(i,j)=path(i,k); end, end, end,end if nargin==3 min1=D(start,terminal); m(1)=start; i=1; path1=[ ]; while path(m(i),terminal)~=terminal k=i+1; m(k)=path(m(i),terminal); i=i+1; end m(i+1)=terminal; path1=m; end 6.结束语 本文通过对Dijkstra算法和Floyd算法的了解，加深了我对网络最短路径算法的认识，在对Dijkstra算法的认识的过程中，知道了Dijkstra算法是一种著名的最短路径算法, 它可为任一源节点找出与其它所有节点的最短路径。在寻径时要分步由源节点开始一步步地向相邻节点扩展, 直到包含所有网络节点为止。其方法是：建立一个节点集N, 开始时N 只包含源节点, 每算一步N 中增加一个相邻节点, 直到所有网络节点均进入N中后才结束计算。在这认识这种算法的过程中我发现了一些不足之处，当网络问题规模增大时，Dijkstra算法会使计算时间复杂度 的数组，其中N为网络的结点数，当网不断增大。在存储图形数据和运算时，需要定义N N 络的结点数较大时，将占用大量的计算机内存。而Floyd算法是一种动态算法，稠密图效果最佳，此算法简单有效，容易理解，可以算出任意两个节点之间的最短距离，代码编写简单，效果高于Dijkstra算法。但是Floyd算法计算最短路径时时间复杂比较高，不适合计算大量数据。 参考文献 [1]王杰臣.GIS网络分析的图简化方法研究[J].测绘学报,2001,(3):263-268. [2]邵振峰.配电网地理信息系统中的网络重构[J].测绘通报,2001,(3):103-105. [3]邓春燕.两种最短路径算法的比较[J].电脑知识与技术,2008,(12):511-512. [4] 王峰,游志胜,曼丽春. Dijkstra及基于Dijkstra的前Ⅳ条最短路径算法在智能交通系统中的应用[J].计 算机应用研究,2006,23(9):203—205. [5]王杰臣.最短路径问题的一种改进算法[J].解放军测绘学院学报,1999 ,16(14):282-285. [6]王杰臣.图的节点弧段联合结构表示法及其在GIS 最优路径选取中的应用[J].测绘学 报,2000,29(1):47-51. [7]李霖.变量查询代数及最短路径分析[J].测绘学报,2000,29(1):59-63. [8]张锦明.利用分区思路优化拓扑关系自动生成算法[J].测绘学院学报,2000,17(2):119-122. [9]郝琪.基于计算机模拟的车门下沉刚度改进设计及模态分析[J].湖北汽车工业学院学报,2006,20（2）:7-10. [10]王宏雁,徐少英.车门的轻量化设计[J].汽车工程,2004,26(3):349-353. [11]马迅.轻型客车结构刚度与模态的有限元分析[J].机械科学与技术,2002,21(1):86-88. [12]马迅,周坤,饶群章,等.基于有限元法的曲轴结构分析及优化[J].湖北汽车工业学院学 报,2005,19(3):9-13. [13]马迅,秦剑.制动鼓的热结构耦合分析[J].湖北汽车工业学院学报,2004,18(3):5-9. [14]凡金伟,吕康.基于Dijkstra算法在物流配送中的应用[J].电脑编程技巧与维护,2009,(04):39-45. [15]龙光正,杨建军.改进的最短路算法[J].系统工程与电子技术,2001,24(6):106-108. [16]陆锋.最短路径算法,分类体系与研究进展[J].测绘学报,2001,30(3):269-275. [17]王菲.高数公路交通事故紧急救援时间模型击救援站点布局研究[J].重庆交通大学,2008,15-16. [18]Goldbergav M. Expected performance of Dijkstra shortest path algorithm[D]. Princeton,Nj, USA:Princeton University,1996. [19]Zhan F B. Three fastest shortest path algorithms on real roadnetworks[J ].Journal of Geographic Information and DecisionAnalysis,1997,1(1):69-82. [20]Jayavel Shanmugasundaram , Eugene Shekita , Rimon Barr 1 Efficiently publishing relational data as XML documents The VLDB Journal,2001,10:133-154. [21]AhujaRK，MehlhornK，Orlin J B，TarjanRE．Faster Algorithms for the Ahortest Path Problem[J]．Journal ofAssociation of Co mputing Machinery,1990,37:213—223． 摘要：主要介绍最短路径问题中的经典算法——迪杰斯特拉(Dijkstra)算法和弗洛伊德（Floyd）算法，以及在实际生活中的运用。 关键字：Dijkstra算法、Floyd算法、赋权图、最优路径、Matlab 目录 摘要 (1) 1引言 (1) 2最短路 (2) 2.1 最短路的定义 (2) 2.2最短路问题常见算法 (2) 3 Dijkstra算法 (2) 3.1Dijkstra算法描述 (2) 3.2 Dijkstra算法举例 (3) 3.3算法的正确性和计算复杂性 (5) 3.3.1贪心选择性质 (5) 3.3.2最优子结构性质 (6) 3.3.3 计算复杂性 (7) 4 Floyd算法 (7) 4.1Floyd算法描述 (8) 4.2 Floyd算法步骤 (11) 4.3 Floyd算法举例 (11) 5 Dijkstra算法和Floyd算法在求最短路的异同 (11) 6 利用计算机程序模拟算法 (11) 7 附录 (11) 8 论文总结 (13) 9 参考文献 (13) 1 引言 最短路问题是图论理论的一个经典问题。寻找最短路径就是在指定网络中两结点间找一条距离最小的路。最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。 最短路径算法的选择与实现是通道路线设计的基础,最短路径算法是计算机科学与地理信息科学等领域的研究热点,很多网络相关问题均可纳入最短路径问题的范畴之中。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。 2 最短路 2.1 最短路的定义 对最短路问题的研究早在上个世纪60年代以前就卓有成效了,其中对赋权图 的有效算法是由荷兰著名计算机专家E.W.Dijkstra 在1959年首次提出的,该算法能够解决两指定点间的最短路,也可以求解图G 中一特定点到其它各顶点的最短路。后来海斯在Dijkstra 算法的基础之上提出了海斯算法。但这两种算法都不能解决含有负权的图的最短路问题。因此由Ford 提出了Ford 算法,它能有效地解决含有负权的最短路问题。但在现实生活中,我们所遇到的问题大都不含负权,所以我们在的() 0ij w ≥的情况下选择Dijkstra 算法。 定义1若图G=G(V,E)中各边e 都赋有一个实数W(e),称为边e 的权,则称这种图为赋权图,记为G=G(V,E,W)。 定义2若图G=G(V,E)是赋权图且()0W e ≥,()e E G ∈,假设[i,j] 的权记为()i j W ，,若i 与j 之间没有边相连接，那么()i j =W ∞，。路径P 的定义为路径中各边的长度之和，记W （P ）。图G 的结点u 到结点v 距离记为d(u,v)，则u 、v 间的最短路径可定义为 { ()min P 0d(u,v)=,u v W =∞（），不可达时 。 2.2 最短路问题常见算法 在求解网络图上节点间最短路径的方法中,目前国内外一致公认的较好算法有迪杰斯特拉(Dijkstra)及弗罗伊德(Floyd)算法。这两种算法中,网络被抽象为一个图论中定义的有向或无向图,并利用图的节点邻接矩阵记录点间的关联信息。在进行图的遍历以搜索最短路径时,以该矩阵为基础不断进行目标值的最小性判别,直到获得最后的优化路径。 Dijkstra 算法是图论中确定最短路的基本方法,也是其它算法的基础。为了求出赋权图中任意两结点之间的最短路径,通常采用两种方法。一种方法是每次以一个结点为源点,重复执行Dijkstra 算法n 次。另一种方法是由Floyd 于1962年提出的Floyd 算法,其时间复杂度为 ()3O n ,虽然与重复执行Dijkstra 算法n 次的时间复杂度相同,但其形式上略为简单,且实际运 算效果要好于前者。 3 Dijkstra 算法 3.1 Dijkstra 算法描述 最短路径算法—D i j k s t r a 总结 -标准化文件发布号：（9556-EUATWK-MWUB-WUNN-INNUL-DDQTY-KII Dijkstra 算法解释 本文引用三篇文章：分别是谢光新-Dijkstra 算法， zx770424 -Dijkstra 算法， 中华儿女英雄 -Dijkstra 算法 有兴趣的朋友请引用原文，由于分类很不相同难以查找，此处仅作汇总。 谢光新的文章浅显易懂，无需深入的数学功力，每一步都有图示，很适合初学者了解。 zx770424将每一步过程，都用图示方式和公式代码\伪代码对应也有助于，代码的理解。 中华儿女英雄从大面上总结了Dijkstra 的思想，并将演路图描叙出来了。起到总结的效果。 希望这篇汇总有助于大家对Dijkstra 算法的理解。 Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。 简介 Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。 算法描述 (这里描述的是从节点1开始到各点的dijkstra算法，其中Wa->b表示a->b的边的权值，d(i)即为最短路径值) 1．置集合S={2,3,...n}, 数组d(1)=0, d(i)=W1->i(1,i之间存在边) or +无穷大(1.i之间不存在边) 2．在S中，令d(j)=min{d(i),i属于S}，令S=S-{j}，若S为空集则算法结束，否则转3 3．对全部i属于S,如果存在边j->i，那么置d(i)=min{d(i), d(j)+Wj->i}，转2 Dijkstra算法思想为：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。 算法具体步骤 （1）初始时，S只包含源点，即S=，v的距离为0。U包含除v外的其他顶点，U中顶点u距离为边上的权（若v与u有边）或）（若u不是v的出边邻接点）。 （2）从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。 （3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u（u U）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k 的距离加上边上的权。 （4）重复步骤（2）和（3）直到所有顶点都包含在S中。 复杂度分析 Dijkstra 算法的时间复杂度为O(n^2) 空间复杂度取决于存储方式，邻接矩阵为O(n^2) 最短路径之Dijkstra算法详细讲解 １最短路径算法 在日常生活中，我们如果需要常常往返A地区和B 地区之间，我们最希望知道的可能是从A地区到B地区间的众多路径中，那一条路径的路途最短。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括： （１）确定起点的最短路径问题：即已知起始结点，求最短路径的问题。 （２）确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。 （３）确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。 （４）全局最短路径问题：求图中所有的最短路径。 用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。最常用的路径算法 有：Dijkstra算法、A*算法、Bellman-Ford算法、Floyd-Warshall算法、Johnson算法。 本文主要研究Dijkstra算法的单源算法。 ２Dijkstra算法 2.1 Dijkstra算法 Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。 Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。 2.2 Dijkstra算法思想 Dijkstra算法思想为：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径, 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U 表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S 中的顶点为中间顶点的当前最短路径长度。 2.3 Dijkstra算法具体步骤 （1）初始时，S只包含源点，即S＝，v的距离为0。U包含除v外的其他顶点，U中顶点u距离为边上的权（若v与u有边）或）（若u不是v的出边邻接点）。 （2）从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。 （3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u（u U）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u 的距离值，修改后的距离值的顶点k的距离加上边上的权。 （4）重复步骤（2）和（3）直到所有顶点都包含在S中。 2.4 Dijkstra算法举例说明 如下图，设A为源点，求A到其他各顶点（B、C、D、E、F）的最短路径。线上所标注为相邻线段之间的距离，即权值。（注：此图为随意所画，其相邻顶点间的距离与图中的目视长度不能一一对等） 实验五分支限界法实现单源最短路径 一实验题目：分支限界法实现单源最短路径问题 二实验要求：区分分支限界算法与回溯算法的区别，加深对分支限界法的理解。 三实验内容：解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。算法从图G的源顶点s和空优先队列开始。 结点s被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。 四实验代码 #include :算法的设计思想 本算法采用分支定界算法实现。构造解空间树为：第一个城市为根结点，与第一个城市相邻的城市为根节点的第一层子节点，依此类推；每个父节点的子节点均是和它相邻的城市；并且从第一个根节点到当前节点的路径上不能出现重复的城市。 本算法将具有最佳路线下界的节点作为最有希望的节点来展开解空间树，用优先队列实现。算法的流程如下：从第一个城市出发，找出和它相邻的所有城市，计算它们的路线下界和费用，若路线下界或费用不满足要求，将该节点代表的子树剪去，否则将它们保存到优先队列中，并选择具有最短路线下界的节点作为最有希望的节点，并保证路径上没有回路。当找到一个可行解时，就和以前的可行解比较，选择一个较小的解作为当前的较优解，当优先队列为空时，当前的较优解就是最优解。算法中首先用Dijkstra算法算出所有点到代表乙城市的点的最短距离。算法采用的下界一个是关于路径长度的下界，它的值为从甲城市到当前城市的路线的长度与用Dijkstra算法算出的当前城市到乙城市的最短路线长度的和；另一个是总耗费要小于1500。 伪代码 算法AlgBB() 读文件m1和m2中的数据到矩阵length和cost中 Dijkstra(length) Dijkstra(cost) while true do for i←1 to 50 do //选择和node节点相邻的城市节点 if shortestlength>optimal or mincost>1500 pruning else if i＝50 optimal=min(optimal,tmpopt)//选当前可行解和最优解的 较小值做最优解 else if looped //如果出现回路 pruning //剪枝 else 将城市i插入到优先队列中 end for while true do if 优先队列为空 输出结果 else 取优先队列中的最小节点 if 这个最小节点node的路径下界大于当前的较优解 continue 实验三单源最短路径 一、实验目的及要求 掌握贪心算法的基本思想 用c程序实现单源最短路径的算法 二、实验环境 Window下的vc 2010 三、实验内容 1、有向图与单源点最短路径 2、按路径长度非降的次序依次求各节点到源点的最短路径 3、Dijkstra算法 四、算法描述及实验步骤 设给定源点为Vs，S为已求得最短路径的终点集，开始时令S={Vs} 。当求得第一条最短路径(Vs ，Vi)后，S为{Vs，Vi} 。根据以下结论可求下一条最短路径。 设下一条最短路径终点为Vj ，则Vj只有：源点到终点有直接的弧 #define MAX 999 void getdata(int **c,int n) { int i,j; int begin,end,weight; for (i=1;i<=n;i++) { for (j=1;j<=n;j++) { if(i==j) c[i][j]=0; else c[i][j]=MAX; } } do { cout<<"请输入起点终点权值(-1退出)："; cin>>begin; if(begin==-1) break; cin>>end>>weight; c[begin][end]=weight; } while(begin!=-1); } void Dijkstra(int n,int v ,int *dist,int *prev,int **c) { bool s[MAX]; int i,j; for (i=1;i<=n;i++) { dist[i]=c[v][i]; //从源点到各点的值 s[i]=false; if(dist[i]==MAX) prev[i]=0; //最大值没有路径 else prev[i]=v; //前驱为源点 } dist[v]=0;s[v]=true; for (i=1;i<=n;i++) { int temp=MAX; int u=v; for(j=1;j<=n;j++) if((!s[j])&&(dist[j] 第36卷第5期2002年9月 浙 江 大 学 学 报(工学版) Jo ur nal o f Zhejiang U niv ersity(Eng ineer ing Science) Vol.36No.5Sep.2002 收稿日期:2001-10-24. 作者简介:柴登峰(1974-),男,浙江江山人,博士生,从事遥感图像处理、地理信息系统方面研究.E-mail:chaidf@z https://www.doczj.com/doc/9e224731.html, 前N 条最短路径问题的算法及应用 柴登峰,张登荣 (浙江大学空间信息技术研究所,杭州浙江310027) 摘 要:现有最短路径问题指的是狭义最短路径问题,针对该问题而设计的算法只能求得最短的一条路径.前N 条最短路径拓宽了最短路径问题的内涵(即不仅要求得最短路径,还要求得次短、再次短…第N 短路径),是广义最短路径问题.在图论理论基础上分析问题之后,设计了一个递归调用Dijkstr a 算法的新算法,该算法可以求取前N 条最短路径,而且时间、空间复杂度都为多项式阶.该算法已经成功应用于一个交通咨询系统中,自然满足实时应用需要. 关键词:最短路径;N 条最短路径;网络分析;地理信息系统;交通咨询系统 中图分类号:P 208;O 22 文献标识码:A 文章编号:1008-973X (2002)05-0531-04 Algorithm and its application to N shortest paths problem CHAI Deng-f eng,ZHAN G Deng-rong (I nstitute of Sp ace and I n f ormation T echnical ,Zhej iang U niv er sity ,H angz hou 310027,China ) Abstract :As the shor test path denotes one path ,algorithms designed for shor test path problem can g et only one path .N shortest paths are N paths including the shortest one ,the one inferior to the shortest one,eto.After reviewing the application of shortest poth pro blem ,an N shortest paths problem w as put fo rw ard and described.Gr aph theo ry w as used to analy ze the problem and results in fo ur theoretical con-clusions .T hen ,algo rithm recursively calling the Dijkstra algor ithm was desig ned and analy zed .Bath time co nplexity and space conplex ity are poly nom ial order.The algo rithm w as tested by ex periment and applied to a traffic consultatio n system of Guang zhou City ,it can meet the need of r eal-time application.Key words :sho rtest path;N shor test paths;netw ork analysis;tr affic consultation system ;GIS 20世纪中后期,随着计算机的出现和发展,图论的理论和应用研究得到广泛重视,图论作为一个数学分支的地位真正得到了确立.现在,图论的应用已经深入到众多领域,GIS 网络分析就是图论在地理信息领域的重要应用[3] ,此外,还有城市规划、电子导航、交通咨询等等. 最短路径问题是图论中的一个典范问题[1],主要研究成果有Dijkstra 、Floy d 等优秀算法[1,2],Dijk-stra 还被认为是图论中的好算法[1] .目前的研究工作主要集中于算法实现的优化改进与应用方面[3,4].最短路径问题通常有两类[2]:一类是求取从某一源点到其余各点的最短路径;另一类是求取每一对顶 点之间的最短路径.它们从不同的角度描述问题,但有一个共同的缺陷:这里的最短路径指两点之间最 短的那一条路径,不包括次短、再次短等等路径.在此不妨称以上两类问题为狭义最短路径问题,为此设计的算法只能求得最短的一条路径,而不能得到次短、再次短等等路径. 实际上,用户在使用咨询系统或决策支持系统时,希望得到最优的决策参考外,还希望得到次优、再次优等决策参考,这同样反映在最短路径问题上.因此,有必要将最短路径问题予以扩充,成为N 条最短路径问题,即不但要求得到最短路径,还要得到次短、再次短等路径.这称之为广义最短路径问题. 数据结构第20次课 （续表） 思考.题 作业题试对下图所示的AOE网络，解答下列问题。 (1) 这个工程最早可能在什么时间结束。 (2) 求每个事件的最早开始时间Ve[i]和最迟开始时间Vl[I]。 (3) 求每个活动的最早开始时间e( )和最迟开始时间l( )。 (4) 确定哪些活动是关键活动。画出由所有关键活动构成的图，指出哪些活动加速可使整个工程提前完成。 *参考资料《数据结构辅导与提高》，徐孝凯编著，清华大学出版社 《数据结构习题解答与考试指导》，梁作娟等编著，清华大学出版社 授课内容 关键路径 对整个工程和系统，人们关心的是两个方面的问题： 一）工程能否顺利进行（对AOV网进行拓扑排序） 二）估算整个工程的完成所必须的最短时间（对AOE网求关键路径） 1. AOE-网 } 与AOV-网相对应的是AOE-网(Activity On Edge)，即边表示活动的网。 AOE-网是一个带权的有向无环图，其中，顶点表示事件(Event)，弧表示活 动，权表示活动持续的时间。通常，AOE-网可用来估算工程的完成时间。 例：下图是一个假想的有11项活动的AOE-网。其中有9个事件v 1 ， v 2 ，…，v 9 ，每个事件表示在它之前的活动已经完成，在它之后的活动可以 开始。如v 1 表示整个工程开始，v 9 表示整个工程结束，v 5 表示a 4 和a 5 已经 完成，a 7 和a 8 可以开始。与每个活动相联系的数是执行该活动所需的时间。 比如，活动a 1 需要6天，a 2 需要4天等。 和AOV-网不同，对AOE-网有待研究的问题是： (1)完成整项工程至少需要多少时间 (2)哪些活动是影响工程进度的关键 2. 关键路径 由于在AOE-网中有些活动可以并行地进行，所以完成工程的最短时间 是从开始点到完成点的最长路径的长度(这里所说的路径长度是指路径上 各活动持续时间之和，不是路径上弧的数目)。路径长度最长的路径叫做关 备注： 回顾 实验四单源最短路径问题 一、实验目的： 1、理解分支限界法的剪枝搜索策略； 2、掌握分支限界法的算法柜架； 3、掌握分支限界法的算法步骤； 4、通过应用范例学习动态规划算法的设计技巧与策略； 二、实验内容及要求： 1、使用分支限界法解决单源最短路径问题。 2、通过上机实验进行算法实现。 3、保存和打印出程序的运行结果，并结合程序进行分析，上交实验报告。 三、实验原理： 分支限界法的基本思想： 1、分支限界法与回溯法的不同： 1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。 2、分支限界法基本思想： 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 3、常见的两种分支限界法： 1）队列式(FIFO)分支限界法 按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 2）优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 四、程序代码 #include 第 6 章图 课后习题讲解 1. 填空题 ⑴设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。 【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵任何连通图的连通分量只有一个，即是（）。 【解答】其自身 ⑶图的存储结构主要有两种，分别是（）和（）。 【解答】邻接矩阵，邻接表 【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。 ⑷已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。 【解答】Ｏ(n+e) 【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。 【解答】求第j列的所有元素之和 ⑹有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。 【解答】出度 ⑺图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。 【解答】前序，栈，层序，队列 ⑻对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。 【解答】Ｏ(n2)，Ｏ(elog2e) 【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。 【解答】回路 单源最短路径的Dijkstra算法： 问题描述： 给定一个带权有向图G=（V，E），其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其他各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。 算法描述： Dijkstra算法是解单源最短路径的一个贪心算法。基本思想是：设置顶点集合S并不断地做贪心选择来扩充这个集合。一个顶点属于S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist做必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其他顶点之间的最短路径长度。 源代码： #include using namespace std; //-------------------------------------数据声明------------------------------------------------//c[i][j]表示边(i,j)的权 //dist[i]表示当前从源到顶点i的最短特殊路径长度 //prev[i]记录从源到顶点i的最短路径上的i的前一个顶点 //--------------------------------------------------------------------------------------------- void Dijkstra(int n, int v, int dist[], int prev[], int c[][LEN]) { bool s[LEN]; // 判断是否已存入该点到S集合中 for (int i = 1; i <= n; i++) { dist[i] = c[v][i]; s[i] = false; //初始都未用过该点 if (dist[i] == MAX) prev[i] = 0; //表示v到i前一顶点不存在 else prev[i] = v; } dist[v] = 0; s[v] = true; 最短路径算法在物流运输 中的应用 Last revision date: 13 December 2020. 本科生毕业设计（论文）题目：线性表的设计和实现 学生姓名：张三 学号： 1153 院系：基础科学学院信息技术系 专业年级： 2012级信息与计算科学专业 指导教师：李四 年月日 摘要 随着现代物流业的发展，如何优化和配置物流的运输路径成为了一个热点的问题。其中，最具代表性的问题就是如何在一个道路网络中选择两点之间的合适路径，使其距离最短。为了解决这个问题，本文介绍了两种最常用的最短路径求解方法——DIJKSTRA算法与FLOYD算法，分析了它们的适用范围以及时间复杂度。最后，对一个具体的航空公司物流配送问题进行了求解，得到了理论最优路径。 关键词：最短路径问题；DIJKSTRA算法；物流运输 ABSTRACT With the development of modern logistics industry, how to optimize and configure the transport path of logistics has become a hot issue. Among them, the most representative problem is how to select the appropriate path between two points in a road network to minimize the distance. In order to solve this problem, this paper introduces two most common shortest path solutions —— Dijkstra algorithm and Floyd algorithm, and analyzes their application range and time complexity. Finally, a specific airline logistics distribution problem is solved, and the theoretical optimal path is obtained. Keywords：Minimum path problem；Dijkstra algorithm；Logistics transportation 单源最短路径问题 I 用贪心算法求解 贪心算法是一种经典的算法，通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。一般具有2个重要的性质：贪心选择性质和最优子结构性质。 一、问题描述与分析 单源最短路径问题是一个经典问题，给定带权有向图G =(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其他各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。 分析过程：运用Dijkstra算法来解决单源最短路径问题。 具备贪心选择性质 具有最优子结构性质 计算复杂性 二、算法设计（或算法步骤） 用贪心算法解单源最短路径问题： 1.算法思想： 设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其他顶点之间的最短路径长度。 2.算法步骤： (1) 用带权的邻接矩阵c来表示带权有向图, c[i][j]表示弧 最短路径问题的算法分析及建模案例 最短路径问题的算法分析及建模案例 一.摘要 (3) 二.网络最短路径问题的基础知识 (5) 2.1有向图 (7) 2.2连通性................... 错误！未定义书签。 2.3割集....................... 错误！未定义书签。 2.4最短路问题 (8) 三．最短路径的算法研究.. 错误！未定义书签。 3.1最短路问题的提出 (9) 3.2 Bellman最短路方程错误！未定义书签。 3.3 Bellman-Ford算法的基本思想错误！未定义书签 3.4 Bellman-Ford算法的步骤错误！未定义书签。 3.5实例....................... 错误！未定义书签。 3.6 Bellman-FORD算法的建模应用举例错误！未定义 3.7 Dijkstra算法的基本思想 (9) 3.8 Dijkstra算法的理论依据 (9) 3.9 Dijkstra算法的计算步骤 (9) 3.10 Dijstre算法的建模应用举例 (10) 3.11 两种算法的分析错误！未定义书签。 1.Diklstra算法和Bellman-Ford算法 思想有很大的区别错误！未定义书签。 Bellman-Ford算法在求解过程中，每 次循环都要修改所有顶点的权值，也就 是说源点到各顶点最短路径长度一直 要到Bellman-Ford算法结束才确定下 来。...................... 错误！未定义书签。 2.Diklstra算法和Bellman-Ford算法 的限制.................. 错误！未定义书签。 3.Bellman-Ford算法的另外一种理解错误！未定 4.Bellman-Ford算法的改进错误！未定义书签。 摘要 近年来计算机发展迅猛，图论的研究也得到了很大程度的发展，而最短路径 问题一直是图论中的一个典型问题，它已应用在地理信息科学，计算机科学等 诸多领域。而在交通路网中两个城市之间的最短行车路线就是最短路径问题的 一个典型例子。 由于最短路径问题在各方面广泛应用，以及研究人员对最短路径的深入研究， 使得在最短路径问题中也产生了很多经典的算法。在本课题中我将提出一些最 短路径问题的算法以及各算法之间的比较，最后将这些算法再应用于实际问题 沈阳航空航天大学 课程设计报告 课程设计名称：数据结构课程设计 课程设计题目：实现求关键路径的算法 院（系）：计算机学院 专业：计算机科学与技术 班级：04010102 学号：2008040101058 姓名：刘小靖 指导教师：许清 完成日期：2014年1月9日 沈阳航空航天大学课程设计报告 目录 第一章需求分析 (1) 1.1题目内容与要求 (1) 1.2题目理解与功能分析 (1) 第二章概要设计 (3) 2.1设计思路 (3) 2.2系统模块图 (3) 第三章详细设计 (4) 3.1图存储结构的建立 (4) 3.2求关键路径的算法 (5) 第四章调试分析 (7) 参考文献 (10) 附录（程序清单） (11) 第一章需求分析 1.1 题目内容与要求 内容： 自拟定合适的方式从键盘上输入一个AOE网，使用图的邻接表存储结构存储该AOE网，然后求出该AOE网的关键路径。输入AOE网的方式要尽量的简单方便，程序要能够形象方便地观察AOE网和它的关键路径 基本要求： 1．熟悉图的存储结构及操作方式； 2．熟悉求关键路径的算法； 3．熟练运用开发环境； 4．完成软件的设计与编码； 5. 熟练掌握基本的调试方法； 6. 提交符合课程设计规范的报告； 1.2 题目理解与功能分析 该题实质要求用数据结构中的图形知识编写一个求无循环有向帯权图中从起点到终点所有路径，经分析、比较求出长度最大路径，从而求出关键路径。 通常我们用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边 物流运输系统中最短路径算法及应用 摘要：根据GIS中网络计算的实际情况，根据A*算法和Dijkstra算法中快速搜索技术的实现入手，采用最短路径算法结合GIS的方法，提出了一种解决物流运输中车辆路径问题的高效率实现的方法。 引言： 在竞争日益激烈的现代商业社会，企业只有以市场为核心去适应不断变化的环境并及时对市场做出发应，才能在竞争中立于不败之地。物流管理正是以实现上述要求为目标的。而物流配送是现代化物流管理中的一个重要环节。它是指按用户的定货要求，在配送中心进行分货、配货，并将配好的货物及时送交收货人的活动。在物流配送业务中，存在许多优化决策的问题。本文只讨论物流配送路径优化问题。合理选择配送路径，对加快配送速度、提高服务质量、降低配送成本以及增加经济效益都有很大影响。所谓的车辆路径问题（Vehicle Routing Problem）VRP。它也是目前在物流系统中较受关注的一个方面。它是指在客户需求位置已知的情况下，确定车辆在各个客户间的行程路线，使得运输路线最短或运输成本最低。 一、系统介绍求解物流配送路径优化问题的方法有很多是路径引导的功能。本设计主要功能是从给定的车辆位置和多个目标点位置，计算车辆遍历所有目标点的代价最优值，并给出代价值和路径描述，并在地图上进行路径显示。路径引导模块的主要过程：初始化路网-＞得到车辆信息和目标点信息-＞求车辆遍历所有目标点的代价最优值和遍历次序（仅求遍历次序，而不需求走什么道路）-＞求每个目标点遍历的最优路径（求具体的道路）-＞输出遍历次序和路径描述 二、车辆遍历所有目标点的代价最优值算法 本设计中的遍历次序的算法采用的是等代价搜索法，它是 A *算法的一种简化 版本。等代价搜索法也是基于宽度优先搜索上进行了部分优化的一种算法,它与A＊ 算法的相似之处都是每次只展开某一个结点（不是展开所有结点）, 不同之处在于：它不需要去另找专门的估价函数，而是以该结点到A点的距离作为估价值。例如图1, 从A 点出发，要遍历C,B,D,E四个目标点。具体算法过程如下：最短路径学年论文
最短路径算法—dijkstra总结
gis计算最短路径的Dijkstra算法详细讲解
分支限界法实现单源最短路径问题
最短路径流程图及算法详解
单源最短路径 贪心算法
前N条最短路径问题的算法及应用
第20讲-关键路径与最短路径
单源最短路径问题
数据结构与算法第6章图答案
单源最短路径的Dijkstra算法
最短路径算法在物流运输中的应用
单源最短路径
最短路径问题的算法分析及建模案例
实现求关键路径的算法
物流运输系统中最短路径算法及应用
相关主题
文本预览