迪杰斯特拉算法讲课教案.ppt

迪杰斯特拉算法实现;迪杰斯特拉--算法思想; 设给定源点为VsS为已求得最短路径的终点集开始时令S={Vs} 当求得第一条最短路径(Vs Vi)后S为{VsVi} 根据以下结论可求下一条最短路径 设下一条最短路径终点为Vj 则Vj只有 源点到终点有直接的弧 从Vs 出发到Vj 的这条最短路径所经过的所有中间顶点必定在S中即只有这条最短路径的最后一条弧才是从S内某个顶点连接到S外的顶点V