最短路径算法及其应用

1、湖北大学本科毕业论文（设计）题 目最短路径算法及其应用姓 名 学 号专业年级指导教师 职 称2011年4月20日目录 TOC o 1-5 h z HYPERLINK l bookmark23 o Current Document 绪论(1) HYPERLINK l bookmark26 o Current Document 1图的基本概念(1) HYPERLINK l bookmark29 o Current Document 1.1图的相关定义(1) HYPERLINK l bookmark57 o Current Document 1.2图的存储结构(2) HYPERLINK l book

2、mark60 o Current Document 1.2.1邻接矩阵的表示(2) HYPERLINK l bookmark66 o Current Document 1.2.2邻接矩阵的相关结论(3) HYPERLINK l bookmark78 o Current Document 2最短路径问题(3) HYPERLINK l bookmark81 o Current Document 2.1最短路径(4) HYPERLINK l bookmark84 o Current Document 2.2最短路径算法(4) HYPERLINK l bookmark87 o Current Docu

3、ment 2.2.1Dijkstra 算法(4) HYPERLINK l bookmark94 o Current Document 2.2.2Floyd 算法(5) HYPERLINK l bookmark102 o Current Document 3应用举例(5) HYPERLINK l bookmark105 o Current Document Dijkstra算法在公交网络中的应用(5) HYPERLINK l bookmark108 o Current Document 3.1.1实际问题描述(5) HYPERLINK l bookmark111 o Current Docume

4、nt 3.1.2数学模型建立(5) HYPERLINK l bookmark114 o Current Document 3.1.3实际问题抽象化(6) HYPERLINK l bookmark117 o Current Document 3.1.4算法应用(6) HYPERLINK l bookmark120 o Current Document Floyd算法在物流中心选址的应用(7) HYPERLINK l bookmark124 o Current Document 1问题描述与数学建模(7) HYPERLINK l bookmark128 o Current Document 3.2

5、.2实际问题抽象化(7) HYPERLINK l bookmark131 o Current Document 3.2.3算法应用(8) HYPERLINK l bookmark146 o Current Document 参考文献(10) HYPERLINK l bookmark175 o Current Document 附录(11)最短路径算法及其应用最短路径算法的研究是计算机科学研究的热门话题，它不仅具有重要的理论意义，而且具有重 要的实用价值。最短路径问题有广泛的应用，比如在交通运输系统、应急救助系统、电子导航系统 等研究领域。最短路径问题又可以引申为最快路径问题、最低费用问题等，但

6、它们的核心算法都是 最短路径算法。经典的最短路径算法 ijkstra和Floyd算法是目前最短路径问题采用的理论基 础。本文主要对Dijkstra和Floyd算法进行阐述和分析，然后运用这两个算法解决两个简单的实际 问题。【关键字】最短路径 Dijkstra算法 Floyd算法 图论Shortest path algorithms and their applicationsAbstractThe research about the shortest path is a hot issue in computer science. It has both important theoreti

7、cal 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

8、their core algorithms are all both the shortest path algorithms. The classical algorithms for the shortest pathDijkstra and Floyd are the theoretical basis for solving the problems of the shortest path. Thearticle mainly through the demonstration and analysis of the Dijkstra and Floyd algorithms, th

9、en use the algorithms to solve the two simple practical problems.keywords shortest path Dijkstra algorithm Floyd algorithm graph绪论随着知识经济的到来，信息将成为人类社会财富的源泉，网络技术的飞速发展与广泛应用带动 了全社会对信息技术的需求，最短路径问题作为许多领域中选择最优问题的基础，在电子导航，交 通旅游，城市规划以及电力，通讯等各种管网，管线的布局设计中占有重要的地位。最短路径，顾名思义就是在所有的路径中找到一条距离最短的路径，而我们所说的最短路径通 常不仅仅指

10、地理意义的距离最短，还可以引申到其他的度量，如时间，费用，路线容量等。相应地， 最短路径问题就成为最快路径问题，最低费用问题等，所以我们所说的最短路径也可以看作是最优 路径问题。最短路径问题在交通网络结构的分析，交通运输路线（公路、铁路、河流航运线、航空线、管 道运输线路等）的选择，通讯线路的建造与维护，运输货流的最小成本分析，城市公共交通网络的 规划等，都有直接应用的价值。最短路径问题在实际中还常用于汽车导航系统以及各种应急系统等 （如110报警、119火警以及120医疗救护系统）这些系统一般要求计算出到出事地点的最佳路线 的时间应该在1s到3s内，在行车过程中还需要实时计算出车辆前方的行驶

11、路线，这就决定了最短 路径问题的实现应该是高效的。最短路径问题一直是计算机科学，运筹学，交通工程学，地理信息学等学科的一个研究热点。 经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。1图论基本概念图（graph）是一种较线性表和树更为复杂的数据结构，图与线性表和树的结构区别表现在结点之 间的关系上，线性表中的每个结点（除首尾结点外）都有一个前驱结点和一个后继结点，结点与结 点之间的关系是一对一的关系；树上的每个结点都有一个父结点（根结点除外）和一个或多个孩子 结点（叶子结点除外），结点与结点的关系是一对多的关系；而图中结点之间的关系是多对多的关系， 结点与

12、结点之间的连接是任意的，每对结点间可以有连接也可以没有连接。1.1图的相关定义图G是由一个非空的顶点集合V和一个描述顶点之间多对多关系的边集合E组成的一个数据结构，记为G = V,E ，其中：（1）V = v,v ,.,v 是有限的顶点集合，v称为顶点，简称点，V称为顶点集。12 ni（2）E是有限集合，称为边集。E中每个元素都有V中的顶点与之对应，称之为边。定义1无向图和有向图如果连接某两个不同顶点间的边是有方向的，则称该边为有向边。有向边用有序对 Vi，Vj 表示，其中Vi表示源点，匕表示终点。如果图G的所有边都是有向边，则称图G为有向图。如果连接某两个不同顶点间的边是没有方向的，则称该边

13、为无向边。无向边用无序对（Vi，Vj）表示，边（Vi,Vj）和边（Vj,Vi）代表同一条边。如果图G中的所有边都是无向边，则称图G为无向图。定义2邻接点与邻接边在图G =中，若两个顶点V_和七是一条边的端点，则称这两个顶点互为邻接点，否则V,与匕称为不邻接的。类似地，具有公共顶点的两条边称为邻接边。定义3度有向图入度:有向图中以顶点V,为终点的边的数目，称为顶点V,的入度。出度:有向图中以顶点V,为源点的边的数目，称为顶点V,的出度。无向图无向图中，与顶点V_相关连的边的个数为顶点V_的度。定义4路径在无向图G =中，从顶点% 到匕的一条路径是一个顶点序列（V,匕,v_2 ,., Vim,匕）

14、，称为从顶点%到匕的一条路径。如果是有向图，则路径也是有向的，路径的长度是指路径上的边或弧的数目。如果序列中第一个顶点和最后一个顶点相同的路径称为回路或环。如果序列中顶点不重复出现的路径称为简单路径。定义5连通在无向图G中，如果从顶点V_到顶点匕有路径存在，则称V_和匕是连通的。若图中任意两个顶点都连通的无向图称为连通图。在有向图中如果从顶点V到顶点匕有路径存在，则称%到匕是连通的。若图中的每一对顶点都连通的有向图称为强连通图。定义6权与网如果图的边或弧具有与之相关的数，则这种与连接顶点V,和%的边或弧相关的数W（V,Vj）就 称为边或弧的权。带权的图就称为网。权可以用来描述从一个顶点到另一个

15、顶点的距离或耗费。如果把道路交通网中的道路起点、终 点和交叉口表示为顶点，把道路表示威连接顶点的弧，把道路的长度、通行时间等属性表示为道路 的权，那么道路网就被抽象成为带权的图，而与之相关的问题就可以利用图论的方法进行分析。1.2图的存储结构图的存储结构除了要存储图中各个顶点本身的信息外，同时还要存储顶点与顶点之间的所有关 系（边的信息）。常用的图的存储结构有邻接矩阵、邻接表、十字邻接表和邻接多重表。由于本文主 要用到第一种，故只介绍第一种。1.2.1邻接矩阵的表示邻接矩阵是表示顶点之间相邻关系的矩阵。设G =，是具有n （n大于0）个顶点的图，顶点的顺序依次为（V0，V1，%），则G的邻接矩

16、阵A是n阶方阵，其定义如下:对于无向图（v ,v）e E，对于有向图 e Ei j其它情况若G是网，则邻接矩阵可定义为:I wI wAiu 2若(v ,v )或 ,v e Eijij其它情况邻接矩阵定义如下:int adjmatrix =Arraynn。邻接矩阵的数据类型定义如下: #define MAXV最大顶点个数 typedef struct vertex 邻接矩阵的数据类型定义如下: #define MAXV最大顶点个数 typedef struct vertex int num;char data;VertexType；typedf stuctint n,e;VertexType v

17、exsMAXV;int edgesMAXVMAXV;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

18、之间是否有弧相连。2最短路径问题所谓最短路径即是从图G中某对顶点Vi和Vj Aj）之间的所有路径中选出权值之和最短的一 条路径作为顶点V_到顶点Vj的最短路径。其中边的权值可多种，比如路途、费用、耗时等，也可以 是同时存在多种权值，根据给定的比例，算出边的综合权值。2.1最短路径在一个无权的图中，若从一个顶点到另一个顶点存在着一条路径，则称该路径长度为该路径上 所经过的边的数目，它等于该路径上的顶点数减1。由于从一个顶点到另一个顶点可能存在着多条 路径，每条路径上所经过的边数可能不同，即路径长度不同，把路径长度最短（即经过的边数最少） 的那条路径叫作最短路径或者最短距离。对于带权的图，考虑路径

19、上各边的权值，则通常把一条路径上所经边的权值之和定义为该路径 的路径长度或带权路径长度。从源点到终点可能不止一条路径，把带权路径长度最短的那条路径称 为最短路径，其路径长度（权值之和）称为最短路径长度或最短距离。实际上，只要把无权图上的每条边看成是权值为1的边，那么无权图和带权图的最短路径和最 短距离的定义是一致的。对于连接某对给定顶点的路径，可能有多条路径有相同的长度，因此最短路径问题的解不一定 是唯一的，它可能有多个满足约束条件的解。2.2最短路径算法求图中的最短路径有两方面的问题：求图中某一顶点到其余各顶点的最短路径与求图中每一对 顶点之间的最短路径。它们分别有Dijkstra算法和Fl

20、oyd算法，是目前两个比较著名的最短路径算法。2.2.1 Dijkstra 算法Dijkstra算法又称为标号法，是1959年由荷兰计算机科学家E.W.Dijkstra提出的关于最短路 径的搜索算法。该算法是用于求解单源点最短路径的实用算法，至今仍然被公认为是解决从固定点 出发到网络中的任意顶点的最短路径问题的较好的方法之一。Dijkstra算法的基本思想如下：设置并逐步扩充一个集合S，存放已求出其最短路径的顶点，则尚未确定最短路径的顶点集合 是V-S其中，V为网中所有顶点集合。按最短路径长度递增的顺序逐个用V-S中的顶点加到S中， 直到S中包含全部顶点，而V-S为空。Dijkstra算法的具

21、体步骤；（1）设源点为V 1，则S中只包含顶点V 1，令W=V-S，则W中包含除V1外图中所有顶点。V1对应的距离值为0，即D1=0OW中顶点对应的距离值是这样规定的：若图中有弧 v1,vk ，则Vj顶 点的距离为此弧权值，否则为8 （一个无穷大的数）；（2）从W中选择一个其距离值最小的顶点vk，并加入到、中；（3）每往S中加入一个顶点vk后，就要对W中各个顶点的距离值进行一次修改。若加进匕做中间顶点，使 v ,v + v ,v 的值小于 v ,v 值，则用 v ,v + v ,v 代替原来v的1 kk j1 j1 kk jj距离值；（4）重复步骤2和3,即在修改过的W中的选距离值最小的顶点加

22、入到、中，并修改W中的各个顶 点的距离值，如此进行下去，知道S中包含图中所有顶点为之，即S=V。这是DN就是从v1到 vN的最短路径长度值。Floyd 算法Floyd算法是由计算机科学家Floyd提出的，该算法能够求得任意顶点之间的最短路径。Floyd算法的基本思想是：任意2个顶点V到v的距离的带权邻接矩阵开始，每次插入一个顶点V，然后将V到v间的 i jki j已知最短路径与插入顶点vk作为中间顶点时可能产生的vi到Vj路径距离比较，取较小值以得到新的距离矩阵.如此循环迭代下去，依次构造出N个矩阵D(1), D，D(n)，当所有的顶点均作为任意2个顶点vi到vj中间顶点时得到的最后的带权邻接

23、矩阵D(n)就反映了所有顶点对之间的最短 距离信息，成为图G的距离矩阵。构造图G的距离矩阵：设G是n个顶点的图，且其顶点用从1到n的整数编号。把G的带权邻接矩阵D作为距离矩阵的初值，即D(0)=(d(0)nxn =DO当两点之间有边时，d(0)等于边的权；当两点之间没有边时，d(0)记为无穷大；当i=j时，d；0)=O.构造D=(d)，其中d(i)=min (d(。)，d(0)+ d.(0)是从v到v的只允许以v作为 TOC o 1-5 h z ij nxnijij ij iji j1中间点的路径中最短路的长度。继续构造D(k)，其中2WkWn，其中d(k)=min ( dd), d(k-1)

24、+ dd)是从v到v的只允ijij ik kji j许以V、V、V作为中间点的路径中最短路的长度。12k这时图G的距离矩阵。)就构造出来了。3应用举例3.1 Dijkstra算法在公交网络中的应用在纷繁复杂的城市公交网中，如果想寻找到一条从当前某个站点到达另一个目的站点的最短路 径应该怎样实现呢？针对这个问题采用图论中最短路径的思想进行了思考和研究，并采用Dijkstra 算法来实现搜寻计算操作和过程。3.1.1实际问题描述公交网络中最短路径问题可以描述为从某起始站点S出发到达目的站点E其中S和E之间可行 的线路往往不只一条，而是有很多条，那么这么多可行的线路中哪一条是最短的呢？这里的“最短”

25、 是指实际走过的路程最短，或指在不计算公交换乘所花费时间和公车保持匀速行驶的前提下，能够 以最短的时间到达目的地中的“最短”。要求解这个问题如果不考虑其它各方面的复杂因素，就可以 看成是一个简单的最短路径问题。3.1.2数学模型建立起始站点、目的站点以及所有的可行路径和中间站点所构成的交通网络，可以抽象为一个图状 的数据模型一一有向带权图记为G=(V,E,L)，其中V表示所有站点的集合，假设共有N个站点；E 表示所有直接通路或直通边的集合，假设共有M条直通边，注意，在实际应用中，这里的边是有方 向性的，边的方向表示该直接通路的可行方向；L表示每条直接通路所对应的边权集合，即每条直 通边所对应的

26、距离值或时间开销等。此图满足下面条件：（1）图G是一个简单图，不含环；（2）边 权W具有非负性和可加性。3.1.3实际问题抽象化经过上述的分析和建模，实际的最短路径问题可抽象为有向带权图中两顶点之间的最短路径问 题。若能寻找出图中某个起始顶点到达另一个目的顶点的最短路径，也就可以得出在实际公交网络 中该起始站点到达另一目的站点的最短路径。若计算出图中两顶点之间的最短路径长度为无穷大， 则表示实际交通网络中两站点之间没有通路或者不可到达。3.1.4算法应用假定现有一公交网络如图3.1所示。假设该网络中任意一对有直接通路的顶点间的通路都是双 向可行的，则可以将其抽象为一个无向带权图，并且各相邻顶点

27、间的直接距离如表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）o 在实际应用中如果只是为了寻找两个指定顶点之间的最短路径，则可以给每个顶点赋予一个未 访问标号（F）或已访问标号（T）。F表示从起始点到目的点之间还未找到最短路径，T表示从起始

28、 点到目的点之间已找到最短路径。这样每一次计算的目的是为了找到某个顶点将其F标号变成T标 号，一旦目的顶点的标号变成T，则表示已寻找到从起始点到目的点之间的最短路径搜寻计算过程 即可停止。例如，在上述实例中，如果只需求解从A点到达E点的最短路径，则搜寻会在A点、C 点 B点、D点、E点的标号依次变成T之后结束，即E点标号变成T后表示到达E点的最短路径已 找到。表3.1无向图的边权列表路段距离（km）路段距离（km）AB3CF7AC2DE5AD5DF6BC2DG10BE4EF2BF5EG7CD2FG4CE3表3.2最短路径算法的搜索过程和结果步骤集合S源点到各个顶点的距离最小距离值待加入顶点DA

29、DBDCDEDEDFDG1A03258882C2A,C0322+2=42+3=52+7=983B3A,C,B032453+5=884D4A,C,B,D0324584+10=145E5A,C,B,D,E032455+2=75+7=127F6A,C,B,D,E,F0324577+4=1111G7A,C,B,D,E,F,G03245711小结：若寻找从起始点到其他所有顶点的最短路径，按照Dijkstra算法则最多需要经过N-1步的搜寻 计算操作（N表示G中的顶点个数）。在实际应用中，Dijkstra算法也称为单源点最短路径算法。事 实上，Dijkstra最短路径算法除了可以用在公交网络上之外，还可以

30、用在现实生活的很多方面，如 邮政线路、物流线路、管道布线等，我们还可以不断地将其推广使用到更多方面，从而使数学与计 算机科学能够更充分地为人类服务。Floyd算法在物流中心选址的应用物流中心的选址问题是整个物流运输网络的关键所在，它涉及到运输路线的选择与规划，而运 输线路的长短直接影响着物流的费用。在分析物流网络的基础上，将图论中的Floyd算法应用于物 流中心的选址上，以最少物流费用为最优目标。1问题描述与数学建模在物流中心的选址问题中，点表示可供选择的配送中心，而其间的连线（边）则表示物流费用。 这种由顶点、边和某些数量指标组成的图，是客观世界的多层次、多结构、多序列在人脑中的一种 反映，

31、能形象、清晰地描述空间中的位置关系，可以定量处理许多问题。运用图论中的有关理论和 方法解决配送中心选址问题具有一定的实际意义。下面通过MATLAB程序实现Floyd选址算法。3.2.2实际问题抽象化在某城市建立物流配送网络，包含八个地方，则可将物流配送网络简化为有8个顶点的图，各点 之间的物流费用如图3.2所示，试对该物流配送网络选择最佳的物流中心。图3.2物流网络3.2.3算法应用运用Floyd算法构造距离矩阵D(n)，其中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):对

32、所有 i，j，若 d(i,j)+d(i,k)d(i,j),则 d(i,j) d(i,j)+d(i,k), r(i,j) k；若k=n，停止；否则k k+1,转回。如图所示，首先，确定矩阵D(。)，其中若顶点v .到 v .有边相连，则d(0)等于该边边权，否则d(0)二1 jijij8而d；o)=O。有图可写出其初始带权邻接矩阵D(。)，然后对k=1,2,3,n依次利用算法原理中第n步递归公式，由己知的D(-1)各元素确定D(n)的各元素值。计算各顶点作为物流中心时的总费用C(v) = d。iijj=1赋初值：对所有i，C(i) 0;更新 C(i)：对所有 i，j，C(i) C(i)+d(i,

33、j)；若i=n，停止，否则i i+1,转。求出顶点使v，C( V ) = min C( V )，则v就是最优的物流中心顶点。ki1inik赋初值：minC 0， minK 1， k 1，更新最小费用minC，并确定最优顶点minK:对所有k,若C(k)=minC，则minC C(k), minK k；若k=n，停止，否则k J k+1，并转。结果分析：经过程序运行求出了 V到其他各点的物流费用和为 C( V1 )=66, C( V2 )=42, C( V3 )=60，C(V )=47, C(V )=64，C(V )=78，C(V )=97, C(V )=68。比较可知，如下图，V 到其他各点的

34、图3.3 *到其它各点的物流费用的总和比较图小结：Floyd最短路径算法是用矩阵的思想来解决任意两点之间的最短距离。它最重要也最明显的应 用就是在多个地址中找到一个合理的物流中心，由最终计算得出的距离矩阵可知：矩阵中元翱功的 值表示从顶点v,到Vj的最短距离；矩阵中第i行所有元素之和就是顶点v_到其它所有顶点距离和的 最小值。Floyd算法在物流运输中的应用，能够降低成本，优化物流网络。参考文献严蔚敏，吴伟民.数据结构M.北京：清华大学出版社，2002李春葆，曾慧，张植民.数据结构程序设计题典M.北京：清华大学出版社，2002张永，李睿，年福忠.算法与数据结构M.北京：国防工业出版社，2008

35、刘玉龙.数据结构与算法实用教程M.北京：电子工业出版社，2007徐俊明.图论及其应用M.合肥：中国科学技术大学出版社，2004曹晓东，原旭.离散数学及算法M.北京：机械工业出版社，2007刘琛.计算机算法引论一一设计与分析技术M.北京：科学出版社，2003殷剑宏，吴开亚.图论及其算法M.合肥：中国科学技术大学出版社，2003李春葆，尹为民等编数据结构教程M，第二版.北京：清华大学出版社，2007李春葆.数据结构习题与解析M，第二版.北京：清华大学出版社，2003傅彦，顾小丰等编.离散数学及其应用M.北京：高等教育出版社，2007冯桂莲.基于Dijkstra算法的最短路径的实现J.青海大学学报，

36、2007，21(2)： 98102项荣武.图论中最短路径问题的解法J.沈阳航空工业学院学报，2004, 21(2)： 8688胡桔州.Floyd最短路径算法在配送中心选址中的应用J.湖南农业大学学报，2004, 30(4): 382384Yan Weimin, Wu Weimin. Data Structure M. Beijing: Tsinghua University Press, 1997E.W.Dijkstra. A note on two problems in connexion with graphs HYPERLINK http:/www-m3.ma.tum.de/foswi

37、ki/pub/MN0506/WebHome/dijkstra.pdf http:/www-m3.ma.tum.de/foswiki/pub/MN0506/WebHome/dijkstra.pdfF.Benjamin Zhan. Three fastest path algorithms on real road networks: Data structures and procedures HYPERLINK http:/publish.uwo.ca/jmalczew/gida_1/Zhan/Zhan.htm%23Introduction http:/publish.uwo.ca/jmalc

38、zew/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,l

39、ength(a);d(1:length(a)=M;d(1)=0;temp=1;while sum(pb)=2index=index(1); endindex2(temp)=index;end index1, index2,d运彳丁结果；indexl =1324567index2 =1113356d =03245711Floyd算法应用在物流中心选址问题的源代码clear;clc;w=06inf8inf136in%初始矩阵60inf257inf5;infinf039inf12inf;82304infinf7;inf594010infinf;137infinf100inf8;6inf12infin

40、finf0inf;inf5inf7inf8inf0;a,a=size(w); %初始矩阵的大小for k=1:aw_(:,:,k)=w;endk=1;for i=1:afor j=1:aif 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),将后者取值赋给前者 endendendfor k=2:aw_(:,:,k)=w_(:,:,k-1);for i=1:afor j=1:aif 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,

41、k-1);%只允许以1、2k-1作为中间点的路径中最短的路径 endendendendw_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（o）为:w=06Inf8Inf136Inf;60Inf257Inf5;InfInf039Inf12Inf;82304InfInf7;Inf594010InfInf;137InfInf100Inf8;6Inf12InfInfInf0Inf;Inf5Inf7Inf8Inf0;06Inf8Inf136Inf60Inf257125InfInf039