1、第三节 最短路问题 最短路问题是网络理论中应用最广的问题之一。许多优化问题可以使这个模型，如设备更新、管道铺设、线路安排、厂区布局等。图论方法比较有效。 最短路问题的一般提法如下：设 G=（ V， E）为连通图，图中各边 为图中任意两点，求一条道路 ，使他是从的所有道路中总权最小的道路。即：最小 . 有些最短问题也可以使球网络中某指定点到其余所有结点的最短路，过求网络中任意两点间的最短路。下面我们介绍三种算法，可分别用于求解这几种最短路问题。 一、 Dijkstra算法 本算法由 Dijkstra于 1959年提出，可用于求解指定两点 间的最短路，或从指定点 到其余各点的最短路，目前被认为是求
2、无负权网络最短路问题的最好方法。算法的基本思想基于以下原理：若序列 是从 的最短路，则序列 必为从 的最短路。 基本步骤： 求出从 a到 z的最短路的长度是？acbedz542101 8 263 解： 0次迭代（初始化） L(a)=0,L(b)=L(c)=L(d)=L(e)=L(z)= ,S0= ; 一次迭代：取 u1=a,S1=aL(a)+w(a,b)=0+4=4L(b)L(a)+w(a,c)=0+2=2L(c)L(a)+w(a,d)=0+ =L(a)+w(a,e)=L(a)+w(a,z)=0+ = ;L(b)=4,L(c)=2,L(d)=L(e)=L(z)=二次迭代：取 u2=c, S2=
3、a,cL(c)+w(c,b)=2+1=3L(b)L(c)+w(c,d)=2+8=10L(d)L(c)+w(c,e)=2+10=12L(e)L(c)+w(c,z)=2+ =L(b)=3,L(d)=10,L(e)=12,L(z)= 三次迭代：取 u3=b, S3=a,c,b L(b)+w(b,d)=3+5=8L(d) L(b)+w(b,e)=3+ = L(b)+w(b,z)=3+ = L(d)=8, L(e)=12, L(z)= 四次迭代：取 u4=d, S4=a,c,b,d L(d)+w(d,e)=8+2=10L(e) L(d)+w(d,z)=8+6=14L(z) L(e)=10, L(z)=14; 五次迭代：取 u5=e, S5=a,c,b,d,e L(e)+w(e,z)=10+3=13L(z) L(z)=13 结束： u6=z, S6=a,c,b,d,e,z 从 a到 z 的最短路的长度为 13,最短路经为 a,c,b,d,e,z 同样可以利用 Dijkstra算法计算 有向网络 中最短有向路的长度，基本步骤如下： 求出点 1到其余各顶点的 最短有向路 的长度？1543253284731 Dijkstra算法 : 课堂练习 1： 利用 Dijkstra算法，算出图中，v1到 v5的 最短路 的长度？V1V3V2V4V5432758101
