【正文】 最短路徑長度值，然后選擇第 5條最短路徑終點(diǎn) V3。 Min{D[k]}= D[3]=45 S={V0,V4,V1,V5,V2,V3},VS ={} 2022/2/16 106 V0 V1 V2 V3 V4 V5 最短路徑值 D 0 20 45 45 10 30 最短路徑 V0 V0, V1 V0, ,V4,V5,V2 V0,V4 ,V3 V0, V4 V0,V4,V5 2022/2/16 107 第 7章 圖 求每一對頂點(diǎn)間最短路徑的弗羅伊德 (Floyd)算法 2022/2/16 108 第 7章 圖 對圖 726的帶權(quán)有向圖利用 Floyd算法求任意一對頂點(diǎn)間的最短路徑。 圖 726 帶權(quán)有向圖 3 2 20 2 1 0 15 2 3 6 1 4 1 第 0步 :初始化任意兩個頂點(diǎn)間的距離為兩點(diǎn)間的弧的權(quán)值 (即鄰接矩陣 A): D 0 1 2 3 0 0 20 2 ? 1 ? 0 4 1 2 3 1 0 6 3 15 2 ? 0 2022/2/16 109 D(0,0)=A(0,0)=0 D(0,1)=A(0,1)=20 D(0,2)=A(0,2)=2 D(0,3)=A(0,3)=? D(1,0)=A(1,0)=? D(1,1)=A(1,1)=0 D(1,2)=A(1,2)=4 D(1,3)=A(1,3)=1 D 0 1 2 3 0 0 20 2 ? 1 ? 0 4 1 2 3 1 0 6 3 15 2 ? 0 D(2,0)=A(2,0)=3 D(2,1)=A(2,1)=1 D(2,2)=A(2,2)=0 D(2,3)=A(2,3)=6 D(3,0)=A(3,0)=15 D(3,1)=A(3,1)=2 D(3,2)=A(3,2)=? D(3,3)=A(3,3)=0 path 0 1 2 3 0 0 0,1 0,2 {} 1 {} 1 1,2 1,3 2 2,0 2,1 2 2,3 3 3,0 3,1 {} 3 當(dāng)前得到的任意兩點(diǎn)間的最短路徑長度 當(dāng)前得到的任意兩點(diǎn)間的最短路徑 2022/2/16 110 第 1步 :計算頂點(diǎn) 0經(jīng)過頂點(diǎn) 0到達(dá)各個頂點(diǎn) 0、 3的最短路徑及其長度。 D(0,0)、 D(0,1)、 D(0,2)、 D(0,3)的計算用到先前算出的最短路徑值。 D(0,0)=min{D(0,0),D(0,0)+D(0,0)}=0,路徑 path(0,0)={0} D(0,1)=min{D(0,1),D(0,0)+D(0,1)}=20,路徑 path(0,1)={0,1} D(0,2)=min{D(0,2),D(0,0)+D(0,2)}=2,路徑 path(0,2)={0,2} D(0,3)=min{D(0,3),D(0,0)+D(0,3)}=?,路徑 path(0,3)={} 0 0 0 1 2 3 D(0,0)=0 D(0,1)=20 D(0,2)=2 D(0,3)=? path(0,0)={0} path(0,1)={0,1} path(0,2)={0,2} path(0,3)={} 0 0 1 2 3 最短路徑圖 2022/2/16 111 D 0 1 2 3 0 0 20 2 ? 1 ? 0 4 1 2 3 1 0 6 3 15 2 ? 0 path 0 1 2 3 0 0 0,1 0,2 {} 1 {} 1 1,2 1,3 2 2,0 2,1 2 2,3 3 3,0 3,1 {} 3 當(dāng)前得到的任意兩點(diǎn)間的最短路徑長度 當(dāng)前得到的任意兩點(diǎn)間的最短路徑 2022/2/16 112 第 2步 :計算頂點(diǎn) 1經(jīng)過頂點(diǎn) 0到達(dá)各個頂點(diǎn) 0、 3的最短路徑及其長度。 D(0,0)、 D(0,1)、 D(0,2)、 D(0,3)的計算用到先前算出的最短路徑值。 D(1,0)=min{D(1,0),D(1,0)+D(0,0)}=?,路徑 path(1,0)={} D(1,1)=min{D(1,1),D(1,0)+D(0,1)}=0,路徑 path(1,1)={1} D(1,2)=min{D(1,2),D(1,0)+D(0,2)}=4,路徑 path(1,2)={1,2} D(1,3)=min{D(1,3),D(1,0)+D(0,3)}=1,路徑 path(1,3)={1,3} 1 0 0 1 2 3 D(1,0)= ? D(1,1)=0 D(1,2)=4 D(1,3)=1 path(1,0)={} path(1,1)={1} path(1,2)={1,2} path(1,3)={1,3} 0 0 1 2 3 先前算出的最短路徑圖 1 0 1 2 3 最短路徑圖 2022/2/16 113 D 0 1 2 3 0 0 20 2 ? 1 ? 0 4 1 2 3 1 0 6 3 15 2 ? 0 path 0 1 2 3 0 0 0,1 0,2 {} 1 {} 1 1,2 1,3 2 2,0 2,1 2 2,3 3 3,0 3,1 {} 3 當(dāng)前得到的任意兩點(diǎn)間的最短路徑長度 當(dāng)前得到的任意兩點(diǎn)間的最短路徑 2022/2/16 114 第 3步 :計算頂點(diǎn) 2經(jīng)過頂點(diǎn) 0到達(dá)各個頂點(diǎn) 0、 3的最短路徑及其長度。 D(0,0)、 D(0,1)、 D(0,2)、 D(0,3)的計算用到先前算出的最短路徑值。 D(2,0)=min{D(2,0),D(2,0)+D(0,0)}=3,路徑 path(2,0)={2,0} D(2,1)=min{D(2,1),D(2,0)+D(0,1)}=1,路徑 path(2,1)={2,1} D(2,2)=min{D(2,2),D(2,0)+D(0,2)}=0,路徑 path(2,2)={2} D(2,3)=min{D(2,3),D(2,0)+D(0,3)}=6,路徑 path(2,3)={2,3} 2 0 0 1 2 3 D(2,0)=3 D(2,1)=1 D(2,2)=0 D(2,3)=6 path(2,0)={2,0} path(2,1)={2,1} path(2,2)={2} path(2,3)={2,3} 0 0 1 2 3 先前算出的最短路徑圖 1 0 1 2 3 2 0 1 2 3 最短路徑圖 2022/2/16 115 D 0 1 2 3 0 0 20 2 ? 1 ? 0 4 1 2 3 1 0 6 3 15 2 ? 0 path 0 1 2 3 0 0 0,1 0,2 {} 1 {} 1 1,2 1,3 2 2,0 2,1 2 2,3 3 3,0 3,1 {} 3 當(dāng)前得到的任意兩點(diǎn)間的最短路徑長度 當(dāng)前得到的任意兩點(diǎn)間的最短路徑 2022/2/16 116 第 4步 :計算頂點(diǎn) 3經(jīng)過頂點(diǎn) 0到達(dá)各個頂點(diǎn) 0、 3的最短路徑及其長度。 D(0,0)、 D(0,1)、 D(0,2)、 D(0,3)的計算用到先前算出的最短路徑值。 D(3,0)=min{D(3,0),D(3,0)+D(0,0)}=15,路徑 path(3,0)={3,0} D(3,1)=min{D(3,1),D(3,0)+D(0,1)}=2,路徑 path(3,1)={3,1} D(3,2)=min{D(3,2),D(3,0)+D(0,2)}=17,路徑 path(3,2)={3,0,2} D(3,3)=min{D(3,3),D(3,0)+D(0,3)}=0,路徑 path(3,3)={3} 3 0 0 1 2 3 D(3,0)=15 D(3,1)=2 D(3,2)=17 D(3,3)=0 path(3,0)={3,0} path(3,1)={3,1} path(3,2)={3,0,2} path(3,3)={3} 0 0 1 2 3 先前算出的最短路徑圖 1 0 1 2 3 3 0 1 2 3 最短路徑圖 2 0 1 2 3 0 2022/2/16 117 D 0 1 2 3 0 0 20 2 ? 1 ? 0 4 1 2 3 1 0 6 3 15 2 17 0 path 0 1 2 3 0 0 0,1 0,2 {} 1 {} 1 1,2 1,3 2 2,0 2,1 2 2,3 3 3,0 3,1 3,0,2 3 當(dāng)前得到的任意兩點(diǎn)間的最短路徑長度 當(dāng)前得到的任意兩點(diǎn)間的最短路徑 2022/2/16 118 第 5步 :計算頂點(diǎn) 0經(jīng)過頂點(diǎn) 1到達(dá)各個頂點(diǎn) 0、 3的最短路徑及其長度。 D(0,1)、 D(1,0)、 D(1,1) 、 D(1,2) 、 D(1,3)的計算用到先前算出的最短路徑值。 D(0,0)=min{D(0,0),D(0,1)+D(1,0)}=0,路徑 path(0,0)={0} D(0,1)=min{D(0,1),D(0,1)+D(1,1)}=20,路徑 path(0,1)={0,1} D(0,2)=min{D(0,2),D(0,1)+D(1,2)}=2,路徑 path(0,2)={0,2} D(0,3)=min{D(0,3),D(0,1)+D(1,3)}=21,路徑 path(0,3)={0,1,3} 0 1 0 1 2 3 D(0,0)=0 D(0,1)=20 D(0,2)=2 D(0,3)=21 path(0,0)={0} path(0,1)={0,1} path(0,2)={0,2} path(0,3)={0,1,3} 0 0 1 2 3 先前算出的最短路徑圖 1 0 1 2 3 0 0 1 2 3 最短路徑圖 2 0 1 2 3 1 3 0 1 2 3 0 2022/2/16 119 D 0 1 2 3 0 0 20 2 21 1 ? 0 4 1 2 3 1 0 6 3 15 2 17 0 path 0 1 2 3 0 0 0,1 0,2 0,1,3 1 {} 1 1,2 1,3 2 2,0 2,1 2 2,3 3 3,0 3,1 3,0,2 3 當(dāng)前得到的任意兩點(diǎn)間的最短路徑長度 當(dāng)前得到的任意兩點(diǎn)間的最短路徑 2022/2/16 120 第 6步 :計算頂點(diǎn) 1經(jīng)過頂點(diǎn) 1到達(dá)各個頂點(diǎn) 0、 3的最短路徑及其長度。 D(1,0)、 D(1,1) 、 D(1,2) 、 D(1,3)的計算用到先前算出的最短路徑值。 D(1,0)=min{D(1,0),D(1,1)+D(1,0)}=?,路徑 path(1,0)={} D(1,1)=min{D(1,1),D(1,1)+D(1,1)}=0,路徑 path(1,1)={1} D(1,2)=min{D(1,2),D(1,1)+D(1,2)}=4,路徑 path(1,2)={1,2} D(1,3)=min{D(1,3),D(1,1)+D(1,3)}=1,路徑 path(1,3)={1,3} 1 1 0 1 2 3 D(1,0)=? D(1,1)=0 D(1,2)=4 D(1,3)=1 path(1,0)={} path(1,1)={1} path(1,2)={1,2} path(1,3)={1,3} 0 0 1 2 3 先前算出的最短路徑圖 1 0 1 2 3 1 0 1 2 3 最短路徑圖 2 0 1 2 3 3 0 1 2 3 0 1 2022/2/16 121 D 0 1 2 3 0 0 20 2 21 1 ? 0 4 1 2 3 1 0 6 3 15 2 17 0 path 0 1 2 3 0 0 0,1 0,2 0,1,3 1 {} 1 1,2 1,3 2 2,0 2,1 2 2,3 3 3,0 3,1 3,0,2 3 當(dāng)前得到的任意兩點(diǎn)間的最短路徑長度 當(dāng)前得到的任意兩點(diǎn)間的最短路徑 2022/2/16 122 第 7步 :計算頂點(diǎn) 2經(jīng)過頂點(diǎn) 1到達(dá)各個頂點(diǎn) 0、 3的最短路徑及其長度。 D(1,0)、 D(1,1) 、 D(1,2) 、 D(1,3)的計算用到先前算出的最短路徑值。 D(2,0)=min{D(2,0),D(2,1)+D(1,0)}=3,路徑 path(2,0)={2,0} D(2,1)=min{D(2,1),D(2,1)+D(1,1)}=1,路徑 path(2,1)={2,1} D(2,2)=min{D(2,2),D(2,1)+D(1,2)}=0,路徑 path(2,2)={2} D(2,3)=min{D(2,3),D(2,1)+D(1