邮局订阅号：８２－９４６３６０元／年技术创新
软件时空
《ＰＬＣ技术应用２００例》
您的论文得到两院院士关注
随着计算机网络技术和地理信息科学的发展，最短路径问题无论是在交通运输，还是在城市规划、
物流管理、网络通讯等方面，它都发挥了重要的作用。因此，对它的研究不但具有重要的理论价值，而且具有重要的应用价值。
研究最短路径问题通常将它们抽象为图论意义下的网络问题，问题的核心就变成了网络图中的最短路径问题。此时的最短路径不单指“纯距离”意义上的最短路径，它可以是“经济距离”意义上的最短路径，“
时间”意义上的最短路径，“网络”意义上的最短路径。关于最短路径问题，目前所公认的最好的求解方法，是由Ｆ．Ｗ．Ｄｉｊｋｓｔｒａ提出的标号法，即Ｄｉｊｋｓｔｒａ算法。
１Ｄｉｊｋｓｔｒａ算法
Ｄｉｊｋｓｔｒａ算法是求最短路径的最基本和使用最广泛的算法。在求从网络中的某一节点（源点）到其余各节点的最短路径时，经典Ｄｉｊｋｓｔｒａ算法将网络中的节点分成三部分：未标记节点、临时标记节点和最短路径节点（永久标记节点）。算法开始时
源点初始化为最短路径节点，其余为未标记节点，算法执行过程中，每次从最短路径节点往相邻节点扩展，非最短路径节点的相邻节点修改为临时标记节点，判断权值是否更新后，在所有临时标记节点中提取权值最小的节点，修改为最短路径节点后作为下一次的扩展源，再重复前面的步骤，当所有节点都做过扩展源后算法结束。具体算法描述如下：
设在一非负权简单连通无向图Ｇ＝＜Ｖ，Ｅ，Ｗ＞（Ｖ：顶点集，Ｅ：边集，Ｗ：边权值）中，ｄ为图Ｇ的邻接矩阵，求源点Ｐ０到其余所有节点Ｐｉ的最短路径长度。
⑴将Ｖ分为未标记节点子集Ｎ、
临时最短路径节点子集Ｔ和最短路径节点子集Ｓ，每个节点上的路径权值为Ｄ（ｉ）。初始化：Ｓ＝｛Ｐ０｝，Ｔ＝￠
，Ｎ＝Ｖ－Ｓ，Ｄ（０）＝０，Ｄ（ｉ）＝∞；⑵更新：将新加入Ｓ集合的节点Ｐｓ作为扩展源，计算从扩展源到相邻节点的路径值。若该值比节点上的原值小，则用该值替换原值，否则保持原值不变，即Ｄ（ｉ）＝ｍｉｎ｛Ｄ（ｓ）＋ｄ［ｓ］［ｉ］，Ｄ（ｉ）｝，并将这些相邻节点之中的未标记节点归为临时标记节点，即
Ｔ＝Ｔ∪Ｐｉ，Ｎ＝Ｎ－Ｐｉ；
⑶选择：在Ｔ中选择具有最小路径值Ｄ（ｓ）的节点Ｐｓ，归入集合Ｓ中，即Ｓ＝Ｓ∪Ｐｓ，Ｔ＝Ｔ－Ｐｓ；
⑷迭代判断：若Ｔ＝￠
算法结束，否则转⑵。该算法总共需要迭代ｎ－１次，每次迭代都新加一个节点到临时节点集合中，由于第ｉ次迭代时不在临时节点集合中的节点数为ｎ－ｉ，即第ｉ次迭代需对ｎ－ｉ个节点进行处理，因此其所
需的处理数为，对ｎ个节点网络的时间复杂
度是Ｏ（ｎ２）。
２Ｄｉｊｋｓｔｒａ算法的优化途径及常用优
化算法
在按标记法实现Ｄｉｊｋｓｔｒａ算法的过程中，核心步骤就是从未标记的点中选择一个权值最小的弧段。这是一个循环比较的过程，如果不采用任何措施，未标记点将以无序的形式存放在一个链表或数组中。那么要选择一个权值最小的弧段就必须把所有的点都扫描一遍，在大数据量的情况下，这无疑是一个制约计算速度的瓶颈。解决办法就是将临时标记结点按照最短路径排序，每个搜索过程不必全部遍历或者较少地遍历临时标记点，可大大提高算法的执行效率。
这是目前各种基于Ｄｉｊｋｓｔｒａ算法的各种优化算法的主要途径。另外，图的结构（网络的拓扑关系）如果用一个矩阵来表示这个网络，不但所需空间巨大，而且效率会很低。下面将就如何用一个简洁高效的结构表示网的拓扑关系以及快速搜索技术的实现进行讨论。
Ｄｉｊｋｓｔｒａ最短路径算法的优化及其实现
ＴｈｅｏｐｔｉｍｉｚａｔｉｏｎａｎｄＩｍｐｌｅｍｅｎｔａｔｉｏｎｏｆｔｈｅＳｈｏｒｔｅｓｔＰａｔｈＤｉｊｋｓｔｒａＡｌｇｏｒｉｔｈｍ
（１．湖南人文科技学院；２．长沙学院计算机教学中心）王志和
１
凌云
２
ＷＡＮＧＺＨＩＨＥＬＩＮＧＹＵＮ
摘要：最短路径分析在地理信息系统、计算机网络路由等方面发挥了重要的作用，对其进行优化很有必要。本文分析了传统的最短路径算法（即Ｄｉｊｋｓｔｒａ算法）的优化途径及现有的优化算法，然后在Ｄｉｊｋｓｔｒａ算法的基础上，采用配对堆结构来实现路径计算过程中优先级队列的一系列操作，经理论分析与实验测试结果对比，可以大大提高该算法的效率和性能。关键词：最短路径；Ｄｉｊｋｓｔｒａ算法；优化；配对堆
中图分类号：ＴＰ３０１．６
文献标识码：ＡＡｂｓｔｒａｃｔ：Ｔｈｅｓｈｏｒｔｅｓｔｐａｔｈａｎａｌｙｓｉｓｉｎａｓｐｅｃｔａｎｄｓｏｏｎｇｅｏｇｒａｐｈｉｃｉｎｆｏｒｍａｔｉｏｎｓｙｓｔｅｍ，ｃｏｍｐｕｔｅｒｎｅｔｗｏｒｋｒｏｕｔｅｈａｓｐｌａｙｅｄｔｈｅｖｉｔａｌ
ｒｏｌｅ，ｃａｒｒｉｅｓｏｎｔｈｅｏｐｔｉｍｉｚａｔｉｏｎｔｏｉｔｔｏｈａｖｅｔｈｅｎｅｃｅｓｓｉｔｙｖｅｒｙｍｕｃｈ．Ｔｈｉｓｐａｐｅｒａｎａｌｙｓｅｓｔｈｅｏｐｔｉｍａｌｗａｙａｎｄｔｈｅｎｏｗａｖａｉｌａｂｌｅｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍｔｈｅｔｒａｄｉｔｉｏｎａｌｓｈｏｒｔｅｓｔｐａｔｈａｌｇｏｒｉｔｈｍ（ｉ．ｅ．Ｄｉｊｋｓｔｒａａｌｇｏｒｉｔｈｍ），ａｎｄａｃｈｉｅｖｅｓａｓｅｒｉｅｓｏｆｏｐｅｒａｔｉｏｎａｌｐｒｉｏｒｉｔｙｑｕｅｕｅｉｎｐａｔｈｃｏｍｐｕｔａｔｉｏｎｐｒｏｃｅｓｓｕｓｉｎｇＰａｉｒｅｄｈｅａｐｂａｓｅｄｏｎＤｉｊｋｓｔｒａａｌｇｏｒｉｔｈｍ，ｂｙｔｈａｔｔｈｅｏｒｅｔｉｃａｌａｎａｌｙｓｉｓａｎｄｔｈｅｅｘｐｅｒｉｍｅｎｔｔｅｓｔｒｅｓｕｌｔｃｏｎｔｒａｓｔ，ｅｆｆｉｃｉｅｎｃｙａｎｄｆｕｎｃｔｉｏｎｂｅｉｎｇａｂｌｅｔｏｉｍｐｒｏｖｅｔｈａｔａｌｇｏｒｉｔｈｍｇｒｅａｔｌｙ．Ｋｅｙｗｏｒｄｓ：ｔｈｅｓｈｏｒｔｅｓｔｐａｔｈ，Ｄｉｊｋｓｔｒａａｌｇｏｒｉｔｈｍ，ｏｐｔｉｍｉｚａｔｉｏｎ，ｐａｒｉｎｇｈｅａｐ
文章编号：１００８－０５７０（２００７）１１－３－０２７５－０３
王志和：讲师软件设计师硕士湖南省自然科学基金（０６ＪＪ５１３）湖南省教育厅科研项目（０６Ｃ４４１）２７５－
－
技
术创新
中文核心期刊《微计算机信息》（管控一体化）２００７年第２３卷第１１－３期
３６０元／年邮局订阅号：８２－９４６
《现场总线技术应用２００例》
软件时空
在此算法思想基础上，人们演绎出了几十种不同的优化算法。目前，对于算法中快速搜索技术的实现，主要有桶结构法、队列法以及堆实现法。ＴＱＱ、ＤＫＡ以及ＤＫＤ在这方面是比较典型的代表。ＴＱＱ是用两个ＦＩＦＯ的队列实现了一个双端队列结构来支持搜索过程，ＤＫＡ和ＤＫＤ是采用桶结构来支持搜索运算，３种算法将空间存储问题放在了一个重要的位置，以牺牲适当的时间效率来换取空间节省。从当前计算机硬件发展水平来看，空间存储问题已不是考虑的主要问题了，须进行改进。
在Ｄｉｊｋｓｔｒａ算法中，为了获得己经计算过距离中值最小的节点，一般采用一个可更新、可排序的优先队列来实现。如何实现Ｄｉｊｋｓｔｒａ算法的优先队列结构，成为提高Ｄｉｊｋｓｔｒａ算法性能的关键。标准的优先队列仅支持“插入（Ｉｎｓｅｒｔ）”、“
删除最小（Ｄｅｌｅｔｅ－Ｍｉｎ）”两种元素操作。但使用Ｄｉｊｋｓｔｒａ算法需要优先队列具备
“
降级（Ｄｅｃｒｅａｓｅ－Ｐｒｉｏｒｉｔｙ）”操作，能动态调整己排序队列中的元素。选择合适的数据结构实现可降级的优先队列可以有效地降低算法复杂度，减少算法执行时间。
为了降低优先队列的操作时间复杂度，一般采用堆结构来实现优先队列。常见的堆结构有：采用二叉堆（ｂｉｎａｒｙｈｅａｐ）的优先队列所有操作时间都是Ｏ（ｌｏｇＮ），Ｄｉｊｋｓｔｒａ算法的时间复杂度为Ｏ（ＥｌｏｇＶ）。Ｆｒｅｄｍａｎ和Ｔａｒｊａｎ提出的斐波那契堆（Ｆｉｂｏｎａｃｃｉ
ｈｅａｐ），其插入时间为Ｏ（ｌ），降级的摊还时间为Ｏ（ｌ），删除最小的摊还时间为Ｏ（ｌｏｇＮ），Ｄｉｊｋｓｔｒａ算法的时间复杂度为Ｏ（Ｅ＋Ｖ１ｏｇＶ），是实现优先队列的常用选择。
３使用配对堆的Ｄｉｊｋｓｔｒａ优化算法
根据上述优化原则和优化的描述，本文的Ｄｉｊｋｓｔｒａ算法采用一种新式堆结构———“配对堆（ｐａｉｒｉｎｇｈｅａｐ）”来实现优先队列。配对堆是一种比斐波那契堆简单，但性能却不低于它的数据结构。
３．１配对堆
配对堆是由配对堆节点组成。每个堆节点除了用于排序的元素外，包括前驱节点、
左儿子节点、右兄弟节点三个指针。为了支持“降级”操作，做为最左儿子节点的前驱节点指针将指向其父亲节点；否则这个节点就是一个右兄弟节点，其前驱节点指针将指向这个节点的左兄弟。如图１所示的是一个具体的配对堆。
图１一个配对堆的表示形式
堆节点的数据结构如下：
ｃｌａｓｓｐｎｏｄｅ
｛
ｐｕｂｌｉｃ：
ｐｎｏｄｅ（ＤａｔａＴｙｐｅＩｔｅｍ）
｛Ｅｌｅｍｅｎｔ＝Ｉｔｅｍ；Ｐｒｅｖ＝ＮＵＬＬ；
ＬｅｆｔＣｈｉｌｄ＝ＮｅｘｔＳｉｂｌｉｎｇ＝ＮＵＬＬ；｝
ＤａｔａＴｙｐｅＥｌｅｍｅｎｔ；／／堆节点保存的元素ｃｌａｓｓｐｎｏｄｅ＊Ｐｒｅｖ；／／前驱节点指针
ｃｌａｓｓｐｎｏｄｅ＊ＬｅｆｔＣｈｉｌｄ；／／左孩子节点指针ｃｌａｓｓｐｎｏｄｅ＊ＮｅｘｔＳｉｂｌｉｎｇ；／／右兄弟节点指针｝
配对堆的性质是：
（１）根节点具有整个堆最小值元素（针对最小值配对堆而言）；
（２）任何一个堆节点的元素值均小于等于其左儿子节点；（３）同一层次串联的兄弟没有大小顺序，但是均大于最左兄弟的父节点（此性质是由配对堆的“合并”操作决定的）。
以上三个性质决定了配对堆结构能够实现可降级的优先队列。
３．２配对堆的基本操作
配对堆的基本操作包括“合并”、“插入”、“降级”和“删除最小”四种。
合并（Ｍｅｒｇｅ）是把两个子堆合并成一个堆，它是后三种操作实现的基础。为了不失一般性，合并的第二个子堆可以是一个节点，也可以是具有右兄弟节点的子堆。合并的过程就是让具有较大根节点的子堆成为另一个子堆的最左的儿子。
插入（Ｉｎｓｅｒｔ）是为配对堆增加一个新元素。把新元素作为一个新的子节点，然后通过与堆根节点进行合并操作完成。“插入”是“合并”的特殊操作。
降级（Ｄｅｃｒｅａｓｅ－Ｐｒｉｏｒｉｔｙ）是改变一个堆节点的元素值。其过程是把需要改变值的节点连同儿子节点从堆中移出成为一个新子堆，然后把修改节点值后的子堆和旧子堆合并。
删除最小（ＤｅｌｅｔｅＭｉｎ）是个复杂的操作，它是从堆中移出最小的根节点。当把堆的根节点删去后，需要从原根节点的所有儿子节点中选取最小的节点成为新堆的根节点。最简单的方法是把所有儿子节点的关联打开成为若干子堆，再依次调用合并操作生成一个新的配对堆。另一种有效的方法称为“两趟合并法（ｔｗｏ－ｐａｓｓｍｅｒｇｉｎｇ）＂。其过程是：首先从左到右，将打开生成的
子堆每两两进行合井；然后再从右到左，依次合并剩余的子堆。例如，如果有６个子堆Ｘ１到Ｘ６，那么在第一合并的过程中，把Ｘ１和Ｘ２合并成Ｙ１，把Ｘ３和Ｘ４合并成Ｙ２，把Ｘ５和Ｘ６合并成Ｙ３。第二次合并，把Ｙ３和Ｙ２合并，再跟Ｙ１合并。“
删除最小”的操作方法有很多，主要目的就是为了使配对堆每个节点的儿子数尽可能的少，提高算法效率。
有关配对堆四种操作算法的实现过程可以参考文献。
３．３基于配对堆的Ｄｉｊｋｓｔｒａ算法
使用堆结构实现优先队列的最大问题是需要知道已访问的网络节点对应的堆节点指针，因为更改堆的操作都是直接操作堆节点指针完成。因此，需要一种网络节点与堆节点之间的快速访问方式。
在这里为每一个网络节点定义一个堆节点指针，但不预先申请内存。而是当算法遍历到对应节点时，动态生成堆节点。这样既保证了算法的执行效率，又减少了内存的浪费。其中，堆节点中保存了对应的网络节点、以及到网络节点花费等相关信息。另外，再以一个变量保存配对堆的根节点，以便于每次取出权值最小的节点。网络节点与配对堆节点的对应关系如图２所
２７６－
－
邮局订阅号：８２－９４６３６０元／年技术创新
软件时空
《ＰＬＣ技术应用２００例》
您的论文得到两院院士关注
示。在算法求出最终结果后，统一遍历网络节点并释放生成的堆节点内存空间。
图２网络节点与配对堆节点的对应关系
新的算法在原始Ｄｉｊｋｓｔｒａ算法的基础上，为每个网络节点增加了一个指向堆节点指针，在算法遍历到新节点时，需要构造配对堆节点，并动态更新配对堆。优化后的Ｄｉｊｋｓｔｒａ算法流程：
⑴输入起始节点信息；
⑵构造一个配对堆节点作为配对堆根节点，并加入起始节
点的指针关联；
⑶取出配对堆根节点中的节点信息，判断是否到达终止结点？若是则转入⑺；
⑷遍历当前节点的邻接节点，累加节点花费；
⑸邻接节点的配对堆节点是否为空，若是则生成一个配对
堆节点，加入当前遍历的邻接节点相关信息，建立节点与配对堆节点的指针关联；
⑹更新配对堆节点中的信息为当前节点和邻接节点花费最小的，并调整配对堆结构，再返回到⑶。
⑺根据终止节点对应的配对堆节点的信息返回结果路径，
并释放所有配对堆节点指针内存。
３．４算法复杂度分析与实验
使用配对堆实现Ｄｉｊｋｓｔｒａ算法的时间复杂度主要是由配对
堆的四种操作决定的。其中“合并”、“插入”、“降级”均在常量时间完成，复杂度是Ｏ（１）。“删除最小”操作最坏情况是根节点具有Ｎ－１个儿子节点。因此“删除最小”操作的最坏时间复杂度是Ｏ（Ｎ）。由于采用“
两趟合并法”需要对所有儿子节点进行“合并”操作，能够有效减少同一层次的兄弟节点数，因此降低了最坏情况发生机率。
表１各堆结构运行时间测试结果表
为了检验配对堆实现优先级队列的一系列操作后，对Ｄｉｊｋｓｔｒａ算法效率的影响，我们做了以下实验：采用较大规模的数据量，节点数Ｖ为Ｎ＝１００００００，边数Ｅ为Ｍ＝１０＊Ｎ，图的生成是先随机生成一个生成树（Ｎ－１条），再将剩下的（Ｍ－Ｎ＋１）条边随
机插入到生成树而构成图，然后分别用二叉堆、斐波那契堆和
配对堆来实现Ｄｉｊｋｓｔｒａ算法，计时采用ＧｅｔＴｉｃｋＣｏｕｎｔ（）
ｉｎＷｉｎｄｏｗｓｕｎｉｔ，测试环境为：ＶＣ＋＋６．０，操作系统为Ｗｉｎｘｐｓｐ２，ＣｅｎｔｒｉｎｏＭ１．８ＧＨｚ，５１２ＭＢＤＤＲ２，其测试结果如表１所示：
Ｐａｉｒｈｅａｐ的ＤｅｌｅｔｅＭｉｎ的复杂度分析是目前没有解决的问题，但从表１的实验测试结果来看，其运行时间比斐波那契堆和二叉堆还要小，可见其均摊的复杂度可能小于Ｏ（ｌｏｇＮ）。文献指出了它能达到同斐波那契堆相同的摊还时间界Ｏ（ｌｏｇＮ），因此使用配对堆实现Ｄｉｊｋｓｔｒａ算法的时间复杂度为Ｏ（Ｅ＋ＶｌｏｇＶ），其中Ｅ、Ｖ分别为图中边数和节点数。
在空间使用上，配对堆节点仅包括前驱节点、左儿子节点和右兄弟节点三个指针。对比斐波那契堆，其堆节点在实现上需要包括父节点、孩子节点、左节点、右节点四个指针，以及孩子节点个数和一个标记信息。配对堆的节点要比斐波那契堆节点节省一个指针、一个整型值和一个布尔值的内存空间。如果用指针记录堆节点的元素，那么在３２位机器中，使用配对堆的构造的优先队列比使用斐波那契堆要节省了３６％的内存空间。
４小结与本文作者的创新点
目前各种基于Ｄｉｊｋｓｔｒａ算法的各种优化算法的优化方法是将临时标记结点按照最短路径排序，每个搜索过程不必全部遍历或者较少地遍历临时标记点。本文在经典Ｄｉｊｋｓｔｒａ算法的基础上，利用配对堆数据结构管理网络节点，从中搜寻最短路径节点，经理论分析与实验测试结果对比，该方法可大大提高该算法的效率和性能。
参考文献
［１］王凌．智能优化算法及其应用［Ｍ］．北京：清华大学出版社，２００１．［２］（美）ＭａｒｋＡｌｌｅｎＷｅｉｓｓ著．冯舜玺译．数据结构与算法分析—Ｃ语言描述（第二版）［Ｍ］．北京：机械工业出版社，２００５．
［３］ＳｔａｓｋｏＪＴ，ＶｉｔｔｅｒＪＳ．Ｐａｉｒｉｎｇｈｅａｐｓ：ｅｘｐｅｒｉｍｅｎｔｓａｎｄａｎａｌｙｓｉｓ．ＣｏｍｍｕｎｉｃａｔｉｏｎｓｏｆｔｈｅＡＣＭ［Ｊ］，１９８７，３０（３）：２３４－２４９．
［４］胡永良，目的驱动最短路径树的快速算法［Ｊ］微计算机信息，２００６，３－３：２８５－２８７
作者简介：王志和（１９７２－），男，湖南双峰人，讲师，软件设计师，硕士，研究方向：软件工程和软件开发。
Ｂｉｏｇｒａｐｈｙ：ＷａｎｇＺｈｉｈｅ（１９７２－），Ｍａｌｅ，ＬｅｃｔｕｒｅｒｉｎＨｕｎａｎＩｎｓｔｉｔｕｔｅｏｆＨｕｍａｎｉｔｉｅｓ，ＭａｓｔｅｒＤｅｇｒｅｅ，ＲｅｓｅａｒｃｈＦｉｅｌｄｓ：ＳｏｆｔｗａｒｅＥｎｇｉｎｅｅｒｉｎｇａｎｄＳｏｆｔｗａｒｅＤｅｓｉｇｎ．
（４１７０００湖南娄底湖南人文科技学院数学系）王志和（４１０００３湖南长沙长沙学院计算机教学中心）凌云
（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃ，ＨｕｎａｎＩｎｓｔｉｔｕｔｅｏｆＨｕｍａｎｉｔｉｅｓ，ＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，Ｌｏｕｄｉ４１７０００，Ｃｈｉｎａ）ＷａｎｇＺｈｉＨｅ（ＣｏｍｐｕｔｅｒＴｅａｃｈｉｎｇＣｅｎｔｅｒ，ＣｈａｎｇｓｈａＵｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｓｈａ４１０００３，Ｃｈｉｎａ）ＬｉｎｇＹｕｎ
通讯地址：（４１７０００湖南省娄底市湖南人文科技学院数学系）
王志和
（收稿日期：２００７．８．０３）（修稿日期：２００７．１０．０５）
您的才能＋阅读本刊＝您的财富
２７７－
－
两个指定顶点之间的最短路径 问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。 以各城镇为图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||- 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发出后的下一跳结点（在算法中常称为“后继结点”）和距离。当然，像这样的路由表，在所有其他各结点中都有一个。但这就需要分别以这些结点为源结点，重新执行算法，然后才能找出以这个结点为根的最短路径树和相应的路由表。 计算最短路径的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 中南大学 《数据结构》课程设计 题目第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 最短路径之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算法，它的已知条件是整个网络拓扑和各链路的长度。 应注意到，若将已知的各链路长度改为链路时延或费用，这就相当于求任意两结点之间具有最小时延或最小费用的路径。因此，求最短路径的算法具有普遍的应用价值。 下面以图E-1的网络为例来讨论这种算法，即寻找从源结点到网络中其他各结点的最短路径。为方便起见，设源结点为结点1。然后一步一步地寻找，每次找一个结点到源结点的最短路径，直到把所有 点1, j)为结点i (1) 初始化 令N表示网络结点的集合。先令N = {1}。对所有不在N中的结点v，写出 不直接相连与结点若结点直接相连 与结点若结点 1 1 ),1()(v v v l v D ? ? ?∞= 在用计算机进行求解时，可以用一个比任何路径长度大得多的数值代替∞。对于上述例子，可以使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的网络的最短路径 #include Dijkstra算法求最短路径(C#版)行如下图的路径,(V0是中心): 经过该算法后转化为下图 using System; using System.Collections; using System.Text; namespace Greedy { class Marx { private int[] distance; private int row; private ArrayList ways = new ArrayList(); public Marx(int n,params int[] d) { this.row = n; distance = new int[row * row]; for (int i = 0; i < row * row; i++) { this.distance[i] = d[i]; } for (int i = 0; i < this.row; i++) //有row个点，则从中心到各点的路有row-1条 { ArrayList w = new ArrayList(); int j = 0; w.Add(j); ways.Add(w); } } //------------------------------ public void Find_way() { ArrayList S = new ArrayList(1); ArrayList Sr = new ArrayList(1); int []Indexof_distance=new int[this.row]; for(int i=0; i < row; i++) { Indexof_distance[i]=i; } S.Add( Indexof_distance[0] ); for (int i = 0; i < this.row; i++) { Sr.Add( Indexof_distance[i] ); } Sr.RemoveAt(0); int[] D = new int[this.row]; //存放中心点到每个点的距离 //---------------以上已经初始化了，S和Sr(里边放的都是点的编 利用Dijkstra算法计算最短路径 摘要 福格环游地球问题是一个十分典型的最短路径求解问题，题设给出了当时世界上主要交通网络图及交通通畅的城市之间来往所需时长，并限定了福格的出行方向（福格选择的是往东走），给出起止地点后要求找出福格环游世界天数最短的最佳路径。 我们认为，这个问题的实质在于最短路径的求解和优化。我们对比图论中的多种最短路径算法，决定利用Dijkstra算法解决这个问题。 由于Dijkstra算法要求输入图G的关联矩阵，且图G为二维赋权图，而题中给出的地图可看成是三维环状地图，因此，我们对题设地图做相关处理，将其从起点处“切断”并展开为二维图，然后根据此图建立关联矩阵。同时，我们考虑到最短路径可能会与切断线有交点，在切断线以西找出若干地点一分为二，修改关联矩阵。 对于题目中缺失的两处数据，本文将以当时的交通数据为基础，经过合理的数据处理，结合Google Earth测距软件与题目数据的合理类比，补充缺失数据，完成关联矩阵。 得到关联矩阵后，我们分别以伦敦、纽约和上海作为起点，调整关联矩阵起点和终点，用matlab编程进行求解得到最短环游时间和最短路径，进而判断出所选择的路径是否能让他赢得赌注。根据我们的求解结果，在这三个城市，福格均能在80天内环游地球，赢得赌注。 本文进一步对此种算法的优缺点、灵敏度与推广性进行了分析，同时初步提出了两种优化方法。 关键词：最短路径算法 dijkstra算法算法优化 一、问题重述 儒勒?凡尔纳的著名小说《环游世界80天》中，英国绅士福格在伦敦与人打赌能够在80天内环游世界，这在当时的1872年是一个了不起的壮举。当时最快的旅行方式是火车和轮船，然而世界上大部分地区还是靠马车、大象、驴子或者步行来旅行。下面是一个从伦敦环游世界不同路线的交通网络图，福格选择的是往东走，每段路线所需要的天数显示在图上（见附录一），旅行的时间基于1872年能采用的旅行方式以及距离。 我们将解决以下问题： 1．我们将设计一个算法为福格选择一条最佳路径，即环游世界天数最短，并判断所选择的路径是否能让他赢得赌注。 2．若他在别的地方与人打赌，如纽约或者上海，我们将分别设计最佳路径并判断所选择的路径是否能让他赢得赌注。 二、问题分析 福格环游地球问题是一个十分典型的最短路径求解问题，题设给出了当时世界上主要交通网络图及交通通畅的城市之间来往所需时长，并限定了福格的出行方向（福格选择的是往东走），给出起止地点后要求找出福格环游世界天数最短的最佳路径。 本题实质在于最短路径的求解和优化，如何求解最短路径呢，我们联系到图论中求解最短路径的Dijkstra算法，然而，要满足Dijkstra算法的条件，首要任务是弄清如何处理题设所给的世界交通网络图。我们可以把题中给出的地图看成是三维环状地图，而Dijkstra算法要求输入图G的关联矩阵，且图G为二维赋权图，因此，我们应该对题设地图做相关处理，将其从起点处“切断”并展开为二维图，然后根据此图建立关联矩阵。但是，考虑到最短路径可能会与切断线有交点，我们必须在切断线以西找出若干地点一分为二，修改关联矩阵。 在创建关联矩阵的时候，必须考虑到如何估计两处缺失的数据，当时的地区交通状况文献已经无法查询，因此，我们只能根据当地周围相似地形地势处的已知交通状况进行估值。如何估值呢，我们用Google Earth对两地距离进行测量，并进行若干假设，与附近相似地形已知数据处进行同比例估值，得到近似结果。对于题目提出的问题，分别以伦敦、纽约和上海作为起点，我们只需调整关联矩阵起点和终点用matlab编程进行求解即可得到最短环游时间和最短路径，从而判断出所选择的路径是否能让他赢得赌注。 三、基本假设 1、题目中给出的数据均准确。 2、题目中给出的数据均采用当时能达到的最高效的交通方式。 3、在环游地球的路程中，福格不会在任何地点因任何原因停留。 单源最短路径的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 算法求最短路问题. 1.需求分析： 首先让用户输入一个带权的有向图，输入时可通过一对一对输入存在弧的两个弧头与弧尾顶点以及弧上的权值从而输入整个有向图。用户输入一对对弧后，我们可以采用数组的形式来进行存储每个顶点之间的权值，最后由用户输入该有向图的源点（即每个最短路径的起点），要求源点必须为刚才输入的各顶点中的某一个，如果用户输入错误，程序要给出错误信息提示并退出程序。然后，我们可以设计一个Graph这样的类，将对关系的各种操作放入其中，然后我们在主函数中调运这个类就可以实现最短路问题的求解了。 2.概要设计： ①.构造一个新的类Graph: class Graph { private: int arcs[MAX][MAX],Path[MAX][MAX],D[MAX]; int arcnum,vexnum,weight,v0; Type a,b,vexs[MAX]; public: void Creat_Graph(); void Show_ShortestPath(); void ShortestPath_DIJ(); }; ②.结构化调用类中方法的主函数： int main() { Graph 数据通信与计算机网络大作业 Dijkstra 最 短 路 径 算 法 【摘要】 摘要:最短路径分析在地理信息系统、计算机网络路由等方面发挥了重要的作用, 对其进行优化很有必要。本文分析了传统 的最短路径算法(即Dijkstra 算法)的优化途径及现有的优化算法, 然后在Dijkstra 算法的基础上, 采用配对堆结构来实现路 径计算过程中优先级队列的一系列操作, 经理论分析与实验测试结果对比, 可以大大提高该算法的效率和性能。 【关键词】 最短路径; Dijkstra 算法; 【正文】 随着计算机网络技术和地理信息科学的发展, 最短路径问题无论是在交通运输, 还是在城市规划、物流管理、网络通讯等方面, 它都发挥了重要的作用。因此, 对它的研究不但具有重要的理论价值, 而且具有重要的应用价值。研究最短路径问题通常将它们抽象为图论意义下的网络问题, 问题的核心就变成了网络图中的最短路径问题。此时的最短路径不单指“纯距离”意义上的最短路径, 它可以是“经济距离”意义上的最短路径, “时间”意义上的最短路径, “网络”意义上的最短路径。关于最短路径问题, 目前所公认的最好的求解方法, 是由F.W.Dijkstra 提出的标号法, 即Dijkstra 算法。 1 Dijkstra 算法 Dijkstra 算法是求最短路径的最基本和使用最广泛的算法。在求从网络中的某一节点(源点)到其余各节点的最短路径时, 经典Dijkstra 算法将网络中的节点分成三部分: 未标记节点、临时标记节点和最短路径节点(永久标记节点)。算法开始时源点初始化为最短路径节点, 其余为未标记节点, 算法执行过程中, 每次从最短路径节点往相邻节点扩展, 非最短路径节点的相邻节点修改为临时标记节点, 判断权值是否更新后, 在所有临时标记节点中提取权值最小的节点, 修改为最短路径节点后作为下一次的扩展源, 再重复前面的步骤, 当所有节点都做过扩展源后算法结束。具体算法描述如下: 设在一非负权简单连通无向图G= 总结：最短路径算法关键先把已知最短路径顶点集(只有一个源点)和未知的顶点分开，然后依次把未知集合的顶点按照最短路径(这里特别强调一下是源点到该顶点的路径权重和，不仅仅是指它和父结点之间的权重，一开始就是在没有这个问题弄清楚)加入到已知结点集中。在加入时可以记录每个顶点的最短路径，也可以在加入完毕后回溯找到每个顶点的最短路径和权重。 迪杰斯特拉算法用于求解一个有向图（也可以是无向图，无向图是有向图的一种特例）的一个点（称之为原点）到其余各点（称之为周边点）的最短路径问题。算法构思很是巧妙（我这么认为），简直达到了“无心插柳柳成荫”的境界。算法本身并不是按照我们的思维习惯——求解从原点到第一个点的最短路径，再到第二个点的最短路径，直至最后求解完成到第n个点的最短路径，而是求解从原点出发的各有向路径的从小到大的排列（如果这个有向图中有环1-2-3-1算法岂不是永无终结之日了？？！！），但是算法最终确实得到了从原点到图中其余各点的最短路径，可以说这是个副产品，对于算法的终结条件也应该以求得了原点到图中其余各点的最短路径为宜。清楚了算法的这种巧妙构思 后，理解算法本身就不是难题了。 算法把一个图（G）中的点划分成了若干部分： 1）：原点（v）； 2）：所有周边点（C）； 另外有一个辅助集合S，从v到S中的点的最短路径已经求得。S的最初状态是空集。 这样就可以进一步划分图（G）： 1）：原点（v）； 2）：已求出v至其最短路径的周边点（S）； 3）：尚未求出v至其最短路径的周边点（Other=C-S）； 算法的主体思想： A、找到v——Other所有路径中的的最短路径vd=v——d（Other的一个元素）； B、找到v——S——Other所有路径中的的最短路径vi=v——i（Other 的一个元素）； C、比较vd和vi如果vd<=vi则将d加入S且从Other中删除，否则将i加入S且从Other中删除。 重复以上步骤直至Other为空集。 我们求得的最短路径是升序排列的，那为什么下一条最短路径就存在于v—— Dijkstra(迪杰斯特拉算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。 Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。 其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。 初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S 中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。 例如，对下图中的有向图，应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下表中。 Dijkstra算法的迭代过程： 主题好好理解上图！ 以下是具体的实现(C/C++: 1. /*************************************** 2. * About: 有向图的Dijkstra算法实现 3. * Author: Tanky Woo 4. * Blog: https://www.doczj.com/doc/f813733296.html, 5. ***************************************/ 6. 7. #include 8. using namespace std; 9. 10. const int maxnum = 100; 11. const int maxint = 999999; 12. 13. 14. void Dijkstra(int n, int v, int *dist, int *prev, int c[maxnum][maxnum] 15. { 16. bool s[maxnum]; // 判断是否已存入该点到S集合中 17. for(int i=1; i<=n; ++i 18. { 19. dist[i] = c[v][i]; 20. s[i] = 0; // 初始都未用过该点 21. if(dist[i] == maxint 22. prev[i] = 0; 23. else 24. prev[i] = v; 25. } 26. dist[v] = 0; 27. s[v] = 1; 28. 29. // 依次将未放入S集合的结点中，取dist[]最小值的结点，放入结合S中 效果展示： 开头输入的是点的序列号（表示第几个点），显示的是最短路径的走法（同样以点的序列号显示，表示途径的第几个点）。 %编写m文件 function [distance,path]=dijkstra(A,s,e) % [DISTANCE,PATH]=DIJKSTRA(A,S,E) % returns the distance and path between the start node and the end node. % % A: adjcent matrix % s: start node % e: end node % initialize n=size(A,1); % node number D=A(s,:); % distance vector path=[]; % path vector visit=ones(1,n); % node visibility visit(s)=0; % source node is unvisible parent=zeros(1,n); % parent node % the shortest distance for i=1:n-1 % BlueSet has n-1 nodes temp=zeros(1,n); count=0; for j=1:n if visit(j) temp=[temp(1:count) D(j)]; else temp=[temp(1:count) inf]; end count=count+1; end [value,index]=min(temp); j=index; visit(j)=0; for k=1:n if D(k)>D(j)+A(j,k) D(k)=D(j)+A(j,k); parent(k)=j; end Dijkstra算法求最短路径(C#版) 行如下图的路径,(V0是中心): 经过该算法后转化为下图 using System; using System.Collections; using System.Text; namespace Greedy { class Marx { private int[] distance; private int row; private ArrayList ways = new ArrayList(); public Marx(int n,params int[] d) { this.row = n; distance = new int[row * row]; for (int i = 0; i < row * row; i++) { this.distance[i] = d[i]; } for (int i = 0; i < this.row; i++) //有row个点，则从中心到各点的路有row-1条 { ArrayList w = new ArrayList(); int j = 0; w.Add(j); ways.Add(w); } } //------------------------------ public void Find_way() { ArrayList S = new ArrayList(1); ArrayList Sr = new ArrayList(1); int []Indexof_distance=new int[this.row]; for(int i=0; i < row; i++) { Indexof_distance[i]=i; } S.Add( Indexof_distance[0] ); for (int i = 0; i < this.row; i++) { Sr.Add( Indexof_distance[i] ); } Sr.RemoveAt(0); int[] D = new int[this.row]; //存放中心点到每个点的距离 //---------------以上已经初始化了，S和Sr(里边放的都是点的编号)------------------ int Count = this.row - 1;Dijkstra算法
计算最短路径的Dijkstra算法的编程实现
数据结构课程设计报告Dijkstra算法求最短路径
gis计算最短路径的Dijkstra算法详细讲解
Dijkstra最短路径算法
迪杰斯特拉算法求解最短路径
Dijkstra算法求最短路径
迪杰斯特拉算法计算最短路径
单源最短路径的Dijkstra算法
最短路径_Dijkstra算法__实验报告
dijkstra最短路径算法
迪杰斯特拉算法总结
最短路径算法―Dijkstra(迪杰斯特拉)算法分析与实现(
暴强Dijkstra算法求任意两点间最短路径
Dijkstra算法求最短路径(C#版)
相关主题
文本预览