最短通路问题 Shortest-Path problems 定义:在一个带权图G中,任给两点u,V,从u到J 能有多条路,在这些路中,所带的权和最小的那条路 称为图中从u到的最短路。这条最短路所带的权和称 为u到∨的距离,记为d(u,v)。 ba到的路有 (1)(ab,c)度为5+4=9 12.(2)(ac)长度为12, (3)(adc)长度为8+20=28 最短通路为:(ab,c) 20 d(a, c=9
最短通路问题 Shortest-Path Problems ◼ 定义：在一个带权图G中，任给两点u，v，从u到v可 能有多条路，在这些路中，所带的权和最小的那条路 称为图中从u到v的最短路。这条最短路所带的权和称 为u到v的距离，记为d(u,v)。 a b d c 5 8 12 4 20 a到c的路有： (1) (a,b,c)长度为5+4=9; (2) (a,c)长度为12; (3) (a,d,c)长度为8+20= 28。 最短通路为： (a,b,c), d(a,c)=9
Dijkstra算法 n定义设G是有限带权图,SV(G),u∈S, S=VG)-S,定义u到S的距离为 duo s)=mind(uo, v)i V∈S 实现上述距离的路称为u到S的最短路。 上述点到点集距离的定义等价于 duo, s)=min duo,u+ w(u, vP u∈S V∈S
Dijkstra算法 ◼ 定义 设G是有限带权图，SV(G)，u0S， S’= V(G) -S，定义u0到S’的距离为 d(u ,S') min {d(u , v)} 0 v S' 0 = 实现上述距离的路称为u0到S’的最短路。 上述点到点集距离的定义等价于 d(u ,S') min {d(u ,u) w(u, v)} 0 v S' u S 0 = +
Dijkstra算法 例:如图所示,令S={a,b,f,则S'={c,d,e}, 求d(a,S)? S f12 10 a b 5 C
Dijkstra算法 例：如图所示，令S={a, b, f}，则S’={c, d, e}， 求d(a, S’)？ a b c d 1 2 5 6 10 f e 1 1 4 3 S S’
Dijkstra算法 设U=a, 取u=a,则W(ac)=,W(ad)=10,W(ae)= min d(a, a)+Wav =mn wav =10 V∈ V∈ S" a 10
Dijkstra算法 ◼ 设u0=a， 取u=a，则w(ac)=∞，w(ad)=10，w(ae)=∞， min {d(a, a) w(av)} min {w(av)} 10 v S' v S' + = = a b c d 1 2 5 6 10 f e 1 1 4 3
Dijkstra算法 取u=b,则d(a,b)=6,w(bc)-=5,w(bd)=wbe)=4, mn{d(a,b)+wbv)}=6+4=10 V∈ 取u=f,则d(anf)=1,w(fe)=1,w(fi)=∞,w(fe)2 mn{d(af+w(f)}=1+1=2 因而d(a,S°)2,a到S 的最短路为 0 a d a.l. c b 5
取 u=b，则d(a,b)=6，w(bc)=5，w(bd)=∞ w(be)=4， min {d(a, b) w(bv)} 6 4 10 v S' + = + = 取 u=f，则d(a,f)=1，w(fc)=1，w(fd)=∞，w(fe)=2 min {d(a, f) w(fv)} 1 1 2 v S' + = + = a b c d 1 2 5 6 10 f e 1 1 4 因而d(a, S’)=2，a到S’ 3 的最短路为 （a, f, c）。 Dijkstra算法