外层层扩展,直到扩展到终点为止.Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等.Dijkstra一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用OPEN, CLOSE表的方式,这里均采用永久和临时标号的方式.该算法要求图中不存在负权边.Р2.2.1 原理РDijkstra算法是1959年由E.W.Dijkstra提出的图论中求最短路径的一个著名的算法,使用其可以求得图中一点到其他各顶点的最短路径.原始的Dijkstra算法将网络结点分成3部分:未标记结点、临时标记结点和永久标记结点.网络中所有结点首先初始化为未标记结点,在搜索过程中和最短路径中的结点相连通的结点为临时标记结点,每次循环都是从临时标记结点中搜索距源点路径长度最短的结点作为永久标记结点,直至找到目标结点或者所有的结点都成为永久标记结点来结束算法.Р假设每个点都有一对标号(,),其中是从起源点到点的最短路径的长度(从顶点到其本身的最短路径是零路(没有弧的路),其长度等于零);Р 则是从到的最短路径中点的前一点.求解从起源点到点的最短路径算法的基本过程如下:Р(1)初始化.起源点设置为:①,为空;②所有其他点:,;③标记起源点,记,其他所有点设为未标记的.Р(2)检验从所有已标记的点到其直接连接的未标记的点j的距离,并设置:式中,是从点到的直接连接距离.Р(3)选取下一个点.从所有未标记的结点中,选取中最小的一个:Р,(所有未标记的点),点就被选为最短路径中的一点,并设为已标记的.Р(4)找到点的前一点.从已标记的点中找到直接连接到点的点,作为前一点,设置:=.Р(5)标记点.如果所有点已标记,则算法完全推出,否则,记=,转到(2)再继续.Р 0Р Р100Р Р 10 Р Р4Р1Р Р 30Р Р 10 Р 50 60Р3Р2
全文预览
