【正文】 ,j , k ]為 ? 路徑中間只允許經過節(jié)點 1…k 的情況下 ? i到 j的最短路距離 ? 它有兩種情況 ? 最短路經過點 k， d[i,j,k]=d[i,k,k1]+d[k,j,k1] ? 最短路不經過點 k， d[i,j,k]=d[i,j,k1] ? 綜合起來，狀態(tài)轉移方程為 d[i,j,k]=min{ d[i,k,k1] + d[k,j,k1],d[i,j,k1] } ? 邊界條件 d[i,j,0]=len[i][j]（不存在的邊權可為 ∞） 最短路徑 Floyd算法 算法描述 6： SP_Floyd( G ) //求每對節(jié)點的最短距離 for i=1 to n do for j=1 to n do dis[i,j] ? len[i][j]。 // 初始化邊界條件 for k=1 to n do //K放在最外層，數組少一維 for i=1 to n do for j=1 to n do if( dis[i,k]+dis[k][j]dis[i,j]) //狀態(tài)轉移 dis[i,j] ? dis[i][k]+dis[k][j]。 最短路徑 Floyd算法 Floyd算法的思考 ? Floyd算法怎樣記錄下最短路徑？ ? Floyd算法怎樣判斷負環(huán)？ ? 求圖中的最小環(huán)問題。 最短路徑 Floyd算法 ? Dijkstra ? 單源 非負 O(|V|2) 對稠密圖好 ? 可用“堆”優(yōu)化 O(|E|*log|V|) 對稀疏圖較好 ? BellmanFord ? 單源 無負環(huán) O(|V|*|E|) ? 可先用 Dijkstra預處理優(yōu)化 ? SPFA用更新隊列優(yōu)化 ,時間復雜度平均好，但不確定。 ? Floyd ? 全源 無負環(huán) O(|V|2) 思考： 有多源問題類嗎？ 如果邊權只有 0,1(或 0,1,2,3,4)，能否優(yōu)化算法？ 最短路徑 算法比 較 最短路徑 實 例三 butter 農夫 John發(fā)現做出全威斯康辛州最甜的黃油的方法：糖。把糖放在一片牧場上，他知道 N只奶牛會過來舔它，這樣就能做出能賣好價錢的超甜黃油。 農夫 John可以訓練這些奶牛，讓它們在聽到鈴聲時去一個特定的牧場。他打算將糖放在那里然后下午發(fā)出鈴聲，以至他可以在晚上擠奶。 農夫 John知道每只奶牛都在各自喜歡的牧場（一個牧場不一定只有一頭牛）。給出各頭牛所在的牧場和牧場間的路線，找出使所有牛到達的路程和最短的牧場（他將把糖放在那） 最短路徑 實 例三 輸入格式 第一行 : 三個數，奶牛數 N（ 1=N=500） , 牧場數 P（ 2=P=800），牧場間道路數 C (1=C=1450) 第二行到第 N+1行 : 1 到 N 頭奶牛所在的牧場號 第 N+2行到第 N+C+1行 ： 每行有三個數 ,相連的牧場 A、 B，兩牧場間距離 D（ 1=D=255），當然 ,連接是雙向的 . 輸出格式 一行 : 輸出奶牛必須行走的最小的距離和 最短路徑 實 例三 輸入樣例 3 4 5 2 3 4 1 2 1 1 3 5 2 3 7 2 4 3 3 4 5 輸出樣例 8 { 說明： 放在 4號牧場最優(yōu) } 樣例圖形 P2 P1 @1@ C1 \ |\ \ | \ 5 7 3 \ | \ \| \ C3 C2 @5@ P3 P4 最短路徑 實 例三 分析 ? 若用 Floyd算法預處理，顯然 P3=80035*108要超時。 ? 邊比較少，可枚舉每一點為源，再用 Dijkstra算法 +堆優(yōu)化來處理 : P*C*logP =800* 1450*log800*107 不超時 參考程序見附件 參考程序 ? 用 SPFA算法平均來說效果最好，試用一下。 參考程序見附件 參考程序 最短路徑 實 例三 總結 ? 堆優(yōu)化的 Dijkstra不能處理負邊的情況，而SPFA則可以 ? 堆優(yōu)化的 Dijkstra時間復雜度穩(wěn)定，而 SPFA的時間復雜度不穩(wěn)定。 ? SPFA的實現比 堆優(yōu)化的 Dijkstra簡單，平均速度也較快。 實際運用中，我們一般根據題目的各種條件來選擇這 2種算法中的一種。 圖遍歷拓展問題 ? 有向無環(huán)圖的拓撲排序 ? 連通塊 ? 有向圖的強連通分量 ? 關鍵節(jié)點、橋 ? 歐拉路（一筆畫）問題 ? 工程圖的關鍵路徑 ? 差分約束系統(tǒng) 圖 圖 的 補 充基 礎 算法 圖的遍歷 :歐拉路問題 結論 1 ：無向圖存在歐拉回路的充要條件是： ? 圖是連通的。 ? 圖中所有點的度均為偶數。 結論 2：無向圖歐拉路存在的充要條件： ? 圖是連通的。 ? 圖中有且僅有 2個度數為奇數的點，并且這兩個點一定是這條歐拉路的起點和終點。 圖 圖 的 補 充基 礎 算法 圖的遍歷 :歐拉路問題 結論 3：有向圖 G，存在歐拉回路的充要條件是： ? 基圖（原有向邊改為無向邊后所得的無向圖）連通 ? 所有點的出度和入度相同 結論 4：有向圖 G，存在歐拉路的充要條件是： ? 基圖連通 ? 有且僅有一個點入度比出度大 1，且這個點是歐拉路的終點 ? 有且僅有一個點入度比出度小 1，且這個點是歐拉路的起點 ? 其他所有的點入度和出度相等 圖 圖 的 補 充基 礎 算法 圖的遍歷 :一筆畫問題程序 下面是用鄰接矩陣寫的程序。用鄰接鏈表的程序 或 兩點之間有多條邊的程序 要適當修改取邊與刪邊處理。 void DFS( int v) //遞歸寫法 { visited[v] = true。 for ( int i = 0。 in。 i++ ) if (g[v][i]) { g[v][i] = g[i][v] = false。 DFS(i)。 } ans[ ansI++ ] = v。 } 圖 圖 的 補 充基 礎 算法 圖的遍歷 :一筆畫問題程序 void trave(int v) { //非遞歸寫法 int i。 visited[v] = true。 que [ 0 ] = v。 while ( queI = 0 ) { v = que[ queI ] 。 if ( get_next(v,i) ) { //取 v的相鄰邊 (v,i) g[v][i] = g[i][v] = 0。 visited[i] = true。 que[ ++queI ] = i。 //訪問點進棧 } else ans[ ansI++ ] = que [ queI ]。 //出棧，放入答案隊列 } } 圖 圖 的 補 充基 礎 算法 updata 剪切原理等 圖 —加 兩個 圈 程序 用 不同 的 底色 分 段 Mst的 圖 示