最短路径算法及其应用.doc

湖北大学本科毕业论文（设计）湖 北 大 学本 科 毕 业 论 文 （设 计）题 目 最短路径算法及其应用 姓 名 学 号 专业年级 指导教师 职 称 2011年 4月 20 日III目 录绪论(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 applicationsAbstract 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 pathDijkstra 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组成的一个数据结构，记为，其中：（1）是有限的顶点集合，称为顶点，简称点，V称为顶点集。（2）E是有限集合，称为边集。E中每个元素都有V中的顶点与之对应，称之为边。定义1 无向图和有向图如果连接某两个不同顶点间的边是有方向的，则称该边为有向边。有向边用有序对表示，其中表示源点，表示终点。如果图G的所有边都是有向边，则称图G为有向图。如果连接某两个不同顶点间的边是没有方向的，则称该边为无向边。无向边用无序对表示，边和边代表同一条边。如果图G中的所有边都是无向边，则称图G为无向图。15定义2 邻接点与邻接边在图中，若两个顶点和是一条边的端点，则称这两个顶点互为邻接点，否则与称为不邻接的。类似地，具有公共顶点的两条边称为邻接边。定义3 度有向图入度:有向图中以顶点为终点的边的数目，称为顶点的入度。出度:有向图中以顶点为源点的边的数目，称为顶点的出度。无向图无向图中，与顶点相关连的边的个数为顶点的度。定义4 路径在无向图中，从顶点到的一条路径是一个顶点序列 (,)，称为从顶点到的一条路径。如果是有向图，则路径也是有向的，路径的长度是指路径上的边或弧的数目。如果序列中第一个顶点和最后一个顶点相同的路径称为回路或环。如果序列中顶点不重复出现的路径称为简单路径。定义5 连通在无向图G中，如果从顶点到顶点有路径存在，则称和是连通的。若图中任意两个顶点都连通的无向图称为连通图。在有向图中如果从顶点到顶点有路径存在，则称到是连通的。若图中的每一对顶点都连通的有向图称为强连通图。定义6 权与网如果图的边或弧具有与之相关的数，则这种与连接顶点和的边或弧相关的数就称为边或弧的权。带权的图就称为网。权可以用来描述从一个顶点到另一个顶点的距离或耗费。如果把道路交通网中的道路起点、终点和交叉口表示为顶点，把道路表示威连接顶点的弧，把道路的长度、通行时间等属性表示为道路的权，那么道路网就被抽象成为带权的图，而与之相关的问题就可以利用图论的方法进行分析。1.2 图的存储结构图的存储结构除了要存储图中各个顶点本身的信息外，同时还要存储顶点与顶点之间的所有关系（边的信息）。常用的图的存储结构有邻接矩阵、邻接表、十字邻接表和邻接多重表。由于本文主要用到第一种，故只介绍第一种。1.2.1 邻接矩阵的表示邻接矩阵是表示顶点之间相邻关系的矩阵。设，是具有n（n大于0）个顶点的图，顶点的顺序依次为（,），则G的邻接矩阵A是n阶方阵，其定义如下：Aij= 若G是网，则邻接矩阵可定义为：Aij= 邻接矩阵定义如下：int adjmatrix =Arraynn。邻接矩阵的数据类型定义如下：#define MAXV / /最多顶点个数typedef struct vertex int num; / /顶点编号char data; / /顶点的信息VertexType；typedf stuctint n,e; / /顶点个数，边的条数VertexType vexsMAXV; / /顶点集合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之间是否有弧相连。2 最短路径问题所谓最短路径即是从图G中某对顶点和()之间的所有路径中选出权值之和最短的一条路径作为顶点到顶点的最短路径。其中边的权值可多种，比如路途、费用、耗时等，也可以是同时存在多种权值，根据给定的比例，算出边的综合权值。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，则S中只包含顶点V，令W=V-S，则W中包含除V外图中所有顶点。V对应的距离值为0，即D1=0。W中顶点对应的距离值是这样规定的：若图中有弧，则V顶点的距离为此弧权值，否则为（一个无穷大的数）；（2）从W中选择一个其距离值最小的顶点，并加入到S中；（3）每往S中加入一个顶点后，就要对W中各个顶点的距离值进行一次修改。若加进做中间顶点，使+的值小于值，则用+代替原来的距离值；（4）重复步骤2和3，即在修改过的W中的选距离值最小的顶点加入到S中，并修改W中的各个顶点的距离值，如此进行下去，知道S中包含图中所有顶点为之，即S=V。这是DN就是从到的最短路径长度值。2.2.2 Floyd算法Floyd算法是由计算机科学家Floyd提出的，该算法能够求得任意顶点之间的最短路径。Floyd算法的基本思想是：任意2个顶点到的距离的带权邻接矩阵开始，每次插入一个顶点，然后将到间的已知最短路径与插入顶点作为中间顶点时可能产生的到路径距离比较，取较小值以得到新的距离矩阵如此循环迭代下去，依次构造出N个矩阵,，当所有的顶点均作为任意 2个顶点到中间顶点时得到的最后的带权邻接矩阵就反映了所有顶点对之间的最短距离信息，成为图G的距离矩阵。构造图G的距离矩阵：设G是n个顶点的图，且其顶点用从1到n的整数编号。（1）把G的带权邻接矩阵D作为距离矩阵的初值，即=D。当两点之间有边时， 等于边的权；当两点之间没有边时，记为无穷大；当i=j时，=0.（2）构造=，其中=min（,+）是从到的只允许以作为中间点的路径中最短路的长度。（3）继续构造，其中2kn，其中=min（,+）是从到的只允许以、 、作为中间点的路径中最短路的长度。（4）这时图G的距离矩阵就构造出来了。3 应用举例3.1 Dijkstra算法在公交网络中的应用在纷繁复杂的城市公交网中，如果想寻找到一条从当前某个站点到达另一个目的站点的最短路径应该怎样实现呢？针对这个问题采用图论中最短路径的思想进行了思考和研究，并采用Dijkstra算法来实现搜寻计算操作和过程。3.1.1 实际问题描述公交网络中最短路径问题可以描述为从某起始站点S出发到达目的站点E其中S和E之间可行的线路往往不只一条，而是有很多条，那么这么多可行的线路中哪一条是最短的呢？这里的“最短”是指实际走过的路程最短，或指在不计算公交换乘所花费时间和公车保持匀速行驶的前提下，能够以最短的时间到达目的地中的“最短”。要求解这个问题如果不考虑其它各方面的复杂因素，就可以看成是一个简单的最短路径问题。3.1.2 数学模型建立起始站点、目的站点以及所有的可行路径和中间站点所构成的交通网络，可以抽象为一个图状的数据模型有向带权图记为，其中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点出发到达其它各顶点的最短路径，按递增顺序依次为AC（2km），AB（3km），ACD（4km），ACE（5km），ACDF（7km），ACEFG（11km）。在实际应用中如果只是为了寻找两个指定顶点之间的最短路径，则可以给每个顶点赋予一个未访问标号（F）或已访问标号（T）。F表示从起始点到目的点之间还未找到最短路径，T表示从起始点到目的点之间已找到最短路径。这样每一次计算的目的是为了找到某个顶点将其F标号变成T标号，一旦目的顶点的标号变成T，则表示已寻找到从起始点到目的点之间的最短路径搜寻计算过程即可停止。例如，在上述实例中，如果只需求解从A点到达E点的最短路径，则搜寻会在A点、C点、B点、D点、E点的标号依次变成T之后结束，即 E点标号变成T后表示到达E点的最短路径已找到。表3.1 无向图的边权列表路段距离（km）路段距离（km）AB3CF7AC2DE5AD5DF6BC2DG10BE4EF2BF5EG7CD2FG4CE3表3.2 最短路径算法的搜索过程和结果步骤集合S源点到各个顶点的距离最小距离值待加入顶点DADBDCDEDEDFDG1A03252C2A,C0322+2=42+3=52+7=93B3A,C,B032453+5=84D4A,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最短路径算法除了可以用在公交网络上之外，还可以用在现实生活的很多方面，如邮政线路、物流线路、管道布线等，我们还可以不断地将其推广使用到更多方面，从而使数学与计算机科学能够更充分地为人类服务。3.2 Floyd 算法在物流中心选址的应用物流中心的选址问题是整个物流运输网络的关键所在，它涉及到运输路线的选择与规划，而运输线路的长短直接影响着物流的费用。在分析物流网络的基础上，将图论中的Floyd算法应用于物流中心的选址上，以最少物流费用为最优目标。3.2.1 问题描述与数学建模在物流中心的选址问题中，点表示可供选择的配送中心，而其间的连线(边)则表示物流费用。这种由顶点、边和某些数量指标组成的图，是客观世界的多层次、多结构、多序列在人脑中的一种反映，能形象、清晰地描述空间中的位置关系，可以定量处理许多问题。运用图论中的有关理论和方法解决配送中心选址问题具有一定的实际意义。下面通过MATLAB程序实现Floyd选址算法。3.2.2 实际问题抽象化 在某城市建立物流配送网络，包含八个地方，则可将物流配送网络简化为有8个顶点的图，各点之间的物流费用如图3.2所示，试对该物流配送网络选择最佳的物流中心。图3.2 物流网络3.2.3 算法应用（1） 运用Floyd算法构造距离矩阵，其中d(i,j)表示i到j的最短距离。输入带权邻接矩阵W，赋初值：对所有i，j, d(i,j) w(i,j),r(i,j)j,k1;更新d(i,j),r(i,j)：对所有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,停止；否则kk+1,转回。 如图所示，首先，确定矩阵，其中若顶点到有边相连，则等于该边边权，否则=而=0。有图可写出其初始带权邻接矩阵，然后对k=1,2,3,n依次利用算法原理中第n步递归公式，由己知的各元素确定的各元素值。（2） 计算各顶点作为物流中心时的总费用。赋初值：对所有i，C(i)0;更新C(i)：对所有i，j，C(i)C(i)+d(i,j)；若i=n，停止，否则ii+1,转。（3）求出顶点使，C()=C()，则就是最优的物流中心顶点。赋初值：minC0，minK1，k1，更新最小费用minC，并确定最优顶点minK：对所有k，若C(k)=minC，则minCC(k)，minKk；若k=n，停止，否则kk+1，并转。结果分析：经过程序运行求出了到其他各点的物流费用和为C()=66，C()=42，C()=60，C()=47, C()=64，C()=78，C()=97，C()=68。比较可知，如下图，到其他各点的费用最小。因此，选为物流中心是最优的。图3.3 到其它各点的物流费用的总和比较图小结：Floyd最短路径算法是用矩阵的思想来解决任意两点之间的最短距离。它最重要也最明显的应用就是在多个地址中找到一个合理的物流中心，由最终计算得出的距离矩阵可知：矩阵中元素的值表示从顶点到的最短距离；矩阵中第i行所有元素之和就是顶点到其它所有顶点距离和的最小值。Floyd算法在物流运输中的应用，能够降低成本，优化物流网络。参考文献1 严蔚敏，吴伟民数据结构M北京：清华大学出版社，20022 李春葆，曾慧，张植民数据结构程序设计题典M北京：清华大学出版社，20023 张永，李睿，年福忠算法与数据结构M北京：国防工业出版社，20084 刘玉龙数据结构与算法实用教程M北京：电子工业出版社，20075 徐俊明图论及其应用M合肥：中国科学技术大学出版社，20046 曹晓东，原旭离散数学及算法M北京：机械工业出版社，20077 刘琛计算机算法引论设计与分析技术M北京：科学出版社，2003 8 殷剑宏，吴开亚图论及其算法M合肥：中国科学技术大学出版社，20039 李春葆，尹为民等编数据结构教程M，第二版北京：清华大学出版社，200710 李春葆数据结构习题与解析M，第二版北京：清华大学出版社，200311 傅彦，顾小丰等编离散数学及其应用M北京：高等教育出版社，200712 冯桂莲基于Dijkstra算法的最短路径的实现J青海大学学报，2007，21(2)：9810213 项荣武图论中最短路径问题的解法J沈阳航空工业学院学报，2004，21(2)：868814 胡桔州Floyd最短路径算法在配送中心选址中的应用J湖南农业大学学报，2004，30(4)：382384 15 Yan Weimin, Wu Weimin. Data Structure M. Beijing: Tsinghua University Press, 199716 E.W.Dijkstra. A note on two problems in connexion with graphshttp:/www-m3.ma.tum.de/foswiki/pub/MN0506/WebHome/dijkstra.pdf17 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)=2 index=index(1); end index2(temp)=index;end index1, index2,d运行结果；index1 = 1 3 2 4 5 6 7index2 = 1 1 1 3 3 5 6d = 0 3 2 4 5 7 11Floyd算法应用在物流中心选址问题的源代码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:aw_(:,:,k)=w;endk=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 endfor 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、2k-1作为中间点的路径中最短的路径 end end endendw_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) %该值为最佳配送值 运行结果初始矩阵为：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 0w_(:,:,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 0w_(:,:,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 0w_(:,:,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 0w_(:,:,5) = 0 6 11 8 11 13 6