迪杰斯特拉算法的原理

发布网友发布时间：2022-04-28 21:24

共1个回答

热心网友时间：2022-06-23 06:32

1.首先，引入一个辅助向量D，它的每个分量 D 表示当前所找到的从起始点（即源点）到其它每个顶点的长度。
例如，D[3] = 2表示从起始点到顶点3的路径相对最小长度为2。这里强调相对就是说在算法执行过程中D的值是在不断*近最终结果但在过程中不一定就等于长度。
2.D的初始状态为：若从到有弧（即从到存在连接边），则D 为弧上的权值（即为从到的边的权值）；否则置D 为∞。
显然，长度为 D = Min{ D | ∈V } 的路径就是从出发到顶点的长度最短的一条路径，此路径为( )。
3.那么，下一条长度次短的是哪一条呢？也就是找到从源点到下一个顶点的最短路径长度所对应的顶点，且这条最短路径长度仅次于从源点到顶点的最短路径长度。
假设该次短路径的终点是，则可想而知，这条路径要么是( )，或者是( )。它的长度或者是从到的弧上的权值，或者是D 加上从到的弧上的权值。
4.一般情况下，假设S为已求得的从源点出发的最短路径长度的顶点的集合，则可证明：下一条次最短路径（设其终点为）要么是弧( )，或者是从源点出发的中间只经过S中的顶点而最后到达顶点的路径。
因此，下一条长度次短的的最短路径长度必是D = Min{ D | ∈V-S }，其中D 要么是弧( )上的权值，或者是D ( ∈S)和弧( , )上的权值之和。
算法描述如下：
1）令arcs表示弧上的权值。若弧不存在，则置arcs为∞（在本程序中为MAXCOST）。S为已找到的从出发的的终点的集合，初始状态为空集。那么，从出发到图上其余各顶点可能达到的长度的初值为D=arcs[Locate Vex(G, )]， ∈V；
2）选择，使得D =Min{ D | ∈V-S } ；
3）修改从出发的到集合V-S中任一顶点的最短路径长度。