给定一个带权图G和一个起始点即源点V，狄克斯特拉算法的具体步骤如下：（1）初始化：顶点集S只包含源点，即S={v)，顶点v到自已的最短路径长度为9。顶点集U包含除V外的其他顶点，源点v到U中顶点的最短路径长度为边上的权值（若源点v到顶点有边<V，>）或8（若源点v到顶点i没有边，此时认为有一条长度为的最短路径）U=V-S6/46
给定一个带权图G和一个起始点即源点v，狄克斯特拉算法的具体步骤如下： （1）初始化：顶点集S只包含源点，即S={v}，顶点v到自已的最短路 径长度为0。顶点集U包含除v外的其他顶点，源点v到U中顶点i的最短路径 长度为边上的权值（若源点v到顶点i有边<v，i>）或∞（若源点v到顶点i 没有边，此时认为有一条长度为∞的最短路径）。 v j S U=V-S i 6/46
（2）从U中选取一个顶点u，它是源点v到U中最短路径长度最小的顶点，然后把顶点u加入S中（此时求出了源点v到顶点u的最短路径长度）。U=V-S最短7146
（2）从U中选取一个顶点u，它是源点v到U中最短路径长度最小的顶点， 然后把顶点u加入S中（此时求出了源点v到顶点u的最短路径长度）。 v i S U=V-S u 7/46
（3）以顶点u为新考虑的中间点，修改顶点U的出边邻接点的最短路径长度，此时源点v到顶点的最短路径有两条，即一条经过顶点u，一条不经过顶点u。①若经过顶点u的最短路径长度比不经过顶点u的最短路径长度更短，则修改源点v到顶点的最短路径长度为经过顶点u的那条长度。②否则，说明原来的不经过顶点u的最短路径长度更短，不需要修改。有一条边有一条路径CvuWuj两条路径中求最小者7Cvj（4）重复步骤（2）和（3）直到S包含所有的顶点即U为空。8/46
（3）以顶点u为新考虑的中间点，修改顶点u的出边邻接点j的最短路 径长度，此时源点v到顶点j的最短路径有两条，即一条经过顶点u，一条 不经过顶点u。 ① 若经过顶点u的最短路径长度比不经过顶点u的最短路径长度更短， 则修改源点v到顶点j的最短路径长度为经过顶点u的那条长度。 ② 否则，说明原来的不经过顶点u的最短路径长度更短，不需要修改。 v j u cvu wuj cvj 有一条路径 有一条边 （4）重复步骤（2）和（3）直到S包含所有的顶点即U为空。 两条路径中求最小者 8/46
2狄克斯特拉算法设计狄克斯特拉算法设计要点：判断顶点i属于哪个集合，设置一个数组s，S[il=1表示顶点属于s集合，S[]=0表示顶点i属于U集合。保存最短路径长度，由于源点v是已知的，只需要设置一个数组dist[o..n-1]，dist[]用来保存从源点v到顶点i的最短路径长度，dist[]的初值为<v，i>边上的权值，若顶点v到顶点i没有边，则权值定为8。以后每考虑一个新的中间点u时，dist[il的值可能被修改变小。保存最短路径，设置一个数组path[o..n-1]，其中path[]存放从源点v到顶点i的最短路径。9/46
2. 狄克斯特拉算法设计 狄克斯特拉算法设计要点： 判断顶点i属于哪个集合，设置一个数组S，S[i]=1表示顶点i属于S 集合，S[i]=0表示顶点i属于U集合。 保存最短路径长度，由于源点v是已知的，只需要设置一个数组 dist[0.n-1]，dist[i]用来保存从源点v到顶点i的最短路径长度。 dist[i]的初值为<v，i>边上的权值，若顶点v到顶点i没有边，则 权值定为∞。以后每考虑一个新的中间点u时，dist[i]的值可能被 修改变小。 保存最短路径，设置一个数组path[0.n-1]，其中path[i]存放从 源点v到顶点i的最短路径。 9/46
为什么能够用一个一维数组保存多条最短路径呢？path[]只保存源点v到顶点j的最短路径上顶点j的前驱顶点path[j]=u如果该路径恰好包含源点v到u的最短路径OK如果不是×10/46
为什么能够用一个一维数组保存多条最短路径呢？ path[j]只保存源点v到顶点j的最短路径上顶点j的前驱顶点 v . u j path[j]=u 如果该路径恰好包含源点v到u的最短路径 OK 如果不是 10/46