算法設(shè)計(jì)與分析 課件 許瑾晨 第十章 -綜合應(yīng)用

信息工程大學(xué)算法設(shè)計(jì)與分析綜合應(yīng)用國家級實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版算法設(shè)計(jì)策略的分析和對比每種算法設(shè)計(jì)策略的特點(diǎn)算法設(shè)計(jì)策略間的聯(lián)系和區(qū)別最大子段和問題窮舉法窮舉法的改進(jìn)分治法動態(tài)規(guī)劃在線算法最短路徑問題單源最短路徑問題迪杰斯特拉算法（貪心法）Bellman-Ford算法SPFA算法所有點(diǎn)對間的最短路徑問題弗洛伊德算法（動態(tài)規(guī)劃）資源分配問題動態(tài)規(guī)劃貪心法回溯法分支限界法信息工程大學(xué)算法設(shè)計(jì)與分析綜合應(yīng)用—算法設(shè)計(jì)策略得對比國家級實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版遞歸分治動態(tài)規(guī)劃貪心回溯分支限界概率算法遞歸分治兩者的關(guān)系：遞歸與分治密不可分，分治要使用遞歸，而遞歸隱含著分治的思想。通常把兩者合二為一，統(tǒng)稱為遞歸與分治策略。思想：函數(shù)調(diào)用自己關(guān)鍵：遞歸式和邊界條件思想：分而治之關(guān)鍵：分、治、合分治動態(tài)規(guī)劃兩者的關(guān)系：都是通過把問題分解為子問題求解，子問題獨(dú)立時(shí)用分治，子問題有重復(fù)時(shí)用動態(tài)規(guī)劃。思想：最優(yōu)子結(jié)構(gòu)和重疊子問題關(guān)鍵：問題和子問題的最優(yōu)值遞歸關(guān)系思想：分而治之關(guān)鍵：分、治、合動態(tài)規(guī)劃貪心思想：最優(yōu)子結(jié)構(gòu)和重疊子問題關(guān)鍵：問題和子問題的最優(yōu)值遞歸關(guān)系思想：一系列局部最優(yōu)得到全局最優(yōu)關(guān)鍵：選擇正確的貪心選擇策略兩者的關(guān)系：求解的問題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)，如果具有貪心選擇性質(zhì)可以使用貪心法求解。回溯分支限界兩者的關(guān)系：求解的問題都是對解空間樹進(jìn)行搜索，邊搜索邊判斷；回溯使用深搜，分支限界使用廣搜。思想：對解空間樹進(jìn)行深度優(yōu)先搜索關(guān)鍵：設(shè)計(jì)合適的剪枝函數(shù)思想：對解空間樹進(jìn)行廣度優(yōu)先搜索關(guān)鍵：設(shè)計(jì)合適的限界函數(shù)算法設(shè)計(jì)策略之間有一定的聯(lián)系和區(qū)別；

在解決具體問題時(shí)，應(yīng)該根據(jù)問題的特點(diǎn)，選擇合適的算法設(shè)計(jì)策略，使問題得到高效求解。信息工程大學(xué)算法設(shè)計(jì)與分析綜合應(yīng)用—最大子段和問題國家級實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版已知某支股票連續(xù)若干天的價(jià)格，問：這段時(shí)間內(nèi)，應(yīng)該在哪天買入哪天賣出才能獲得最大收益？天0123456789101112131415價(jià)格1001131108510510286638110194106101799490表1：某支股票的價(jià)格變動情況思路一：找最低價(jià)和最高價(jià)思路一：最低價(jià)買入，最高價(jià)賣出。不正確最低價(jià)出現(xiàn)在第7天，最高價(jià)出現(xiàn)在第1天。思路二思路二：找最低價(jià)和最高價(jià)，從最高價(jià)向左找最低價(jià)，從最低價(jià)向右找最高價(jià)，取兩對價(jià)格中差值最大者。正確嗎？1343思路二：找最低價(jià)和最高價(jià)，從最高價(jià)向左找最低價(jià)，從最低價(jià)向右找最高價(jià)，取兩對價(jià)格中差值最大者。不正確反例：如下表中的最大收益是第2天買入、第3天賣出，與最低價(jià)和最高價(jià)無關(guān)。天01234價(jià)格10117106表2：某支股票的價(jià)格變動情況思路三：窮舉法，計(jì)算所有前后兩天的價(jià)格差，找最大的，即為最大收益。表1：某支股票的價(jià)格變動情況天0123456789101112131415價(jià)格1001131108510510286638110194106101799490intmax_value=0;fori=0ton-1forj=i+1ton{t=p[j]-p[i];if(t>max_value)max_value=t;}returnmax_value;時(shí)間復(fù)雜度為O(n2)思路四：從價(jià)格變化的角度考慮，最大收益等價(jià)于連續(xù)區(qū)間的價(jià)格變化之和最大的。表3：某支股票的價(jià)格變動情況天0123456789101112131415價(jià)格p1001131108510510286638110194106101799490變化a13-3-2520-3-16-231820-712-5-2215-4用a[i]表示第i天與前一天的價(jià)格差，則最大收益為給定一個序列，找連續(xù)區(qū)間中和的最大值。最大子段和例1：序列(-20,11,-4,13,-5,-2)的最大子段和為(11,-4,13)=20。例2：序列(-20,11,-4,-6,-5,-2)的最大子段和為(11)=11。例3：序列(-20,-11,-4,-13,-5,-2)的最大子段和為0。選擇題序列(20,11,4,6,5,2)的最大子段和為（）。A.48B.20C.0D.以上都不對窮舉法：計(jì)算所有連續(xù)區(qū)間的和，找其中最大的。a[i]a[j]1.intMaxSubsequenceSum(int*a,intn)2.{3. intThisSum,MaxSum,i,j,k;4. MaxSum=0;5. for(i=1;i<=n;i++)/*a[i]為起點(diǎn)*/6. for(j=i;j<=n;j++){/*a[j]為終點(diǎn)*/7. ThisSum=0;8. for(k=i;k<=j;k++)/*累加a[i]~a[j]*/9. ThisSum+=a[k];10. if(ThisSum>MaxSum)MaxSum=ThisSum;12.}13. returnMaxSum;14.}時(shí)間復(fù)雜度為:O(n3)窮舉法改進(jìn)：去除重復(fù)計(jì)算，優(yōu)化連續(xù)區(qū)間的求和方法。1.intMaxSubsequenceSum(int*a,intn)2.{3. intThisSum,MaxSum,i,j,k;4. MaxSum=0;5

for(i=1;i<=n;i++){/*a[i]為起點(diǎn)*/6.

ThisSum=0;7.

for(j=i;j<=n;j++){/*a[j]為終點(diǎn)*/8.

ThisSum+=a[j];9.

if(ThisSum>MaxSum)10. MaxSum=ThisSum;11.}12}13. returnMaxSum;14.}時(shí)間復(fù)雜度為O(n2)a[i]a[j]a[j+1]分治法：序列一分為二，取三種情況的最大值。情況1：左邊序列的最大子段和情況2：右邊序列的最大子段和情況3：跨越中間位置的最大子段和-2011-4135-2110131120T(n/2)T(n/2)O(n)T(n)=2T(n/2)+cn,T(1)=O(1)=O(nlogn)01376/*分治法求最大子段和*/1.intMaxSum(int*a,intleft,intright){2.intsum=0;3.intcenter=0,leftsum=0,rightsum=0,lefts=0,rights=0,s1=0,s2=0;4.if(left==right){/*如果序列長度為1，直接求解*/5.

if(a[left]>0)sum=a[left];6.

elsesum=0;7.}else{8.center=(left+right)/2;9.leftsum=MaxSum(a,left,center);/*求左序列的最大子段和*/10.

rightsum=MaxSum(a,center+1,right);/*求右序列的最大子段和*/11.

s1=0;lefts=0;12.for(inti=center;i>=left;i--){/*求中間位置向左的最大和*/13. lefts+=a[i];if(lefts>s1)s1=lefts;}14.s2=0;rights=0;15.for(intj=center+1;j<=right;j++){/*求中間位置向右的最大和*/16.

rights+=a[j];if(rights>s2)s2=rights;}17.sum=s1+s2;18.if(sum<leftsum)sum=leftsum;19.if(sum<rightsum)sum=rightsum; 20.}21.returnsum;}動態(tài)規(guī)劃：用dp[i]表示以第i項(xiàng)結(jié)尾的最大子段和dp[i]=max(dp[i-1]+a[i],a[i]),i=1~n。整個問題的最大子段和為：max(dp[i]，0)。下標(biāo)123456a[i]-2011-413-5-2dp[i]-20117152013動態(tài)規(guī)劃：用dp[i]表示以第i項(xiàng)結(jié)尾的最大子段和dp[i]=max(dp[i-1]+a[i],a[i]),i=1~n。整個問題的最大子段和為：max(dp[i],0)。/*動態(tài)規(guī)劃求解最大子段和*/1.intMaxSubsequenceSum(int*a,intn)2.{3. intMaxSum,i;4. dp[0]=0;5. MaxSum=0;/*MaxSum初始化為0，保證了最大子段和>=0*/6.

for(i=1;i<=n;i++){7. dp[i]=max(dp[i-1]+a[i],a[i]);8.

if(dp[i]>MaxSum)MaxSum=dp[i];9.}10. returnMaxSum;11.}時(shí)間復(fù)雜度為O(n)在線算法：從第1項(xiàng)開始，依次累加后面的項(xiàng)，如果小于等于0，則舍棄，否則繼續(xù)累加，記錄其中的最大值。下標(biāo)123456a[i]-2011-413-5-21172015130/*在線算法求解最大子段和*/1.intMaxSubsequenceSum(int*a,intn)2.{3. inttSum,MaxSum,j;4. tSum=MaxSum=0;5. for(j=1;j<=n;j++){6. tSum+=a[j];7. if(tSum>MaxSum)8. MaxSum=tSum;9. elseif(tSum<0)10. tSum=0;11. }12. returnMaxSum;13.}時(shí)間復(fù)雜度為O(n)在線算法：從第1項(xiàng)開始，依次累加后面的項(xiàng)，如果小于等于0，則舍棄，否則繼續(xù)累加，記錄其中的最大值。

從價(jià)格變化的角度考慮，問題等價(jià)于求解連續(xù)序列的最大和，抽象為最大子段和問題。以股票問題為例，考慮直觀的求解思路：從最高價(jià)和最低價(jià)分析，但該方法并不正確。正確方法為：計(jì)算所有可能的情況，時(shí)間復(fù)雜度為O(n2)。問題轉(zhuǎn)換討論最大子段和問題的若干求解方法:窮舉法O(n3)窮舉法的改進(jìn)O(n2)分治法O(nlogn)動態(tài)規(guī)劃O(n)在線算法O(n)信息工程大學(xué)算法設(shè)計(jì)與分析綜合應(yīng)用—最短路徑問題問題描述和分析國家級實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版最短路徑問題是圖論中的一個經(jīng)典問題，有以下幾種常見形式：確定起點(diǎn)的最短路徑問題確定終點(diǎn)的最短路徑問題確定起點(diǎn)終點(diǎn)的最短路徑問題任意兩點(diǎn)間的最短路徑問題單源最短路徑問題

給定帶權(quán)有向圖G=(V,E)，圖G的頂點(diǎn)編號為1~n(1≤n≤100)。求G中某兩點(diǎn)間的最短路徑長度。50102060100301012534從點(diǎn)1到其他點(diǎn)的最短路徑是：1-21-41-4-31-4-3-550102060100301012534邊數(shù)最長的最短路徑是1-4-3-5，這個最短路徑也包含了1到4、1到3的最短路徑?？梢詮闹邪l(fā)現(xiàn)什么？從點(diǎn)1到其他點(diǎn)的最短路徑是：1-21-41-4-31-4-3-5一般地，假設(shè)從u

到點(diǎn)v的最短路徑是u->u1->…uk->uk+1->v，那么從u到uk的最短路徑是什么？50102060100301012534從u到v的最短路徑包含了從u到u1、u2…uk、uk+1的最短路徑。最短路徑問題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)：u到v的最短路徑包含u到該路徑上其它各點(diǎn)的最短路徑。反證法：已知，一條從起點(diǎn)u到v的最短路徑:uu1…uk+1vuu1u2…uk-1ukuk+1vⅠⅡ反證法：已知，一條從起點(diǎn)u到v的最短路徑:uu1…uk+1vuu1u2…uk-1ukuk+1vⅠⅡ③做如下替換：ⅡⅠⅡⅢ④可得,路徑的長度小于路徑的長度ⅡⅠⅡⅢ⑤該結(jié)論與已知條件矛盾，假設(shè)不成立。①假設(shè)，路徑Ⅰ不是起點(diǎn)u到中間點(diǎn)uk的最短路徑。②則必然存在一條比路徑Ⅰ更短的路徑Ⅲ：uu’1…u’m-1ukuu1u2…uk-1ukuk+1vuu1u2…uk-1ukuk+1uu1uu1u2…最短路徑問題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)：u到v的最短路徑包含u到該路徑上其它各點(diǎn)的最短路徑。擴(kuò)展：u到v的最短路徑包含該路徑上任意兩點(diǎn)間的最短路徑。信息工程大學(xué)算法設(shè)計(jì)與分析綜合應(yīng)用—最短路徑問題迪杰斯特拉算法國家級實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版

給定帶權(quán)有向圖G=(V,E)，其中每條邊的權(quán)值是非負(fù)數(shù)，u稱為源點(diǎn)；圖G的頂點(diǎn)編號為1~n(1≤n≤100)。求從u到G中所有其余頂點(diǎn)的最短路徑長度。50102060100301012534uu1u2…uk-1ukuk+1vuu1u2…uk-1ukuk+1uu1uu1u2…最短路徑長度遞增迪杰斯特拉(Dijkstra)提出：按最短路徑長度遞增的次序，依次產(chǎn)生每個點(diǎn)的最短路徑。最短路徑問題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)：u到v的最短路徑包含u到該路徑上其它各點(diǎn)的最短路徑。邊的權(quán)值為非負(fù)判斷題。Dijkstra算法按路徑長度遞增的次序依次產(chǎn)生源點(diǎn)到各點(diǎn)的最短路徑。A.錯誤

B.正確uu1u2…uk-1ukuk+1vuu1u2…uk-1ukuk+1uu1uu1u2…最短路徑長度遞增Dijkstra提出：按最短路徑長度遞增的次序，依次產(chǎn)生每個點(diǎn)的最短路徑。進(jìn)一步可知：第一條最短路徑：直達(dá)其他：利用已得到最短路徑的點(diǎn)，求未知點(diǎn)的最短路徑集合集合SS’S中的點(diǎn)表示已找到該點(diǎn)的最短路徑S’中的點(diǎn)表示未找到最短路徑的點(diǎn)1.將圖中點(diǎn)分成兩個集合：S和S’;集合集合SS’1.將圖中點(diǎn)分成兩個集合：S和S’；2.計(jì)算從源點(diǎn)u出發(fā)，經(jīng)S中點(diǎn)到S’中各點(diǎn)的最短路徑長度；集合集合SS’1.將圖中點(diǎn)分成兩個集合：S和S’；2.計(jì)算從源點(diǎn)u出發(fā)，經(jīng)S中點(diǎn)到S’中各點(diǎn)的最短路徑長度；3.從S’中選擇距離最短的點(diǎn)v加入S中，并從S’中移除該點(diǎn)，同時(shí)更新S’中點(diǎn)的最短距離；集合S集合S’1.將圖中點(diǎn)分成兩個集合：S和S’；2.計(jì)算從源點(diǎn)u出發(fā)，經(jīng)S中點(diǎn)到S’中各點(diǎn)的最短路徑長度；3.從S’中選擇距離最短的點(diǎn)v加入S中，并從S’中移除該點(diǎn)，同時(shí)更新S’中點(diǎn)的最短距離；4.重復(fù)第3步，直到S’為空。算法需要的數(shù)據(jù)結(jié)構(gòu)：1.對各點(diǎn)所處集合的狀態(tài)進(jìn)行標(biāo)記，使用數(shù)組s；2.需要存儲S’中各點(diǎn)的距離，使用數(shù)組dist；3.記錄點(diǎn)的前驅(qū)，使用數(shù)組pre；初始時(shí)，先將源點(diǎn)u放入S。對u之外的每個頂點(diǎn)v，令dist[v]為邊<u,v>的權(quán)或+∞；不斷地做貪心選擇來擴(kuò)充S，直到所有頂點(diǎn)均進(jìn)入S。貪心策略：如果頂點(diǎn)v不屬于S，且dist[v]值最小，則優(yōu)先選擇v。當(dāng)v加入S后，需調(diào)整尚未進(jìn)入S的點(diǎn)的dist和pre。算法結(jié)束時(shí)，dist[i]就是u到點(diǎn)i的最短距離。迭代Svdist[2]pre[2]dist[3]pre[3]dist[4]pre[4]dist[5]pre[5]初始1101+∞-1301100111,22101602301100121,2,4410150430190431,2,4,3310150430160341,2,4,3,5550102060100301012534迭代Svdist[2]pre[2]dist[3]pre[3]dist[4]pre[4]dist[5]pre[5]初始1101+∞-1301100111,22101602301100121,2,4410150430190431,2,4,3310150430160341,2,4,3,55選擇題。根據(jù)下表，源點(diǎn)1到點(diǎn)5的最短路徑長度和最短路徑是（）。A.60,1-5

B.60,1-3-5C.60,1-4-3-5/*graph表示圖的鄰接矩陣，u表示源點(diǎn)，n表示頂點(diǎn)總數(shù)*/voidDijkstra(int**graph,intu,intn){ints[MaxSize],i=0;memset(s,0,sizeof(s));s[u]=1;for(i=1;i<=n;i++){dist[i]=graph[u][i];pre[i]=-1;}i=1;while(i<n){v為

滿足s[v]==0&&dist[v]最小的點(diǎn);s[v]=1;i++;for(對每個相鄰于v的頂點(diǎn)k){

if

（(s[k]==0)&&

(dist[v]+graph[v][k]<dist[k])）{

dist[k]=dist[v]+graph[v][k]); pre[k]=v; }}/*endfor*/}/*endwhile*/}時(shí)間復(fù)雜度：O(n2)/*借助優(yōu)先隊(duì)列實(shí)現(xiàn)迪杰斯特拉算法*/#include<iostream>#include<cstring>#include<queue>usingnamespacestd;#defineMaxSize101typedefstruct{intno;/*no表示頂點(diǎn)的編號，從1開始*/intdist=0x3f3f3f3f;/*dist表示長度，初值為一個較大的值*/intprev=0;/*prev表示源點(diǎn)到該點(diǎn)的最短路徑中該點(diǎn)的前驅(qū)頂點(diǎn)的編號*/intflag=0;/*flag=0表示源點(diǎn)到該點(diǎn)的最短路徑還未求出*/}vertex;structcomp{/*定義優(yōu)先隊(duì)列的排序規(guī)則*/booloperator()(vertexa,vertexb){returna.dist>b.dist;}};/*函數(shù)功能：dijkstra算法求解單源最短路徑*//*參數(shù)說明：n表示圖中頂點(diǎn)總數(shù)，graph表示圖的鄰接矩陣*//*a存儲頂點(diǎn)信息，u表示源點(diǎn)編號*/voiddijsktra(intn,intgraph[][MaxSize],vertexa[],intu){priority_queue<vertex,vector<vertex>,comp>p;/*定義優(yōu)先隊(duì)列*/inti=0;a[u].dist=0;/*設(shè)置源點(diǎn)到它自身的最短路徑長度為0*/p.push(a[u]);/*源點(diǎn)加入優(yōu)先隊(duì)列*/intt=0;vertexv;while(!p.empty()){v=p.top();/*取dist最小的頂點(diǎn)*/p.pop();/*dist最小的頂點(diǎn)出隊(duì)*/t=v.no;a[t].flag=1;/*出隊(duì)頂點(diǎn)的最短路徑已得到*/ ……}借助優(yōu)先隊(duì)列優(yōu)化算法時(shí)間復(fù)雜度O(|V|log|V|)單選題。

Dijkstra算法求解單源最短路徑，適用于（）。 A.權(quán)值為非負(fù) B.權(quán)值為負(fù) C.權(quán)值無要求Q：迪杰斯特拉算法為什么需要“邊的權(quán)值為非負(fù)數(shù)”？12323-101233-241236-25圖中有負(fù)值環(huán)時(shí)，不存在最短路徑；圖中無負(fù)值環(huán)但存在負(fù)值邊時(shí)，不能使用Dijkstra。圖1有負(fù)值環(huán)時(shí)，不存在最短路徑圖2有負(fù)值邊，但可以得到正確解圖3有負(fù)值邊，不能得到正確解12323-101233-241236-25信息工程大學(xué)算法設(shè)計(jì)與分析綜合應(yīng)用—最短路徑問題-貝爾曼·福特算法國家級實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版當(dāng)圖中存在負(fù)權(quán)邊時(shí)，迪杰斯特拉算法無法正確求解單源最短路徑問題。這種情況下，該如何求解呢？理查德·貝爾曼（RichardBellman）和萊斯特·福特共同提出了Bellman-Ford算法。

該算法可以求解有負(fù)權(quán)邊的單源最短路徑問題，也可以判斷圖中是否存在負(fù)環(huán)。

邊(u,v)的松弛過程：Relax(u,v,w){if(d[v]>d[u]+w(u,v)){d[v]=d[u]+w(u,v);pre[v]=u;}}d[v]：記錄源點(diǎn)s到v的最短路徑估計(jì)w(u,v)：記錄點(diǎn)u到點(diǎn)v的邊的權(quán)值pre[v]：記錄點(diǎn)v的前驅(qū)uvsBellman-Ford算法通過邊的松弛操作得到單源最短路徑。Bellman-Ford算法過程：1.對所有邊進(jìn)行(|V|-1)

輪松弛操作，得到源點(diǎn)到所有點(diǎn)的最短路徑長度；2.再進(jìn)行1輪松弛操作，如果發(fā)現(xiàn)某些點(diǎn)的最短路徑長度仍有更新，則說明圖中存在負(fù)環(huán)。

初始化點(diǎn)dpreA0-1B∞-1C∞-1D∞-1E∞-11.初始化，設(shè)源點(diǎn)為A。初始化d數(shù)組。初始化pre數(shù)組。

初始化第一輪點(diǎn)dpredpreA0-10-1B∞-1-1AC∞-12BD∞-11BE∞-11B2.對所有邊進(jìn)行第一輪松弛操作。依次遍歷邊A->B、E->D、B->D、D->B、B->E、A->C、B->C、D->C，修改d數(shù)組和pre數(shù)組。

初始化第一輪第二輪點(diǎn)dpredpredpreA0-10-10-1B∞-1-1A-1AC∞-12B2BD∞-11B-2EE∞-11B1B3.對所有邊進(jìn)行第二輪松弛操作。依次遍歷邊A->B、E->D、B->D、D->B、B->E、A->C、B->C、D->C，修改d數(shù)組和pre數(shù)組。

初始化第一輪第二輪第三輪第四輪第五輪點(diǎn)dpredpredpredpredpredpreA0-10-10-10-10-10-1B∞-1-1A-1A-1A-1A-1AC∞-12B2B2B2B2BD∞-11B-2E-2E-2E-2EE∞-11B1B1B1B1B4.對所有邊進(jìn)行第三~五輪松弛操作。依次遍歷邊A->B、E->D、B->D、D->B、B->E、A->C、B->C、D->C，修改d數(shù)組和pre數(shù)組。/*貝爾曼?福特算法求解單源最短路徑*/voidBellman-Ford(G,w,s){/*G表示有向網(wǎng)，w表示鄰接矩陣，s表示源點(diǎn)*//*1.初始化*/d[s]=0;pre[s]=-1;foreachv∈V-{s}{d[v]=+∞;pre[v]=-1;}

/*2.松弛步驟*/fori=1to|V|-1foreachedge(u,v)∈Eif(d[v]>d[u]+w(u,v)){ d[v]=d[u]+w(u,v); pre[v]=u;}

/*3.檢查是否存在負(fù)值環(huán)*/foreachedge(u,v)∈Eif(d[v]>d[u]+w(u,v)) printf(“存在負(fù)值環(huán)”);}時(shí)間復(fù)雜度：O(VE)

定理：如果圖G=(V,E)不包含負(fù)環(huán)，執(zhí)行Bellman-Ford算法后，d[v]即是源點(diǎn)s到點(diǎn)v的最短路徑距離。證明：假設(shè)v是G中的任一結(jié)點(diǎn)，從源點(diǎn)s到v、且邊數(shù)最少的最短路徑為p，如圖10-10所示：

證明：假設(shè)v是G中的任一結(jié)點(diǎn)，從源點(diǎn)v0到vk、長度最短且邊數(shù)最少的最短路徑為p，如下圖所示：

由于p是最短路徑，有d[vi]=d[vi-1]+w(vi-1,vi)。

第一輪遍歷后，有d[v1]=d[v0]+w(v0,v1)；

第二輪遍歷后，有d[v2]=d[v1]+w(v1,v2)；

……

第k輪遍歷后，有d[v]=d[vk]=d[vk-1]+w(vk-1,vk)。

由于圖G沒有負(fù)值環(huán)存在，路徑p是一條簡單路徑（邊數(shù)最少），因此，路徑p最多有(|V|-1)條邊，Bellman-Ford算法經(jīng)過(|V|-1)輪遍歷后，可以得到每個點(diǎn)的單源最短路徑。

推論：如果在(|V|-1)輪遍歷后，存在某個點(diǎn)的最短路徑距離仍然有變化，那么G中存在負(fù)值環(huán)。

如下圖所示，經(jīng)過(|V|-1)輪遍歷，可得從源點(diǎn)到v1、v2、…、vk的當(dāng)前最短路徑距離；

繼續(xù)進(jìn)行第|V|輪遍歷時(shí)，假定從vk到v2存在一條邊，此時(shí)d[v2]=min{d[v2],d[vk]+w(vk,v2)}，若d[v2]有更新，說明從源點(diǎn)s(v0)->v1->v2->…->vk->v2是比s(v0)->v1->v2更短的一條路徑，即v2->…->vk->v2構(gòu)成一個負(fù)值環(huán)。因此，推論成立。負(fù)環(huán)思考：什么情況發(fā)生松弛操作？只有d[u]更新后，從u發(fā)出的點(diǎn)才可能進(jìn)行松弛操作。

初始化第一輪第二輪第三輪第四輪第五輪點(diǎn)dpredpredpredpredpredpreA0-10-10-10-10-10-1B∞-1-1A-1A-1A-1A-1AC∞-12B2B2B2B2BD∞-11B-2E-2E-2E-2EE∞-11B1B1B1B1BBellman-Ford算法的優(yōu)化1.首先對從源點(diǎn)發(fā)出的邊進(jìn)行松弛操作；2.找到d[u]降低的點(diǎn)u，繼續(xù)對從點(diǎn)u發(fā)出的邊進(jìn)行松弛操作；3.重復(fù)步驟2，直到所有點(diǎn)的最短路徑長度d[i]都不再改變。SPFA(ShortestPathFasterAlgorithm)while(隊(duì)列不為空){取出隊(duì)列中結(jié)點(diǎn)；松弛它發(fā)出的邊；把最短路徑長度有更新的點(diǎn)加入隊(duì)列；}隊(duì)列d[A]d[B]d[C]d[D]d[E]A0∞∞∞∞B、C0-14∞∞C、D、E0-1211D、E0-1211E0-1211D0-12-210-12-21SPFA算法的局限性：1.無法判斷負(fù)環(huán)，因?yàn)橐粋€點(diǎn)可能被入隊(duì)多次2.最壞時(shí)間復(fù)雜度沒有改進(jìn)3.實(shí)際運(yùn)行效果可能不如Bellman-Ford算法上述過程是不斷發(fā)現(xiàn)問題、解決問題的過程！發(fā)現(xiàn)問題比解決問題更重要！

科學(xué)研究、創(chuàng)新研發(fā)的道路從來都不是一帆風(fēng)順的，只要朝著正確的方向，堅(jiān)持下去，一定有收獲！信息工程大學(xué)算法設(shè)計(jì)與分析綜合應(yīng)用—最短路徑問題-弗洛伊德算法國家級實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版思考：如何求解任意兩點(diǎn)間的最短路徑？

重復(fù)執(zhí)行迪杰斯特拉(Dijkstra)算法|V|次?？偟膱?zhí)行時(shí)間為O(|V|3)。

重復(fù)執(zhí)行Bellman-Ford算法|V|次?？偟膱?zhí)行時(shí)間為O(|E||V|2)，稠密圖需O(|V|4)。

弗洛伊德（Floyd）算法。時(shí)間復(fù)雜度也是O(|V|3)，但形式上非常簡潔優(yōu)雅，而且對于比較稠密的圖，實(shí)際運(yùn)行效率更快。求解任意兩點(diǎn)間的最短路徑：ikj最短路徑問題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)：u到v的最短路徑包含該路徑上任意兩點(diǎn)間的最短路徑。用d(i,j)表示i到j(luò)的最短路徑長度，k是該路徑上的一個中間點(diǎn)（k=1,2,3,…,n），那么有d(i,j)=min{w(i,j),d(i,k)+d(k,j)},w(i,j)是邊(i,j)的權(quán)值定義d[k][i][j]：中間點(diǎn)編號≤k，點(diǎn)i到點(diǎn)j之間的最短路徑長度。iji1jk=1時(shí)，d[1][i][j]得到中間點(diǎn)編號不超過1的最短路徑長度，包括：直達(dá)路徑以1號點(diǎn)為中間點(diǎn)的路徑d[k][i][j]的含義：中間點(diǎn)編號≤k，點(diǎn)i到點(diǎn)j之間的最短路徑長度。k=2時(shí)，d[2][i][j]得到中間點(diǎn)編號不超過2的最短路徑長度，包括：i1jiji2ji2j1i1j2直達(dá)路徑以1號點(diǎn)為中間點(diǎn)的路徑以2號點(diǎn)為中間點(diǎn)的路徑依次經(jīng)過1、2點(diǎn)的路徑依次經(jīng)過2、1點(diǎn)的路徑d[k][i][j]的含義：中間點(diǎn)編號≤k，點(diǎn)i到點(diǎn)j之間的最短路徑長度。k=n時(shí)，d[n][i][j]得到中間點(diǎn)編號不超過n的最短路徑長度，即i到j(luò)的最短路徑長度?？梢园凑罩虚g點(diǎn)編號k從小到大的順序?qū)ふ易疃搪窂?。關(guān)鍵問題：已知d[k-1][i][j]，如何求解d[k][i][j]？d[k][i][j]的含義：中間點(diǎn)編號≤k，點(diǎn)i到點(diǎn)j之間的最短路徑長度。對于d[k][i][j]，可以分為兩種情況：（1）i到j(luò)的最短路不經(jīng)過k：d[k][i][j]=d[k-1][i][j]。（2）i到j(luò)的最短路經(jīng)過k：d[k][i][j]=d[k-1][i][k]+d[k-1][k][j]。d[i][j]=min(d[i][j],d[i][k]+d[k][j]),

k,i,j∈[1,n];d[k][i][j]的含義：中間點(diǎn)編號≤k，點(diǎn)i到點(diǎn)j之間的最短路徑長度。弗洛伊德算法(Floyd)因此，最短路徑的遞歸關(guān)系式：d[k][i][j]=min(d[k-1][i][j],d[k-1][i][k]+d[k-1][k][j])

（k,i,j∈[1,n]）[例]給出一個有向網(wǎng)及其鄰接矩陣A。用Floyd算法求該有向網(wǎng)中每對頂點(diǎn)之間的最短路徑長度及其最短路徑。d(0)[i][j]的含義是：從vi到vj的直達(dá)的最短路徑長度d(0)v1(a)

v2(b)

v3(c)

v4(d)0

5∞

∞10061

∞04∞820v1v2v3v4d(0)v1(a)

v2(b)

v3(c)

v4(d)0

5∞

∞10061

∞04∞820v1v2v3v4v1v2v3v40

5∞

∞10061

∞04∞820v1v2v3v4d(1)v1v2v3v40

5∞

∞0613804∞820v1v2v3v4d(1)v1v2v3v40

5∞

∞0613804∞820v1v2v3v4v1v2v3v40

5∞

∞0613804∞820v1v2v3v4d(2)v1v2v3v40

5116061380418820v1v2v3v4v1v2v3v40

511

610061

80418820v1v2v3v4d(3)v1v2v3v40

511

6906138045820v1v2v3v4v1v2v3v40

511

6906138045820v1v2v3v4d(4)v1v2v3v40

586603138045820v1v2v3v4d(2)v1v2v3v40

5116061380418820v1v2v3v4d(3)v1v2v3v40

511

6906138045820v1v2v3v4單選題。以下說法正確的是（）。A.Floyd算法適用于權(quán)值為負(fù)的情況B.Floyd算法不適用于權(quán)值為負(fù)的情況p(0)[i][j]=i的含義是：從vi到vj的最短路徑中，vj的前驅(qū)結(jié)點(diǎn)為vip(4)[2][1]=4的含義是：從v2到v1的最短路徑中，v1的前驅(qū)為點(diǎn)v4p(0)v1v2v3v41

1-1-122223-133-1444v1v2v3v4p(1)v1v2v3v41

1-1-122223133-1444v1v2v3v4p(2)v1v2v3v41

122222231332444v1v2v3v4p(3)v1v2v3v41

122322231333444v1v2v3v4p(4)v1v2v3v41

142424231333444v1v2v3v4單選題。下圖是最終得到的前驅(qū)矩陣，從V1到V3點(diǎn)的最短路徑是（）。 A.v1-v4-v3 B.v1-v3 C.v1-v2-v4-v3 D.以上都不對P(4)v1v2v3v41

142424231333444v1v2v3v4void

floyd(){/*Floyd算法求解任意兩點(diǎn)間的最短路徑*//*初始化*/

for(int

i=1;i<=n;i++)

for(int

j=1;j<=n;j++)

d[0][i][j]=graph[i][j];

/*自底向上動態(tài)規(guī)劃求解*/

for(int

k=1;k<=n;k++){

for(int

i=1;i<=n;i++){

for(int

j=1;j<=n;j++){

d[k][i][j]=min(d[k-1][i][j],d[k-1][i][k]+d[k-1][k][j]);

}

}}}時(shí)間復(fù)雜度：O(n3)空間復(fù)雜度：O(n2)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);d[i][j]=graph[i][j];信息工程大學(xué)算法設(shè)計(jì)與分析綜合應(yīng)用—資源分配問題國家級實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版

有一筆資金共計(jì)m份，現(xiàn)給n個工程項(xiàng)目投資，給第i項(xiàng)工程投資資金j(份)所得的收益用p(i,j)(i,j為非負(fù)整數(shù))表示。問應(yīng)該如何分配資金，使得投資的收益最大。

比如m=4，n=3時(shí)，p(i,j)如下表所示，給工程1、2、3分別分配資金1、1、2時(shí)獲得最大收益為43。投資金額01234工程1收益013151922工程2收益01213.514.516工程3收益014182124分配資金的方法很多，從中選擇收益最大的。該問題是一個最優(yōu)化問題，如果符合最優(yōu)子結(jié)構(gòu)性質(zhì)，進(jìn)一步判斷是否可用動態(tài)規(guī)劃和貪心法求解。該問題也是一個搜索問題，可以用回溯法、分支限界求解。結(jié)合實(shí)例分析：當(dāng)m=4，n=3時(shí)，對應(yīng)的最優(yōu)解為（1，1，2），那么，(1,1)是2份資金給工程1、2投資對應(yīng)的最佳分配方案。投資金額01234