弗洛伊德算法

在我們的生活中，有很多常去的地方，比如上學的學校、玩耍的公園、購物的超市，還有最溫暖的家。往返兩地之間有很多條路可以走，但有些路比較長，有些路比較短。弗洛伊德算法，就是找出從一個地方到另一個地方最短那條路的方法。

弗洛伊德算法會把每個地方都當作一個“中間站”，看通過這個“中間站”是否能讓其他兩個地方之間的距離變得更短。如果能，就把新的更短的距離記下來。經(jīng)過這樣一輪一輪的計算，最后我們就能知道任意兩地之間的最短距離。

魔法鎮(zhèn)地圖

安奇奇和小酷龍來到一個魔法小鎮(zhèn)，魔法小鎮(zhèn)上居住著企鵝、猴子、小豬、長頸鹿。小動物們的家之間以魔法道路相連，每條路的長度都不一樣。并且魔法道路是單向通行，只能從一個地方走到另一個地方，不能反向行走。安奇奇想知道，每個小動物從自己家到其他小動物的家的最短距離是多少。

答案：企鵝到猴子、小豬、長頸鹿家的最短距離分別是5，9，12；猴子到企鵝、小豬、長頸鹿家的最短距離分別是13，5，7；小豬到企鵝、猴子、長頸鹿家的最短距離分別是10，15，4；長頸鹿到企鵝、猴子、小豬家的最短距離分別是6，11，15。

解析：我們可以通過表格表示四個小動物家之間的距離，把能直接判斷得出的數(shù)據(jù)先填入，其中，表格里的“α”表示一開始不知道的最短距離。

然后，依次把每個小動物的家當“中間點”，檢查所有路線，看是否有“XX家 $$ 中間點-xx 家”比原路徑更短的。

第1輪以企鵝家為中間點

長頸鹿家-企鵝家 - 猴子家，道路

長度是 6+5=11 ，在表格中把 ∞ 改為11;長頸鹿家 $$ 企鵝家 $$ 小豬家，道路

長度是 6+9=15 ，在表格中把 ∞ 改為15。

第2輪以猴子家為中間點

企鵝家-猴子家- 小豬家，道路長度是5+5=10 ；原企鵝家-小豬家的直接長度為9，9lt;10 ，數(shù)據(jù)不用更新。

企鵝家 -猴子家 - 長頸鹿家，道路長度是5+7=12 ，在表格中把 ∞ 改為12。

第3輪，以小豬家為中間點

企鵝家 -小豬家 - 長頸鹿家，道路長度是 9+4=13 ，第2輪中填入的企鵝家$$ 長頸鹿家的道路長度是12， 12lt;13 ，數(shù)據(jù)不用更新。

猴子家 - 小豬家 - 長頸鹿家，道路長度是 5+4=9 ，原猴子家 $$ 長頸鹿家的道路長度是7， 7lt;9 ，數(shù)據(jù)也不用更新。

第4輪以長頸鹿家為中間點

小豬家 - 長頸鹿家 _ 企鵝家，道路長度是4+6=10 ，在表格中把∞改為10;

小豬家-"長頸鹿家- 猴子家，道路長度是4+11=15 （第1輪已經(jīng)算出長頸鹿家 $$ 猴子家的道路長度是11），在表格中把 ∞ 改為15；

猴子家 - 長頸鹿家- 企鵝家，道路長度是7+6=13 ，在表格中把 ∞ 改為13。

完成這4個步驟之后，表格也全部填寫完成，如右表所示。

練一練

計算思維訓練

在計算機的工作過程中，也會畫一個如前面所示的表格來記錄從每個小動物家到其他小動物家的距離。弗洛伊德算法用到了窮舉思維，即算法會考慮所有可能的中間節(jié)點，對每一對節(jié)點之間的路徑都進行檢查和比較，通過這種窮舉的方式，確保不會遺漏任何可能的最短路徑。

安奇奇準備辦生日派對，他家在小區(qū)的高處。他要把請柬送給好朋友黃大堯（住在小區(qū)的中間）和趙小羽（住在小區(qū)的最低處）。他發(fā)現(xiàn)走路太慢，于是用滑板車傳送請柬。他測了時間：

從他家滑到黃大堯家需要2分鐘；

從他家直接滑到趙小羽家需要8分鐘；

從黃大堯家滑到趙小羽家需要3分鐘。

請給出一個最合理的請柬遞送方案，要求安奇奇到達好朋友家用時最短。

（答案見52頁）