Key word:
??? ①最短路
??? ②傳遞閉包:大小關系 數值關系 先后關系 聯通關系
??? ③floyd變形
??? ④實現方式:插點發法
??? ⑤思想:動態規劃

1.最短路:
最短路是floyd的一個基本應用，但是對于不是裸題的最短路該怎么使用是我們要關注的，其次什么時候使用也是要注意的，至于什么時候使用Floyd，首先先看數據量，三重循環始終是Floyd不可避免的，所以200的點是極限，小于兩百的時候，就要考慮，這個最短路如果考察Floyd那么他一定有坑，或者改變問的方式及在floyd過程中的處理操作，這里放到3，簡單的有求一條最短路，最短路經過邊需要花費，經過節點也需要花費，這時候就需要稍稍處理，復雜的也會有很多提問方式，要敏感，因為floyd的很多特性是其他最短路所沒有的，多源最短路，關系的傳遞性這里放到2，例如給出最短路，在原圖中刪去一些邊是使得給出最短路仍是最短路，因為Floyd動態規劃的特性，他具有能夠遍歷所有的狀態的特點，所有他能夠找到任何邊判斷能否被松弛，這里是被替換。所以掌握好Floyd是做題的關鍵。
2.傳遞閉包:
這里是對關系的傳遞，這點用起來很舒服，比如匯率問題，求一種貨幣能經過若干次兌換變成更多的自己，這里的話我們考慮，dis[i][j]為i與j的匯率，那么松弛時則有dis[i][k]* dis[k][j]與dis[i][j]比較大小，這個時候Floyd傳遞的不再是數值關系，而是大小關系，這也算是最短路的變形，最大乘積路(?)。
3.Floyd 變形:
剛才也舉了很多例子了，他們都是屬于Floyd變形，至于為什么拿出來說是因為Floyd不可能考裸體(實在想考，那也沒辦法)，考的都是變形題目，那么怎么變形很成問題，所以怎么變形，怎么去找題意是解決問題的關鍵，出題人的想法千奇百怪，你真的想不到他會怎么考你，所以做到所有的floyd是不現實的，即使floyd不難，但是我們還是通過題目找到了規律，所有的題目的考察都是根據2，4，5所改造的，那么理解4，5是解題關鍵。
4、5.這里一起說一下，動態規劃思想在這里是最小化的枚舉各種松弛情況，可以理解為區間DP相似的思想，也就是說關于I J之間的關系，可以通過floyd解決，在就是插點法，在兩點外插入點以獲得松弛操作，比如在一個圖中，給你幾條邊讓你添加到圖中使得起點終點距離最小，這就是插點，插點更新距離即可。
這是我的總結，有不太對的地方，希望可以指出，共同進步。

總結

以上是生活随笔為你收集整理的图论--Floyd总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。