找最短路的狄杰科斯特解法

出处：按学科分类—自然科学总论 山东人民出版社《方法大辞典》第204页（809字）

最短路问题是图论、网络理论中的一个重要问题。

它不仅可以直接应用于各种管道铺设、线路安排、厂区布局等实际问题，并且也是解决图、网络的其他理论问题的基础。

给定图G=(V，E)，每条边有实数权a(e)(a(e)≥0)。

现在要求连接G中任意两点之间的所有通路中边的权数之和最小的一条通路。

最短路的狄杰科斯特解法的求解过程如下：首先从u₀出发选择一个距u₀最近的节点，为此检查所有与u₀相邻的节点，并找出它与u₀的距离，取其中最小者为，同时确定

根据d(u₀，s₀)=min｛d(u₀，u)+a(u，v)｝u₀∈s₀，所以。令满足此式的V=u₁集合s从s₀=｛u₀｝扩大到s₁=｛u₀，u₁｝。记p₁为u₀u₁通路，显然这是一条u₀到的最短路。若集合已扩展到s_k=｛u₀，u₁，…u_k｝，其对应的最短路p₁，p₂，…，p_k就已确定下来，则由前式可以计算，并同时可以选取节点，使

因为 d(u₀，u_k+1)=d(u₀，u_j)+a(u_j，u_k+1)，当j=1，2，…k中某个j成立，

所以，将边u_ju_k+1连接到通路p_j上，即得(u₀，u_k+1)的最短路，p_j=(u₀，…，u_j)。

为了避免重复计算并保留每一步的计算信息，在计算过程中采用一定的标号程序，给每一节点V－开始就给个初始标记I(V)。

I(V)是d(u_。，v)的一个上界。开始计算时标号I(u₀)=0，其他节点标记I(V)=∞。计算过程中，这些标记不断被修改，到第i步结束时

I(u)=d(u₀，u)，u∈s_i

以及