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