湖北大学
本科毕业论文（设计）
题目最短路径算法及其应用
姓名学号
专业年级
指导教师职称
2011年 4月 20 日
目录
绪论 (1)
1 图的基本概念 (1)
1.1 图的相关定义 (1)
1.2 图的存储结构 (2)
1.2.1 邻接矩阵的表示 (2)
1.2.2 邻接矩阵的相关结论 (3)
2 最短路径问题 (3)
2.1 最短路径 (4)
2.2 最短路径算法 (4)
2.2.1Dijkstra算法 (4)
2.2.2Floyd算法 (5)
3 应用举例 (5)
3.1 Dijkstra算法在公交网络中的应用 (5)
3.1.1 实际问题描述 (5)
3.1.2 数学模型建立 (5)
3.1.3 实际问题抽象化 (6)
3.1.4 算法应用 (6)
3.2 Floyd算法在物流中心选址的应用 (7)
3.2.1 问题描述与数学建模 (7)
3.2.2 实际问题抽象化 (7)
3.2.3 算法应用 (8)
参考文献 (10)
附录 (11)
最短路径算法及其应用
摘要
最短路径算法的研究是计算机科学研究的热门话题，它不仅具有重要的理论意义，而且具有重要的实用价值。最短路径问题有广泛的应用，比如在交通运输系统、应急救助系统、电子导航系统等研究领域。最短路径问题又可以引申为最快路径问题、最低费用问题等，但它们的核心算法都是最短路径算法。经典的最短路径算法——Dijkstra和Floyd算法是目前最短路径问题采用的理论基础。本文主要对Dijkstra和Floyd算法进行阐述和分析，然后运用这两个算法解决两个简单的实际问题。
【关键字】最短路径 Dijkstra算法 Floyd算法图论
Shortest path algorithms and their applications
Abstract
The research about the shortest path is a hot issue in computer science. It has both important theoretical significance and important utility value. The shortest path problem has broad application area, such as transport system, rescue system, electronic navigation system and so on. The shortest path problem can be extended to the problem of the fastest path problem and the minimum cost problem. But their core algorithms are all both the shortest path algorithms. The classical algorithms for the shortest path——Dijkstra and Floyd are the theoretical basis for solving the problems of the shortest path. The article mainly through the demonstration and analysis of the Dijkstra and Floyd algorithms, then use the algorithms to solve the two simple practical problems.
【keywords】shortest path Dijkstra algorithm Floyd algorithm graph
绪论
随着知识经济的到来，信息将成为人类社会财富的源泉，网络技术的飞速发展与广泛应用带动了全社会对信息技术的需求，最短路径问题作为许多领域中选择最优问题的基础，在电子导航，交通旅游，城市规划以及电力，通讯等各种管网，管线的布局设计中占有重要的地位。
最短路径，顾名思义就是在所有的路径中找到一条距离最短的路径，而我们所说的最短路径通常不仅仅指地理意义的距离最短，还可以引申到其他的度量，如时间，费用，路线容量等。相应地，最短路径问题就成为最快路径问题，最低费用问题等，所以我们所说的最短路径也可以看作是最优路径问题。
最短路径问题在交通网络结构的分析，交通运输路线（公路、铁路、河流航运线、航空线、管道运输线路等）的选择，通讯线路的建造与维护，运输货流的最小成本分析，城市公共交通网络的规划等，都有直接应用的价值。最短路径问题在实际中还常用于汽车导航系统以及各种应急系统等（如110报警、119火警以及120医疗救护系统）这些系统一般要求计算出到出事地点的最佳路线的时间应该在1s 到3s 内，在行车过程中还需要实时计算出车辆前方的行驶路线，这就决定了最短路径问题的实现应该是高效的。
最短路径问题一直是计算机科学，运筹学，交通工程学，地理信息学等学科的一个研究热点。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。
1 图论基本概念
图(graph)是一种较线性表和树更为复杂的数据结构，图与线性表和树的结构区别表现在结点之间的关系上，线性表中的每个结点（除首尾结点外）都有一个前驱结点和一个后继结点，结点与结点之间的关系是一对一的关系；树上的每个结点都有一个父结点（根结点除外）和一个或多个孩子结点（叶子结点除外），结点与结点的关系是一对多的关系；而图中结点之间的关系是多对多的关系，结点与结点之间的连接是任意的，每对结点间可以有连接也可以没有连接。
1.1 图的相关定义
图G 是由一个非空的顶点集合V 和一个描述顶点之间多对多关系的边集合E 组成的一个数据结构，记为G V,E =<>，其中：
（1）12n V {v ,v ,...,v }=是有限的顶点集合，i v 称为顶点，简称点，V 称为顶点集。 （2）E 是有限集合，称为边集。E 中每个元素都有V 中的顶点与之对应，称之为边。
定义1 无向图和有向图
如果连接某两个不同顶点间的边是有方向的，则称该边为有向边。有向边用有序对i j V,V <>表示，其中i V 表示源点，j V 表示终点。如果图G 的所有边都是有向边，则称图G 为有向图。
如果连接某两个不同顶点间的边是没有方向的，则称该边为无向边。无向边用无序对i j (V ,V )表示，边i j (V ,V )和边j i (V ,V )代表同一条边。如果图G 中的所有边都是无向边，则称图G 为无向图。
定义2 邻接点与邻接边
在图G V,E =<>中，若两个顶点i V 和j V 是一条边的端点，则称这两个顶点互为邻接点，否则
i V 与j V 称为不邻接的。
类似地，具有公共顶点的两条边称为邻接边。
定义3 度
①有向图
入度:有向图中以顶点i V 为终点的边的数目，称为顶点i V 的入度。 出度:有向图中以顶点i V 为源点的边的数目，称为顶点i V 的出度。 ②无向图
无向图中，与顶点i V 相关连的边的个数为顶点i V 的度。
定义4 路径
在无向图G V,E =<>中，从顶点i V 到j V 的一条路径是一个顶点序列 (i V ,i1V ,i2V ,…,im V ,j V )，称为从顶点i V 到j V 的一条路径。
如果是有向图，则路径也是有向的，路径的长度是指路径上的边或弧的数目。 如果序列中第一个顶点和最后一个顶点相同的路径称为回路或环。 如果序列中顶点不重复出现的路径称为简单路径。
定义5 连通
在无向图G 中，如果从顶点i V 到顶点j V 有路径存在，则称i V 和j V 是连通的。 若图中任意两个顶点都连通的无向图称为连通图。
在有向图中如果从顶点i V 到顶点j V 有路径存在，则称i V 到j V 是连通的。 若图中的每一对顶点都连通的有向图称为强连通图。
定义6 权与网
如果图的边或弧具有与之相关的数，则这种与连接顶点i V 和j V 的边或弧相关的数i j W(V,V )就称为边或弧的权。带权的图就称为网。
权可以用来描述从一个顶点到另一个顶点的距离或耗费。如果把道路交通网中的道路起点、终点和交叉口表示为顶点，把道路表示威连接顶点的弧，把道路的长度、通行时间等属性表示为道路的权，那么道路网就被抽象成为带权的图，而与之相关的问题就可以利用图论的方法进行分析。
1.2 图的存储结构
图的存储结构除了要存储图中各个顶点本身的信息外，同时还要存储顶点与顶点之间的所有关系（边的信息）。常用的图的存储结构有邻接矩阵、邻接表、十字邻接表和邻接多重表。由于本文主要用到第一种，故只介绍第一种。
1.2.1 邻接矩阵的表示
邻接矩阵是表示顶点之间相邻关系的矩阵。设G V,E =<>，是具有n （n 大于0）个顶点的图，
顶点的顺序依次为（0V ,1V ,…,n-1V ），则G 的邻接矩阵A 是n 阶方阵，其定义如下：
A[i][j]=1
0???
i j i j v ,v E v ,v E ∈∈对于无向图（），对于有向图<>其它情况
若G 是网，则邻接矩阵可定义为： A[i][j]=i j
w 0??
∞
?，或 i j i j v ,v v ,v E ∈若()或<>其它情况
邻接矩阵定义如下：
int adjmatrix =Array[n][n]。
邻接矩阵的数据类型定义如下：
#define MAXV <最大顶点个数> / /最多顶点个数 typedef struct vertex {
int num; / /顶点编号 char data; / /顶点的信息 }VertexType ；
typedf stuct {
int n,e; / /顶点个数，边的条数 VertexType vexs[MAXV]; / /顶点集合 int edges[MAXV][MAXV]; / /边的结合 }MGraph;
1.2.2 邻接矩阵的相关结论
在无向图的邻接矩阵具有以下特征： （1）矩阵是对称的；
（2）第i 行或第i 列中l 的个数为顶点i 的度； （3）矩阵中1的个数为图中边的数目；
（4）很容易判断顶点i 和顶点j 之间是否有边相连(看矩阵中i 行j 列值是否为l)。 而有向图的邻接矩阵的特征为： （1）矩阵不一定是对称的；
（2）第i 行中1的个数为顶点i 的出度； （3）第j 列l 的个数为顶点j 的入度； （4）矩阵中1的个数为图中弧的数目；
（5）很容易判断顶点i 和顶点j 之间是否有弧相连。
2 最短路径问题
所谓最短路径即是从图G 中某对顶点i V 和j V (i j ≠)之间的所有路径中选出权值之和最短的一
条路径作为顶点i V 到顶点j V 的最短路径。其中边的权值可多种，比如路途、费用、耗时等，也可以是同时存在多种权值，根据给定的比例，算出边的综合权值。
2.1最短路径
在一个无权的图中，若从一个顶点到另一个顶点存在着一条路径，则称该路径长度为该路径上所经过的边的数目，它等于该路径上的顶点数减1。由于从一个顶点到另一个顶点可能存在着多条路径，每条路径上所经过的边数可能不同，即路径长度不同，把路径长度最短（即经过的边数最少）的那条路径叫作最短路径或者最短距离。
对于带权的图，考虑路径上各边的权值，则通常把一条路径上所经边的权值之和定义为该路径的路径长度或带权路径长度。从源点到终点可能不止一条路径，把带权路径长度最短的那条路径称为最短路径，其路径长度（权值之和）称为最短路径长度或最短距离。
实际上，只要把无权图上的每条边看成是权值为1的边，那么无权图和带权图的最短路径和最短距离的定义是一致的。
对于连接某对给定顶点的路径，可能有多条路径有相同的长度，因此最短路径问题的解不一定是唯一的，它可能有多个满足约束条件的解。
2.2 最短路径算法
求图中的最短路径有两方面的问题：求图中某一顶点到其余各顶点的最短路径与求图中每一对顶点之间的最短路径。它们分别有Dijkstra 算法和Floyd 算法，是目前两个比较著名的最短路径算法。
2.2.1 Dijkstra 算法
Dijkstra 算法又称为标号法，是1959年由荷兰计算机科学家E.W.Dijkstra 提出的关于最短路径的搜索算法。该算法是用于求解单源点最短路径的实用算法，至今仍然被公认为是解决从固定点出发到网络中的任意顶点的最短路径问题的较好的方法之一。 Dijkstra 算法的基本思想如下：
设置并逐步扩充一个集合S ，存放已求出其最短路径的顶点，则尚未确定最短路径的顶点集合是V-S 其中，V 为网中所有顶点集合。按最短路径长度递增的顺序逐个用V-S 中的顶点加到S 中，直到S 中包含全部顶点，而V-S 为空。 Dijkstra 算法的具体步骤；
（1）设源点为V 1，则S 中只包含顶点V 1，令W=V-S ，则W 中包含除V 1外图中所有顶点。V 1对应的
距离值为0，即D[1]=0。W 中顶点对应的距离值是这样规定的：若图中有弧1k v ,v <>，则V j 顶点的距离为此弧权值，否则为∞（一个无穷大的数）； （2）从W 中选择一个其距离值最小的顶点k v ，并加入到S 中；
（3）每往S 中加入一个顶点k v 后，就要对W 中各个顶点的距离值进行一次修改。若加进k V 做中间
顶点，使1k v ,v <>+k j v ,v <>的值小于1j v ,v <>值，则用1k v ,v <>+k j v ,v <>代替原来j v 的距离值；
（4）重复步骤2和3，即在修改过的W 中的选距离值最小的顶点加入到S 中，并修改W 中的各个顶
点的距离值，如此进行下去，知道S 中包含图中所有顶点为之，即S=V 。这是D[N]就是从1v 到
N v 的最短路径长度值。
2.2.2 Floyd 算法
Floyd 算法是由计算机科学家Floyd 提出的，该算法能够求得任意顶点之间的最短路径。 Floyd 算法的基本思想是：
任意2个顶点i v 到j v 的距离的带权邻接矩阵开始，每次插入一个顶点k v ，然后将i v 到j v 间的已知最短路径与插入顶点k v 作为中间顶点时可能产生的i v 到j v 路径距离比较，取较小值以得到新的距离矩阵．如此循环迭代下去，依次构造出N 个矩阵)
1(D ,D
（2）
,…,(n)
D
，当所有的顶点均作为
任意 2个顶点i v 到j v 中间顶点时得到的最后的带权邻接矩阵(n)
D 就反映了所有顶点对之间的最短距离信息，成为图G 的距离矩阵。 构造图G 的距离矩阵：
设G 是n 个顶点的图，且其顶点用从1到n 的整数编号。
（1）把G 的带权邻接矩阵D 作为距离矩阵的初值，即)
0(D
=(0)ij n n d )?（=D 。当两点之间有边时，ij d （0）
等于边的权；当两点之间没有边时，ij d （0）记为无穷大；当i=j 时，ij d （0）
=0.
（2）构造)
1(D =(1)ij n n d )?（，其中ij d （1）=min （ij d （0）,ij d （0）
+ij d (0)）是从i v 到j v 的只允许以1v 作为
中间点的路径中最短路的长度。 （3）继续构造(k)
D
，其中2≤k ≤n ，其中k ij d （）=min （(k 1)ij
d -,(k 1)
ik d -+(k 1)kj d -）是从i v 到j v 的只允许以1v 、2v 、… 、k v 作为中间点的路径中最短路的长度。 （4）这时图G 的距离矩阵(n)D 就构造出来了。
3 应用举例
3.1 Dijkstra 算法在公交网络中的应用
在纷繁复杂的城市公交网中，如果想寻找到一条从当前某个站点到达另一个目的站点的最短路
径应该怎样实现呢？针对这个问题采用图论中最短路径的思想进行了思考和研究，并采用Dijkstra 算法来实现搜寻计算操作和过程。
3.1.1 实际问题描述
公交网络中最短路径问题可以描述为从某起始站点S 出发到达目的站点E 其中S 和E 之间可行的线路往往不只一条，而是有很多条，那么这么多可行的线路中哪一条是最短的呢？这里的“最短”是指实际走过的路程最短，或指在不计算公交换乘所花费时间和公车保持匀速行驶的前提下，能够以最短的时间到达目的地中的“最短”。要求解这个问题如果不考虑其它各方面的复杂因素，就可以看成是一个简单的最短路径问题。
3.1.2 数学模型建立
起始站点、目的站点以及所有的可行路径和中间站点所构成的交通网络，可以抽象为一个图状的数据模型——有向带权图记为G=(V,E,L)，其中V 表示所有站点的集合，假设共有N 个站点；E
表示所有直接通路或直通边的集合，假设共有M条直通边，注意，在实际应用中，这里的边是有方向性的，边的方向表示该直接通路的可行方向；L表示每条直接通路所对应的边权集合，即每条直通边所对应的距离值或时间开销等。此图满足下面条件：（1）图G是一个简单图，不含环；（2）边权W具有非负性和可加性。
3.1.3 实际问题抽象化
经过上述的分析和建模，实际的最短路径问题可抽象为有向带权图中两顶点之间的最短路径问题。若能寻找出图中某个起始顶点到达另一个目的顶点的最短路径，也就可以得出在实际公交网络中该起始站点到达另一目的站点的最短路径。若计算出图中两顶点之间的最短路径长度为无穷大，则表示实际交通网络中两站点之间没有通路或者不可到达。
3.1.4 算法应用
假定现有一公交网络如图3.1所示。假设该网络中任意一对有直接通路的顶点间的通路都是双向可行的，则可以将其抽象为一个无向带权图，并且各相邻顶点间的直接距离如表3.1所示，现要求解的问题是：寻找从A点出发到达其他各顶点的最短路径。根据Dijkstra算法，可得出搜索过程和结果如表3.2所示，运用MATLAB编程的结果见附录。
图3.1 公交网络
从表3.2可以看出，从A点出发到达其它各顶点的最短路径，按递增顺序依次为A→C（2km），A→B（3km），A→C→D（4km），A→C→E（5km），A→C→D→F（7km），A→C→E→F→G（11km）。
在实际应用中如果只是为了寻找两个指定顶点之间的最短路径，则可以给每个顶点赋予一个未访问标号（F）或已访问标号（T）。F表示从起始点到目的点之间还未找到最短路径，T表示从起始点到目的点之间已找到最短路径。这样每一次计算的目的是为了找到某个顶点将其F标号变成T标号，一旦目的顶点的标号变成T，则表示已寻找到从起始点到目的点之间的最短路径搜寻计算过程即可停止。例如，在上述实例中，如果只需求解从A点到达E点的最短路径，则搜寻会在A点、C 点、B点、D点、E点的标号依次变成T之后结束，即 E点标号变成T后表示到达E点的最短路径已找到。
表3.1 无向图的边权列表
表3.2 最短路径算法的搜索过程和结果
小结：
若寻找从起始点到其他所有顶点的最短路径，按照Dijkstra算法则最多需要经过N-1步的搜寻计算操作（N表示G中的顶点个数）。在实际应用中，Dijkstra算法也称为单源点最短路径算法。事实上，Dijkstra最短路径算法除了可以用在公交网络上之外，还可以用在现实生活的很多方面，如邮政线路、物流线路、管道布线等，我们还可以不断地将其推广使用到更多方面，从而使数学与计算机科学能够更充分地为人类服务。
3.2 Floyd 算法在物流中心选址的应用
物流中心的选址问题是整个物流运输网络的关键所在，它涉及到运输路线的选择与规划，而运输线路的长短直接影响着物流的费用。在分析物流网络的基础上，将图论中的Floyd算法应用于物流中心的选址上，以最少物流费用为最优目标。
3.2.1 问题描述与数学建模
在物流中心的选址问题中，点表示可供选择的配送中心，而其间的连线(边)则表示物流费用。这种由顶点、边和某些数量指标组成的图，是客观世界的多层次、多结构、多序列在人脑中的一种反映，能形象、清晰地描述空间中的位置关系，可以定量处理许多问题。运用图论中的有关理论和方法解决配送中心选址问题具有一定的实际意义。下面通过MATLAB程序实现Floyd选址算法。3.2.2 实际问题抽象化
在某城市建立物流配送网络，包含八个地方，则可将物流配送网络简化为有8个顶点的图，各点之间的物流费用如图3.2所示，试对该物流配送网络选择最佳的物流中心。
图3.2 物流网络
3.2.3 算法应用
（1） 运用Floyd 算法构造距离矩阵(n)
D ，其中d(i,j)表示i 到j 的最短距离。
①输入带权邻接矩阵W ，赋初值：对所有i ，j, d(i,j) ←w(i,j),r(i,j)←j,k ←1;
②更新d(i,j),r(i,j)：对所有i ，j ，若d(i,j)+d(i,k) ③若k=n,停止；否则k ←k+1,转回②。 如图所示，首先，确定矩阵) 0(D ，其中若顶点i v 到j v 有边相连，则）（0ij d 等于该边边权，否则） （0ij d = ∞而） （0ii d =0。有图可写出其初始带权邻接矩阵) 0(D ，然后对k=1,2,3,…,n 依次利用算法原理 中第n 步递归公式，由己知的) 1(D -n 各元素确定) (D n 的各元素值。 （2） 计算各顶点作为物流中心时的总费用n i ij j 1 C(v )d == ∑。 ①赋初值：对所有i ，C(i)←0; ②更新C(i)：对所有i ，j ，C(i)←C(i)+d(i,j)； ③若i=n ，停止，否则i ←i+1,转②。 （3）求出顶点使k v ，C(i v )=1i n min ≤≤{C(i v )}，则k v 就是最优的物流中心顶点。 ①赋初值：minC ←0，minK ←1，k ←1， ②更新最小费用minC ，并确定最优顶点minK ：对所有k ，若C(k)<=minC ，则minC ←C(k)，minK ←k ； ③若k=n ，停止，否则k ←k+1，并转②。 结果分析： 经过程序运行求出了i V 到其他各点的物流费用和为C(1V )=66，C(2V )=42，C(3V )=60，C(4V )=47, C(5V )=64，C(6V )=78，C(7V )=97，C(8V )=68。比较可知，如下图，2V 到其他各点的费用最小。因此，2V 选为物流中心是最优的。 图3.3 i V 到其它各点的物流费用的总和比较图 小结： Floyd 最短路径算法是用矩阵的思想来解决任意两点之间的最短距离。它最重要也最明显的应用就是在多个地址中找到一个合理的物流中心，由最终计算得出的距离矩阵可知：矩阵中元素ij a 的值表示从顶点i v 到j v 的最短距离；矩阵中第i 行所有元素之和就是顶点i v 到其它所有顶点距离和的最小值。Floyd 算法在物流运输中的应用，能够降低成本，优化物流网络。 参考文献 [1] 严蔚敏，吴伟民．数据结构[M]．北京：清华大学出版社，2002 [2] 李春葆，曾慧，张植民．数据结构程序设计题典[M]．北京：清华大学出版社，2002 [3] 张永，李睿，年福忠．算法与数据结构[M]．北京：国防工业出版社，2008 [4] 刘玉龙．数据结构与算法实用教程[M]．北京：电子工业出版社，2007 [5] 徐俊明．图论及其应用[M]．合肥：中国科学技术大学出版社，2004 [6] 曹晓东，原旭．离散数学及算法[M]．北京：机械工业出版社，2007 [7] 刘琛．计算机算法引论——设计与分析技术[M]．北京：科学出版社，2003 [8] 殷剑宏，吴开亚．图论及其算法[M]．合肥：中国科学技术大学出版社，2003 [9] 李春葆，尹为民等编．数据结构教程[M]，第二版．北京：清华大学出版社，2007 [10] 李春葆．数据结构习题与解析[M]，第二版．北京：清华大学出版社，2003 [11] 傅彦，顾小丰等编．离散数学及其应用[M]．北京：高等教育出版社，2007 [12] 冯桂莲．基于Dijkstra算法的最短路径的实现[J]．青海大学学报，2007，21(2)：98~102 [13] 项荣武．图论中最短路径问题的解法[J]．沈阳航空工业学院学报，2004，21(2)：86~88 [14] 胡桔州．Floyd最短路径算法在配送中心选址中的应用[J]．湖南农业大学学报，2004，30(4)： 382~384 [15] Yan Weimin, Wu Weimin. Data Structure [M]. Beijing: Tsinghua University Press, 1997 [16] E.W.Dijkstra. A note on two problems in connexion with graphs http://www-m3.ma.tum.de/foswiki/pub/MN0506/WebHome/dijkstra.pdf [17] F.Benjamin Zhan. Three fastest path algorithms on real road networks: Data structures and procedures http://publish.uwo.ca/~jmalczew/gida_1/Zhan/Zhan.htm#Introduction 附录 Dijkstra算法应用在公交网络中的源代码 clear; clc; M=10000; a(1,:)=[0,3,2,5,M,M,M]; a(2,:)=[zeros(1,2),2,M,4,5,M]; a(3,:)=[zeros(1,3),2,3,7,M]; a(4,:)=[zeros(1,4),5,6,10]; a(5,:)=[zeros(1,5),2,7]; a(6,:)=[zeros(1,6),4]; a(7,:)=zeros(1,7); a=a+a'; pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a)); d(1:length(a))=M;d(1)=0;temp=1; while sum(pb) tb=find(pb==0); d(tb)=min(d(tb),d(temp)+a(temp,tb)); tmpb=find(d(tb)==min(d(tb))); temp=tb(tmpb(1)); pb(temp)=1; index1=[index1,temp]; index=index1(find(d(index1)==d(temp)-a(temp,index1))); if length(index)>=2 index=index(1); end index2(temp)=index; end index1, index2,d 运行结果； index1 = 1 3 2 4 5 6 7 index2 = 1 1 1 3 3 5 6 d = 0 3 2 4 5 7 11 Floyd算法应用在物流中心选址问题的源代码 clear; clc; w=[0 6 inf 8 inf 13 6 inf; %初始矩阵 6 0 inf 2 5 7 inf 5; inf inf 0 3 9 inf 12 inf; 8 2 3 0 4 inf inf 7; inf 5 9 4 0 10 inf inf; 13 7 inf inf 10 0 inf 8; 6 inf 12 inf inf inf 0 inf; inf 5 inf 7 inf 8 inf 0]; [a,a]=size(w); %初始矩阵的大小 for k=1:a w_(:,:,k)=w; end k=1; for i=1:a for j=1:a if w_(i,j,k)>=w(i,k)+w(k,j) w_(i,j,k)=w(i,k)+w(k,j); %如果两点间距离大于w(i,1)+w(1,j),将后者取值赋给前者 end end end for k=2:a w_(:,:,k)=w_(:,:,k-1); for i=1:a for j=1:a if w_(i,j,k)>=w_(i,k,k-1)+w_(k,j,k-1) w_(i,j,k)=w_(i,k,k-1)+w_(k,j,k-1); %只允许以1、2……k-1作为中间点的路径中最短的路径 end end end end w_ k=a; result=zeros(1,a); result=(sum(w_(:,:,k),2)).' %对其进行行向量相加，为求出各行之和的最小值做准备i=1:a; stem(i,result) %画图，通过图形可以得到各行之和的最小值 axis([0,9,0,110]); m=min(result) %该值为最佳配送值 运行结果 D为： 初始矩阵)0( w=[0 6 Inf 8 Inf 13 6 Inf; 6 0 Inf 2 5 7 Inf 5; Inf Inf 0 3 9 Inf 12 Inf; 8 2 3 0 4 Inf Inf 7; Inf 5 9 4 0 10 Inf Inf; 13 7 Inf Inf 10 0 Inf 8; 6 Inf 12 Inf Inf Inf 0 Inf; Inf 5 Inf 7 Inf 8 Inf 0]; w_(:,:,1) = 0 6 Inf 8 Inf 13 6 Inf 6 0 Inf 2 5 7 12 5 Inf Inf 0 3 9 Inf 12 Inf 8 2 3 0 4 21 14 7 Inf 5 9 4 0 10 Inf Inf 13 7 Inf 21 10 0 19 8 6 12 12 14 Inf 19 0 Inf Inf 5 Inf 7 Inf 8 Inf 0 w_(:,:,2) = 0 6 Inf 8 11 13 6 11 6 0 Inf 2 5 7 12 5 Inf Inf 0 3 9 Inf 12 Inf 8 2 3 0 4 9 14 7 11 5 9 4 0 10 17 10 13 7 Inf 9 10 0 19 8 6 12 12 14 17 19 0 17 11 5 Inf 7 10 8 17 0 w_(:,:,3) = 0 6 Inf 8 11 13 6 11 6 0 Inf 2 5 7 12 5 Inf Inf 0 3 9 Inf 12 Inf 8 2 3 0 4 9 14 7 11 5 9 4 0 10 17 10 13 7 Inf 9 10 0 19 8 6 12 12 14 17 19 0 17 11 5 Inf 7 10 8 17 0 w_(:,:,4) = 0 6 11 8 11 13 6 11 6 0 5 2 5 7 12 5 11 5 0 3 7 12 12 10 8 2 3 0 4 9 14 7 11 5 7 4 0 10 17 10 13 7 12 9 10 0 19 8 6 12 12 14 17 19 0 17 11 5 10 7 10 8 17 0 w_(:,:,5) = 0 6 11 8 11 13 6 11 6 0 5 2 5 7 12 5 11 5 0 3 7 12 12 10 8 2 3 0 4 9 14 7 11 5 7 4 0 10 17 10 13 7 12 9 10 0 19 8 6 12 12 14 17 19 0 17 11 5 10 7 10 8 17 0 w_(:,:,6) = 0 6 11 8 11 13 6 11 6 0 5 2 5 7 12 5 11 5 0 3 7 12 12 10 8 2 3 0 4 9 14 7 11 5 7 4 0 10 17 10 13 7 12 9 10 0 19 8 6 12 12 14 17 19 0 17 11 5 10 7 10 8 17 0 w_(:,:,7) = 0 6 11 8 11 13 6 11 6 0 5 2 5 7 12 5 11 5 0 3 7 12 12 10 8 2 3 0 4 9 14 7 11 5 7 4 0 10 17 10 13 7 12 9 10 0 19 8 6 12 12 14 17 19 0 17 11 5 10 7 10 8 17 0 w_(:,:,8) = 0 6 11 8 11 13 6 11 6 0 5 2 5 7 12 5 11 5 0 3 7 12 12 10 8 2 3 0 4 9 14 7 11 5 7 4 0 10 17 10 13 7 12 9 10 0 19 8 6 12 12 14 17 19 0 17 11 5 10 7 10 8 17 0 result = 66 42 60 47 64 78 97 68 m = 42 致谢 光阴似箭，转眼间，四年的大学生活即将随着这篇论文的答辩而结束了，依依不舍之情难以言表，也有许许多多的感谢要说。 首先，要特别感谢我的论文指导老师孙志敏老师。她平日里工作繁多，但该论文从选题、构思、到最后定稿的各个环节，孙老师都给予了细心的指导和不懈的支持。从她身上，我深切地感受到了一个学者的严谨和务实，这些都让我获益匪浅，并且将终生受用无穷。在此，谨向孙老师表示崇高的敬意和衷心的感谢！ 另外，还要感谢所有教育过我的老师们！尤其是数计学院的老师，他们知识渊博，阅历丰富，讲课独具风格，是他们开启了我对数学的兴趣，激发了我对知识的渴望．他们孜孜不倦的给予我指导和帮助，教会我为人处事；他们传授的知识是我不断成长的源泉，也是完成本论文的基础。同时，感谢07数学全体同学在这大学四年里对我学习、生活上的帮助、信任和支持。四年里，我们共同成长，共同进步，在一起共同经历了很多快乐和难忘的时光。在这里，我祝愿我的每一位同学在以后的人生道路上一路走好！ 感谢多年来一直给予我鼎力支持和无私奉献的父母和弟弟．没有他们的付出与关爱，我的学业就谈不上顺利完成，真心地感谢和祝福他们！ 在此我对所有关心和支持我的人再次表示感谢，谢谢你们！四年时光转瞬即逝，然而这短暂时光的点点滴滴都将是我生命中的美好回忆．在今后新的征程中，无论面临多大的困难，我都将怀抱着感激、怀抱着情谊、怀抱着责任、怀抱着期望和梦想，坚定、自信地走下去。 摘要：主要介绍最短路径问题中的经典算法——迪杰斯特拉(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 算法描述 :算法的设计思想 本算法采用分支定界算法实现。构造解空间树为：第一个城市为根结点，与第一个城市相邻的城市为根节点的第一层子节点，依此类推；每个父节点的子节点均是和它相邻的城市；并且从第一个根节点到当前节点的路径上不能出现重复的城市。 本算法将具有最佳路线下界的节点作为最有希望的节点来展开解空间树，用优先队列实现。算法的流程如下：从第一个城市出发，找出和它相邻的所有城市，计算它们的路线下界和费用，若路线下界或费用不满足要求，将该节点代表的子树剪去，否则将它们保存到优先队列中，并选择具有最短路线下界的节点作为最有希望的节点，并保证路径上没有回路。当找到一个可行解时，就和以前的可行解比较，选择一个较小的解作为当前的较优解，当优先队列为空时，当前的较优解就是最优解。算法中首先用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 最短路径算法—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) 两个指定顶点之间的最短路径 问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。 以各城镇为图G 的顶点，两城镇间的直通铁路为图G 相应两顶点间的边，得图G 。对G 的每一边e ，赋以一个实数)(e w —直通铁路的长度，称为e 的权，得到赋权图G 。G 的子图的权是指子图的各边的权和。问题就是求赋权图G 中指定的两个顶点00,v u 间的具最小权的轨。这条轨叫做00,v u 间的最短路，它的权叫做00,v u 间的距离，亦记作),(00v u d 。 求最短路已有成熟的算法：迪克斯特拉（Dijkstra ）算法，其基本思想是按距0u 从近到远为顺序，依次求得0u 到G 的各顶点的最短路和距离，直至0v （或直至G 的所有顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法。 (i) 令0)(0=u l ，对0u v ≠，令∞=)(v l ，}{00u S =，0=i 。 (ii) 对每个i S v ∈（i i S V S \=），用 )}()(),({min uv w u l v l i S u +∈ 代替)(v l 。计算)}({min v l i S v ∈，把达到这个最小值的一个顶点记为1+i u ，令}{11++=i i i u S S 。 (iii). 若1||-=V i ，停止；若1||- 最短路径之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）的最短路径。线上所标注为相邻线段之间的距离，即权值。（注：此图为随意所画，其相邻顶点间的距离与图中的目视长度不能一一对等） 5.3.4 附录E 最短路径算法——Dijkstra 算法 在路由选择算法中都要用到求最短路径算法。最出名的求最短路径算法有两个，即Bellman-Ford 算法和Dijkstra 算法。这两种算法的思路不同，但得出的结果是相同的。我们在下面只介绍Dijkstra 算法，它的已知条件是整个网络拓扑和各链路的长度。 应注意到，若将已知的各链路长度改为链路时延或费用，这就相当于求任意两结点之间具有最小时延或最小费用的路径。因此，求最短路径的算法具有普遍的应用价值。 令v 部分： 不直接相连与结点若结点 1 v ? ?∞在用计算机进行求解时，可以用一个比任何路径长度大得多的数值代替∞。对于上述例子， 可以使D (v ) = 99。 (2) 寻找一个不在N 中的结点w ，其D (w )值为最小。把w 加入到N 中。然后对所有不在N 中的结点v ，用[D (v ), D (w ) + l (w , v )]中的较小的值去更新原有的D (v )值，即： D (v )←Min[D (v ), D (w ) + l (w , v )] (E-1) (3) 重复步骤(2)，直到所有的网络结点都在N 中为止。 表E-1是对图E-1的网络进行求解的详细步骤。可以看出，上述的步骤(2)共执行了5次。表中带圆圈的数字是在每一次执行步骤(2)时所寻找的具有最小值的D (w ) 值。当第5次执行步骤(2)并得出了结果后，所有网络结点都已包含在N 之中，整个算法即告结束。 表E-1 计算图E-1的网络的最短路径 现在我们对以上的最短路径树的找出过程进行一些解释。 因为选择了结点1为源结点，因此一开始在集合N中只有结点1。结点1只和结点2, 3和4直接相连，因此在初始化时，在D(2)，D(3)和D(4)下面就填入结点1到这些结点相应的距离，而在D(5)和D(6)下面填入∞。 下面执行步骤1。在结点1以外的结点中，找出一个距结点1最近的结点w，这应当是w = 4，因为在D(2)，D(3)和D(4)中，D(4) = 1，它的之值最小。于是将结点4加入到结点集合N中。这时，我们在步骤1这一行和D(4)这一列下面写入①，数字1表示结点4到结点1的距离，数字1的圆圈表示结点4在这个步骤加入到结点集合N中了。 接着就要对所有不在集合N中的结点（即结点2, 3, 5和6）逐个执行（E-1）式。 对于结点2，原来的D(2) = 2。现在D(w) + l(w, v) = D(4) + l(4, 2) = 1 + 2 = 3 > D(2)。因此结点2到结点1距离不变，仍为2。 对于结点3，原来的D(3) = 5。现在D(w) + l(w, v) = D(4) + l(4, 3) = 1 + 3 = 4 < D(3)。因此结点3到结点1的距离要更新，从5减小到4。 对于结点5，原来的D(5) = ∞。现在D(w) + l(w, v) = D(4) + l(4, 5) = 1 + 1 = 2 < D(5)。因此结点5到结点1的距离要更新，从∞减小到2。 对于结点6，现在到结点1的距离仍为∞。 步骤1的计算到此就结束了。 下面执行步骤2。在结点1和4以外的结点中，找出一个距结点1最近的结点w。现在有两个结点（结点2和5）到结点1的距离一样，都是2。我们选择结点5（当然也可以选择结点2，最后得出的结果还是一样的）。以后的详细步骤这里就省略了，读者可以自行完 1的路由表。此路由表指出对于发往某个目的结点的分组，从结点1发出后的下一跳结点（在算法中常称为“后继结点”）和距离。当然，像这样的路由表，在所有其他各结点中都有一个。但这就需要分别以这些结点为源结点，重新执行算法，然后才能找出以这个结点为根的最短路径树和相应的路由表。 最短路径问题的算法分析及建模案例 最短路径问题的算法分析及建模案例 一.摘要 (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算法的改进错误！未定义书签。 摘要 近年来计算机发展迅猛，图论的研究也得到了很大程度的发展，而最短路径 问题一直是图论中的一个典型问题，它已应用在地理信息科学，计算机科学等 诸多领域。而在交通路网中两个城市之间的最短行车路线就是最短路径问题的 一个典型例子。 由于最短路径问题在各方面广泛应用，以及研究人员对最短路径的深入研究， 使得在最短路径问题中也产生了很多经典的算法。在本课题中我将提出一些最 短路径问题的算法以及各算法之间的比较，最后将这些算法再应用于实际问题 第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/9816366028.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 条最短路径问题,即不但要求得到最短路径,还要得到次短、再次短等路径.这称之为广义最短路径问题. 计算最短路径的Dijkstra算法的编程实现 实验环境: C++ 为了进行网络最短路径路径分析，需将网络转换成有向图。如果要计算最短路径，则权重设置为两个节点的实际距离，Dijkstra算法可以用于计算从有向图中任意一个节点到其他节点的最短路径。 算法描述： 1）用带权的邻接矩阵来表示带权的n个节点的有向图，road[i][j]表示弧< vertex i, vertex j>的权值，如果从vertex i到vertex j不连通，则road road[i][j]=无穷大=9999。引进一个辅助向量Distance，每个Distance[i]表示从起始点到终点vertex i的最短路径长度。设起始点为first，则Distance[i]= road[first][i]。令S为已经找到的从起点出发的最短路径的终点的集合。 2）选择vertex j使得Distance[j]=Min{ Distance[i]| vertexi∈V-S},vertex j就是当前求得的一条从起始点出的的最短路径的终点的，令S=S∪{ vertex j} 3）修改从起始点到集合V-S中任意一个顶点vertex k的最短路径长度。如果Distance[j]+ road[j][k]< Distance[k]，则修改Distance[k]为：Distance[k]= Distance[j]+ road[j][k]。 4）重复2,3步骤操作共n-1次，由此求得从起始点出发到图上各个顶点的最短路径长度递增的序列。 算法复杂度为O(n2)。 程序代码如下： #include 课程设计任务书 目录 第1章概要设计 (1) 1.1题目的内容与要求 (1) 1.2总体结构 (1) 第2章详细设计 (2) 2.1主模块 (2) 2.2构建城市无向图 (3) 2.3添加城市 (4) 2.4修改城市距离 (5) 2.5求最短路径 (6) 第3章调试分析 (7) 3.1调试初期 (7) 3.2调试中期 (7) 3.3调试末期 (7) 第4章测试及运行结果 (7) 附页（程序清单） (10) 第1章概要设计 1.1题目的内容与要求 内容：给出一张无向图，图上的每个顶点表示一个城市，顶点间的边表示城市间存在路径，边上的权值表示城市间的距离。试编写程序求解从某一个城市出发到达任意其他任意城市的最短路径问题。 要求： 1)能够提供简单友好的用户操作界面，可以输入城市的基本信息，包括城市名 称，城市编号等； 2)利用矩阵保存城市间的距离； 3)利用Floyd算法求最短路径； 4)独立完成系统的设计，编码和调试； 5)系统利用C语言完成； 6)按照课程设计规范书写课程设计报告。 1.2总体结构 本程序主要分为四个模块（功能模块见图1.1）：主模块对整个程序起一主导作用，开始构建一城市无向图，对其进行添加城市顶点，以及对原来的距离数据进行修改，整体构建结束可以实现求一城市到其他城市的最短路径问题。 图1.1 功能模块图 第2章详细设计 2.1主模块 用户根据屏幕上显示的操作提示输入要进行操作的模块，通过调用相对应的模块程序，达到用户所想进行操作。程序的总框架大致分为四个模块：1.建立城市无向图2.添加城市模块3.修改城市距离4.求最短路径。具体实现过程见2.2：建立城市无向图2.3：添加城市2.4：修改城市距离2.5：求最短路径。流程图中通过输入n，由n的值来选择调用相对应子函数，实现所选择的功能，调用完后可以返回调用主函数进行下一次选择，从而实现反复调用子函数而实现四个模块的功能等。 图2.1 主模块流程图 地图中最短路径的搜索算法研究 学生:李小坤导师：董峦 摘要：目前为止, 国内外大量专家学者对“最短路径问题”进行了深入的研究。本文通过理论分析, 结合实际应用，从各个方面较系统的比较广度优先搜索算法(BFS)、深度优先搜索算法(DFS)、A* 算法的优缺点。 关键词:最短路径算法；广度优先算法；深度优先算法；A*算法； The shortest path of map's search algorithm Abstract:So far, a large number of domestic and foreign experts and scholars on the" shortest path problem" in-depth study. In this paper, through theoretical analysis and practical application, comprise with the breadth-first search algorithm ( BFS ), depth-first search algorithm ( DFS ) and the A * algorithms from any aspects of systematic. Key words: shortest path algorithm; breadth-first algorithm; algorithm; A * algorithm; 前言： 最短路径问题是地理信息系统（GIS）网络分析的重要内容之一，而且在图论中也有着重要的意义。实际生活中许多问题都与“最短路径问题”有关, 比如: 网络路由选择, 集成电路设计、布线问题、电子导航、交通旅游等。本文应用深度优先算法，广度优先算法和A*算法，对一具体问题进行讨论和分析，比较三种算的的优缺点。 在地图中最短路径的搜索算法研究中，每种算法的优劣的比较原则主要遵循以下三点:[1] (1)算法的完全性：提出一个问题，该问题存在答案，该算法能够保证找到相应的答案。算法的完全性强是算法性能优秀的指标之一。 (2)算法的时间复杂性: 提出一个问题，该算法需要多长时间可以找到相应的答案。算法速度的快慢是算法优劣的重要体现。 (3)算法的空间复杂性:算法在执行搜索问题答案的同时，需要多少存储空间。算法占用资源越少，算法的性能越好。 地图中最短路径的搜索算法: 1、广度优先算法 广度优先算法(Breadth-First-Search)，又称作宽度优先搜索，或横向优先搜索，是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型,Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽 中南大学 《数据结构》课程设计 题目第9题 Dijkstra算法求最短路径 学生姓名 XXXX 指导教师 XXXX 学院信息科学与工程学院 专业班级 XXXXXXX 完成时间 XXXXXXX 目录 第一章问题分析与任务定义---------------------------------------------------------------------3 1.1 课程设计题目-----------------------------------------------------------------------------3 1.2 原始数据的输入格式--------------------------------------------------------------------3 1.3 实现功能-----------------------------------------------------------------------------------3 1.4 测试用例-----------------------------------------------------------------------------------3 1.5 问题分析-----------------------------------------------------------------------------------3 第二章数据结构的选择和概要设计------------------------------------------------------------4 2.1 数据结构的选择--------------------------------------------------------------------------4 2.2 概要设计-----------------------------------------------------------------------------------4 第三章详细设计与编码-----------------------------------------------------------------------------6 3.1 框架的建立---------------------------------------------------------------------------------6 3.2 点结构体的定义---------------------------------------------------------------------------7 3.3 创立带权值有向图------------------------------------------------------------------------8 3.4 邻接矩阵的显示---------------------------------------------------------------------------9 3.5 递归函数的应用---------------------------------------------------------------------------10 3.6 Dijkstra算法实现最短路径--------------------------------------------------------------10 第四章上机调试------------------------------------------------------------------------------------11 4.1 记录调试过程中错误和问题的处理---------------------------------------------------11 4.2 算法的时间课空间性能分析------------------------------------------------------------11 4.3 算法的设计、调试经验和体会---------------------------------------------------------11 第五章测试结果-----------------------------------------------------------------------------------12 第六章学习心得体会-----------------------------------------------------------------------------12 第七章参考文献-----------------------------------------------------------------------------------12 附录------------------------------------------------------------------------------------------------------12 数据结构与算法课程实验报告实验四：图的相关算法应用 姓名：王连平 班级：09信科2班 学号：I09630221 实验四图的相关算法应用 一、实验内容 求有向网络中任意两点之间的最短路。 二、实验目的 掌握图和网络的定义，掌握图的邻接矩阵、邻接表和十字链表等存储表示。掌握图的深度和广度遍历算法，掌握求网络的最短路的标号法和floyd算法。 三、问题描述 对于下面一张若干个城市以及城市间距离的地图，从地图中所有可能的路径中求出任意两个城市间的最短距离及路径，给出任意两个城市间的最短距离值及途径的各个城市。 四、问题的实现 4.1数据结构的抽象数据类型定义和说明 1） typedef struct ArcCell{//储存弧信息 int Distance; ArcCell *info;//此项用来保存弧信息，，在本实验中没有相关信息要保存 }ArcCell,AdjMatrix[ MAX_VERTEX_NUM][ MAX_VERTEX_NUM]; typedef struct{//储存顶点信息 string vexs[ MAX_VERTEX_NUM];//顶点向量 AdjMatrix arcs;//邻接矩阵 int vexnum , arcnum;//图的当前顶点数和弧数 }MGraph; 顶点信息和弧信息都是用来建立一个有向网G 2） d[v][w];//G中各对顶点的带权长度 若P[v][w][u]为TRUE，则u是从v到w当前求得最短路径上的顶点 4.2主要的实现思路 首先通过一个函数（CreateDN）建立图的邻接矩阵储存方式,一次输入某条弧的起点，终点，和权值。通过调用Locate函数来找到该弧在邻接矩阵中的相应位置。 其次运用弗洛伊德算法来求各定点的最短路劲，具体思路为：如果从v到w有弧，则存在一条长度为arcs[v][w]的路径，该路径不一定是最短路径。考虑路径（v,u,w）是否存在，若存在，比较（v,w）和（v,u,w）的长度，取较短者为从v到w的中间点序号不大于0的最短路径。以此类推，每次增加一个点，从而求出任意两点间的最短路径。这样，经过n次比较后，所求得的必为从v到w的最短路径。按此方法，可以同时求得任意两点间的最短路径。 五、主要源程序代码（包含程序备注） #include 单源最短路径的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 //-------------------------------------数据声明------------------------------------------------//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; for (int i = 1; i < n; i++)最短路径学年论文
最短路径流程图及算法详解
最短路径算法—dijkstra总结
最短路径的Dijkstra算法及Matlab程序
gis计算最短路径的Dijkstra算法详细讲解
Dijkstra算法
最短路径问题的算法分析及建模案例
前N条最短路径问题的算法及应用
计算最短路径的Dijkstra算法的编程实现
弗洛伊德算法求解最短路径
地图中最短路径的搜索算法研究综述 (1)
数据结构课程设计报告Dijkstra算法求最短路径
实验四图的最短路径弗洛伊德算法实现
单源最短路径的Dijkstra算法
相关主题
文本预览