并加上圆圈。如表中k=1所示 k=2,将L2)的第2行和第2列的元素保持不变,按(4.2)式计算 L32=min{L1y,L2+L2(}=min{4,3+(-4)}=1 L152=min{L1s,L124+L250}=min{∞,3+2}=5 L43(2=min{L4y,L424)L2(}=min{13,12+(-4)}=8 L53(2=min{L5y,L2)+L2()}=min{∞,2+(-4)}=2 其余元素未变,并对L13(2),L15(2,L432),Ls32)加圈。 同时在02)中按(43)式有 132=012()=20152=012().432=2(=1,053=0s2(=2,并加圈。如表中k=2 所示 k=34.5的结果均在表中给出,过程从略。 L5=(L5)给出了图11中各点之间的最短路长,05=(15)给出了从 到ⅵ的最短路必须经过点的下标,并由此可找出最短路。例如从v到vs 的最短路长为1(L155=1),最短路由01552(即必经过v),又由0255=3(即 经过v3),再由03=4(即必经过v),最后由045=5,可知从v到vs的 最短路是(v,v2,V3,V4,Vs)。同样,从ⅴs到v1的最短路长为10,最短路为 (v5,v2,v3,v4v1) 表 k=2 k=3 k=5 0-42:0-4-1-180-4-1-280-4-1-2 L4] 3|115032 4032 9nB0-191280-19n80-1|91280 12345 小)12345|12345 2345 123 1234512345|12345 12345 44344 2345 11145 1114 1145 1114 12345 12345 2245 2225 例用 Flood方法求图12中各顶点之间的最短路,其中各弧旁的数据32 并加上圆圈。如表中 k=1 所示。 k=2，将 L (2)的第 2 行和第 2 列的元素保持不变，按(4.2)式计算： L13(2)=min{L13(1),L12(1)+L23(1)}=min{4,3+(-4)}=-1 L15(2)=min{L15(1),L12(1)+L25(1)}=min{,3+2}=5 L43(2)=min{L43(1),L42(1)+L23(1)}=min{13,12+(-4)}=8 L53(2)=min{L53(1),L52(1)+L23(1)}=min{,2+(-4)}=-2 其余元素未变，并对 L13(2)，L15(2)，L43(2)，L53(2)加圈。 同时在 (2)中,按(4.3)式有 13(2)=12(1)=2,15(2)=12(1) ,43(2)=42(1)=1,53=52(1)=2，并加圈。如表中 k=2 所示。 k=3,4,5 的结果均在表中给出，过程从略。 L (5)=(Lij(5))给出了图 11 中各点之间的最短路长， (5)=(ij(5))给出了从 vi 到 vj 的最短路必须经过点的下标，并由此可找出最短路。例如从 v1 到 v5 的最短路长为 1(L15(5)=1),最短路由15(5)=2（即必经过 v2），又由25(5)=3（即 经过 v3），再由35(5)=4（即必经过 v4），最后由45(5)=5,可知从 v1 到 v5 的 最短路是(v1,v2,v3,v4,v5)。同样，从 v5 到 v1 的最短路长为 10，最短路为 (v5,v2,v3,v4,v1)。 表 k=0 k=1 k=2 k=3 k=4 k=5 [Lij(k)] 2 0 9 0 1 0 3 3 0 4 2 0 3 4 9      −    −   2 0 9 12 13 0 1 0 3 3 0 4 2 0 3 4 9    −    −   2 2 0 9 12 8 0 1 0 3 3 0 4 2 0 3 1 9 5  −  −    −  − 2 2 1 0 9 12 8 0 1 0 3 3 0 4 1 1 0 3 1 2 2  − −    − − − − 10 2 2 1 0 9 12 8 0 1 12 15 0 3 2 8 0 4 1 2 0 3 1 2 1 − − − − − − 10 2 2 1 0 9 1 3 0 1 12 4 0 3 2 8 0 4 1 2 0 3 1 2 1 − − − − − − − [ij(k)] 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 1 1 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 2 4 5 1 1 1 4 5 1 2 3 4 5 1 2 3 4 5 1 2 2 4 2 1 2 2 2 5 1 1 1 4 5 1 2 3 4 5 1 2 3 3 3 1 2 2 2 2 2 2 2 2 5 1 1 1 4 5 4 4 3 4 4 3 2 3 3 3 1 2 2 2 2 2 2 2 2 5 1 5 5 4 5 4 4 3 4 4 3 2 3 3 3 1 2 2 2 2 例 用 Flogd 方法求图 12 中各顶点之间的最短路，其中各弧旁的数据