Dijkstra的一种改进算法.pdfVIP

维普资讯 Dijkstra的一种改进算法 孙 强 沈建华 顾君忠 (华东师范走学计算机科学技术系，上海 200O62) E-mall：h100sh@263．net 摘 要 在Dijks~a算法的基础上，谊算法使用了一些独特的敷括结构 如《：前趋表和最短肆往表)；使用谊算法能南效 率地求 出囤中一个顶点到其它各碗点的所有最短肆往 。用 C语言设计 了相应程序验证 了此算法。 美t词 Dijkstra 最短路径 算鲁 文章编号 1002-8331一(2002)O3一O099—03 文献标识码 A 中围分类号 TP3l】 AnImprovedAlgorithm oftheDijkstraAlgorithm Sun Qiang ShenJianhua GuJunzlmug (DepartmentofComputerScienceandTechnology，EastChinaNormalUniversity，Shanghai200062) Al~aaet： BasedOf／theDjikmaalgorithm，soll3epeculiardatastruelares(suchasthetableofpredecessornodes)have been usod．MIshortestpathsfrom one：nodetoallothernodescan be derived quickly ifyou Iethealogrithm．The timeeomplexltyofthisalgorithm isveryneara lowerlimitof any timecomplexityof allthosl~algorihtmsthatfind OUt allshortestpaths IKeFwords~DIjkstlra，shortestpath，algorithm 1 前言 直接前趋结点的。PR表由一个一堆数组 ^pr和若干个单链表 Dijkstra算甚 (以下简称 D算法)是圈论中求最短路径 的一 (这样的每个单链表以下简称一个前趋单链表)组成。^P艰]中 个著名的算法，使用D算法可求出图中从一个顶点到其它各 存储的是一个前趋单链表的头指针 ，一个以^p,-I~l为头指针的 顶点的最短路径的长度 ，而不能求出从一个顶点到其它各顶点 前趋单链表中每个结点(称为一个趋向结点)由二个域组成，即 的所有最短路径。1996年。EliOliniekl~l和D．K．Smith~等就求出 faexi，其中 (1《P≤)称为直接前趋域，它存已求出的从 所有最短路径这一问题做了一些简单的探讨，但这些探讨过于 1到V 的路径上 的一个直接前趋结点，而船 称为趋向 简单 ，又不完整 ，而且缺少时间分析 。所 没有多大 的实用性 。 指针域，它存此单链表中下一个趋向结点的地址。 该文挺出了D算法的一种改进算法 (以下简称改进算法)，使 (4)所有最短路径表(以下简称 APT表) 用改进算法能求出从一个顶点到其它各顶点的所有最短路径 。 APT表是用来存储 已求出的从 1刊其它各顶点的所有 而且，此改进算法 的时间复杂度非常接近于任何一个求所有最 最短路径的。AVf表 由一个一维数组 和若干个 AIrY表的 短路径算法的时问复杂度的一个下限值。改进算法在很多领域 子表 APT1(2≤ ≤n)共 同组成 设从 y1刊 y 共有nlk条最 (如：变通等)中有着较高的实用价值。 短路径，一个APT的子表APT1是用来存储已求出的从y1 到 ¨ 的所有这 nlk条最短路径 ，而APT1这个子表 的地址存 2 改进算法的存贮结构