172
②一维数组Path[i]：记录从源点v0到终点v i的当前最短路径上v i的直接前驱顶点序号。其初值为：如果从v0到v i有弧，则Path [i]为v0；否则为−1。
③一维数组D[i]：记录从源点v0到终点v i的当前最短路径长度。其初值为：如果从v0到v i 有弧，则D[i]为弧上的权值；否则为∞。
显然，长度最短的一条最短路径必为(v0, v k)，满足以下条件：
D[k]= Min{D[i]|v i∈V −S}
求得顶点v k的最短路径后，将其加入到第一组顶点集S中。
每当加入一个新的顶点到顶点集S，对第二组剩余的各个顶点而言，多了一个“中转”顶点，从而多了一个“中转”路径，所以要对第二组剩余的各个顶点的最短路径长度进行更新。
原来v0到v i的最短路径长度为D[i]，加进v k之后，以v k作为中间顶点的“中转”路径长度为：D[k] + G.arcs[k][i]，若D[k] + G.arcs[k][i]<D[i]，则用D[k] + G.arcs[k][i]取代D[i]。
更新后，再选择数组D中值最小的顶点加入到第一组顶点集S中，如此进行下去，直到图中所有顶点都加入到第一组顶点集S中为止。
算法6.10 迪杰斯特拉算法
数据结构与算法c++版 pdf
【算法步骤】
①初始化：
●将源点v0加到S中，即S[v0]= true；
●将v0到各个终点的最短路径长度初始化为权值，即D[i]= G.arcs[v0][v i]，(v i∈V − S)；
●如果v0和顶点v i之间有弧，则将v i的前驱置为v0，即Path[i]= v0，否则Path[i]= −1。
②循环n − 1次，执行以下操作：
●选择下一条最短路径的终点v k，使得：
D[k]= Min{D[i]|v i∈V − S}
●将v k加到S中，即S[v k]= true；
●根据条件更新从v0出发到集合V − S上任一顶点的最短路径的长度，若条件
D[k] + G.arcs [k][i]<D[i]成立，则更新D[i] = D[k] + G.arcs[k][i]，同时更改v i的前驱为
v k；Path [i] = k。
【算法描述】
void ShortestPath_DIJ(AMGraph G, int v0)
{//用Dijkstra算法求有向网G的v0顶点到其余顶点的最短路径
n=G.vexnum;                    //n为G中顶点的个数
for(v=0;v<n;++v)  //n个顶点依次初始化
{
S[v]=false;                  //S初始为空集
D[v]=G.arcs[v0][v];            //将v0到各个终点的最短路径长度初始化为弧上的权值
if(D[v]<MaxInt) Path[v]=v0;  //如果v0和v之间有弧，则将v的前驱置为v0
else Path[v]=-1;                //如果v0和v之间无弧，则将v的前驱置为-1
}  //for
S[v0]=true;                    //将v0加入S
D[v0]=0;                      //源点到源点的距离为0
/*--------初始化结束，开始主循环，每次求得v0到某个顶点v的最短路径，将v加到S集---------*/    for(i=1;i<n;++i) //对其余n−1个顶点，依次进行计算
{
min=MaxInt;
for(w=0;w<n;++w)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。