3.1狄克斯拉(Dijkstra)算法 最短路问题可以化为线性规划问题求解，也可以用动态规划方 法求解，这里介绍一种有效算法一狄克斯拉(Dijkstra)算法，这一 算法是1959年首次被提出来的。该算法适用于每条弧的权数o,≥0 情形。算法的基本思路：从发点，出发，有一个假想的流沿网络一 切可能的方向等速前进，遇到新节点后，再继续沿一切可能的方向 继续前进，则最先到达终点，的流所走过的路径一定是最短的。为 了实现这一想法，对假想流依次到达的点，依次给予标号，表示： 到这些点的最短距离。对于假想流尚未到达的点给予T标号，表示v 到这些点的最短距离的估计值。具体作法如下： s1°标p(v,)=0,其余点标T(v)=+o; $2°由刚刚获得标号的v,点出发，改善它的相邻点v,的T标号，即 新的T(o)=min{老的T（y),p()+o} 若T(y)=p()+@,则记k(y)=(前点标记)； $3°找出具有最小T标号的点，将其标号改为p标号。若v,已获得p 标号，则已找到最短路，由k（,)反向追踪，就可找出v,到，的最 短路径，p（)就是，到：的最短距离。否则，转2°。3.1 狄克斯拉（Dijkstra）算法 最短路问题可以化为线性规划问题求解，也可以用动态规划方 法求解，这里介绍一种有效算法—狄克斯拉（Dijkstra）算法，这一 算法是1959年首次被提出来的。该算法适用于每条弧的权数ωij ≥0 情形。算法的基本思路：从发点vs 出发，有一个假想的流沿网络一 切可能的方向等速前进，遇到新节点后，再继续沿一切可能的方向 继续前进，则最先到达终点vt 的流所走过的路径一定是最短的。为 了实现这一想法，对假想流依次到达的点，依次给予p标号，表示vs 到这些点的最短距离。对于假想流尚未到达的点给予T标号，表示vs 到这些点的最短距离的估计值。具体作法如下： 1°标p（vs）=0，其余点标T（vi）=+∞; 2°由刚刚获得p标号的vi 点出发，改善它的相邻点vj 的T标号,即 新的T（vj）=min{老的T（vj），p（vi）+ ωij } 若T（vj）= p（vi）+ ωij ，则记k（vj ）=vi（前点标记）; 3°找出具有最小T标号的点，将其标号改为p标号。若vt 已获得p 标号，则已找到最短路，由k（vt）反向追踪，就可找出vs 到vt 的最 短路径，p（vt）就是vs 到vt 的最短距离。否则，转2°