迪杰斯特拉算法的基本思想(共1页).doc

精选优质文档-倾情为你奉上迪杰斯特拉算法的基本思想 算法的基本思想是：设置并逐步扩充一个集合S，存放已求出其最短路径的顶点，则尚未确定最短路径的顶点集合是V-S，其中V为网中所有顶点集合。按最短路径长度递增的顺序逐个以V-S中的顶点加到S中直到S中包含全部顶点，而V-S为空。 具体做法是：设源点为vl，则S中只包含顶点vl，令WV-S，则W中包含除v1外图中所有顶点，vl对应的距离值为0，W中顶点对应的距离值是这样规定的：若图中有弧<vi,vj>，则vj顶点的距离为此弧权值，否则为¥ (一个很大的数)，然后每次从W中的顶点中选个其距离值为最小的顶点vm加入到S中，每往S中加入一个顶点vm，就要对W中的各个顶点的距离值进行一次修改。若加进vm做中间顶点，使<vi,vm>+<vm,vj>的值小于<vi,vj>值，则用<vi,vm>+<vm,vj>代替原来vj的距离，修改后再在W中选距离值最小的顶点加入到S中，如此进行下去，直到S中包含了图中所有顶点为止。下面以邻接矩阵存储来讨论迪杰斯特拉算法的具体实现。为了找到从源点到其他顶点的最短路径，引入两个辅助数组distn,sn,数组dist记录从源点到其他各顶点当前的最短距离，其初值为disti=costv0i, i=2,.,n.其中v0表示源点。从S之外的顶点集合V-S中选出一个顶点w,使distw的值最小。于是从源点到达w只通过S中的顶点，把w加入集合S中调整dist中记录的从源点到V-S中每个顶点v的距离：从原来的distv和distw+costwv中选择较小的值作为新的distv,重复上述过程，直到S中包含V中其余各顶点的最短路径。专心-专注-专业