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

精选优质文档-倾情为你奉上迪杰斯特拉算法的基本思想 算法的基本思想是：设置并逐步扩充一个集合S，存放已求出其最短路径的顶点，则尚未确定最短路径的顶点集合是V-S，其中V为网中所有顶点集合。按最短路径长度递增的顺序逐个以V-S中的顶点加到S中直到S中包含全部顶点，而V-S为空。 具体做法是：设源点为vl，则S中只包含顶点vl，令WV-S，则W中包含除v1外图中所有顶点，vl对应的距离值为0，W中顶点对应的距离值是这样规定的：若图中有弧，则vj顶点的距离为此弧权值，否则为 (一个很大的数)，然后每次从W中的顶点中选个其距离值为最小的顶点vm加入到S中，每往S中加入一个顶点vm，就要对W中的各个顶点的距离值进行一次修改。若加进vm做中间顶点，使+的值小于值，则用+代替原来vj的距离，修改后再在W中选距离值最小的顶点加入到S中，如此进行下去，直到S中包含了图中所有顶点为止。下面以邻接矩阵存储来讨论迪杰斯特拉算法的具体实现。为了找到从源点到其