如例1，A一B2一C1一D2一E是由A到E的最短路线，我们在 该路线上任取一点C,,按照最优性原理C,一D,一E应该是C,到 E的最短路。很容易用反证法证明这一结论的正确性，从而说 明最优性原理的正确性。 按最优性原理，·可以将例1分成AB二C一—D二E个阶段， 由后向前逐步求出各点到E的最短线路，直至求出A至E的最短 线路。 K=4时，出发点有D1,D2,D3,记 例1的线路网络图： (D)(i=1,2,3)为D到E的最短距 4(D)表示从状态D出发采取的决 策。显然：(D1)=7,u4(D)=E f(D2)=8,u4(D2)=E f(D3)=6,u4(D3)=E 9 K=3时，出发点有C1,C2,C3 (C)=min {d (C D)(D),d (C D2)(D2)) =min{4+7,2+8}=10, u3(C1)=D2 5(C2) =min {d (C2D2)(D2),d (C2D3)(D3) =min{5+8,7+6}=13, u3(C2=D2或D3 5(C3)=min{d(C3D2)+i(D2),d(C3D3)+f(D3)) =min{10+8,9+6}=15, u3(C3)=D3如例1，A—B2—C1—D2—E是由A到E的最短路线，我们在 该路线上任取一点C1 ，按照最优性原理C1—D2—E应该是C1到 E的最短路。很容易用反证法证明这一结论的正确性，从而说 明最优性原理的正确性。 按最优性原理，可以将例1分成A—B—C—D—E 4个阶段， 由后向前逐步求出各点到E的最短线路，直至求出A至E的最短 线路。 K=4时，出发点有D1，D2，D3，记 f4（Di）（i=1,2,3）为Di到E的最短距 离；u4 (Di )表示从状态Di出发采取的决 策。显然： f4（D1）=7，u4 (D1 )=E f4（D2）=8，u4 (D2 )=E f4（D3）=6，u4 (D3 )=E K=3时，出发点有C1，C2，C3 f3（C1）=min｛d（C1D1）+f4（D1）,d（C1D2）+f4（D2）｝ =min｛4+7,2+8｝=10, u3 (C1 )= D2 f3（C2）=min｛d（C2D2）+f4（D2）,d（C2D3）+f4（D3）｝ =min｛5+8,7+6｝=13, u3 (C2 )= D2或D3 f3（C3）=min｛d（C3D2）+f4（D2）,d（C3D3）+f4（D3）｝ =min｛10+8,9+6｝=15, u3 (C3 )= D3