西電算法導(dǎo)論上機(jī)實(shí)驗(yàn)報(bào)告(共25頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 算法導(dǎo)論上機(jī)實(shí)驗(yàn)報(bào)告冊(cè) 班級(jí)： xxxxxx 學(xué)號(hào)： xxxxxxx 姓名： xxxx 教師： xxxxxx 專心-專注-專業(yè)目 錄實(shí)驗(yàn)一 排序算法1題目一：11、題目描述：12、所用算法：13、算法分析：14、結(jié)果截圖：15、總結(jié)：2題目二：31、題目描述：32、所用算法：33、算法分析：34、結(jié)果截圖：35、總結(jié)：4題目三：41、題目描述：42、所用算法：43、算法分析：54、結(jié)果截圖：55、總結(jié)：5題目四：61、題目描述：62、所用策略：63、算法分析：64、 結(jié)果截圖：65、 總結(jié)：7實(shí)驗(yàn)二 動(dòng)態(tài)規(guī)劃7題目一：71、題目描述：72、所用策略：73、算法分析：

2、74、結(jié)果截圖：85、總結(jié)：8題目二：91、題目描述：92、所用策略：93、算法分析：94、結(jié)果截圖：95、總結(jié)：10題目三：101、題目描述：102、所用策略：103、算法分析：104、結(jié)果截圖：115、總結(jié)：11題目四：111、題目描述：122、所用策略：123、算法分析:124、結(jié)果截圖：125、總結(jié)：13題目五：131、題目描述：132、所用策略：133、算法分析：134、結(jié)果截圖：145、總結(jié)：14實(shí)驗(yàn)三 貪心算法14題目一：141、題目描述：142、所用策略：143、算法分析：144、結(jié)果截圖：155、總結(jié)：16題目二：161、題目描述：162、所用策略：163、算法分析：164、

3、結(jié)果截圖：175、總結(jié)：17題目三：171、題目描述:172、所用算法：173、算法分析：174、結(jié)果截圖：185、總結(jié)：18題目四：181、題目描述：192、所用算法：193、算法分析：19實(shí)驗(yàn)四 回溯法19題目一：191、題目描述：192、所用策略：193、算法分析：19題目二：201、題目描述：212、所用策略：213、算法分析：21實(shí)驗(yàn)一 排序算法題目一： 1、題目描述：描述一個(gè)運(yùn)行時(shí)間為(nlgn)的算法，給定n個(gè)整數(shù)的集合S和另一個(gè)整數(shù)x，該算法能確定S中是否存在兩個(gè)其和剛好為x的元素。 2、所用算法：1、運(yùn)用歸并排序算法 2、在已經(jīng)排好序的基礎(chǔ)上，對(duì)其運(yùn)用二分查找。 3、算法分析

4、：（1）歸并排序運(yùn)用的是分治思想，時(shí)間復(fù)雜度為 (nlgn)，能夠滿足題目要求的運(yùn)行時(shí)間。歸并排序的分解部分是每次將數(shù)組劃分兩個(gè)部分，時(shí)間復(fù)雜度為（1）；再對(duì)已經(jīng)分解的兩個(gè)部分再進(jìn)行分解直到將數(shù)組分解成單個(gè)元素為止；解決部分是遞歸求解排序子序列；合并部分是將已經(jīng)排序的子序列進(jìn)行合并得到所要的答案，時(shí)間復(fù)雜度為(lgn)。（2）二分查找算法的時(shí)間復(fù)雜度為(lgn)在題目要求的范圍內(nèi)，二分查找的條件為待查的數(shù)組為有序序列。算法的主要思想為設(shè)定兩個(gè)數(shù)，low指向最低元素，high指向最高元素，然后比較數(shù)組中間的元素與待查元素進(jìn)行比較。如果待查元素小于中間元素，那么表明查找元素在數(shù)組的前半段；反之，如

5、果待查元素大于中間元素，那么表明查找元素在數(shù)組的后半段。 4、結(jié)果截圖： 5、總結(jié)：（1）在主函數(shù)中調(diào)用二分查找的時(shí)候，參數(shù)應(yīng)該為BinSearch(a,j+1,n,x-aj），從j+1開始遍歷而不是都是從第一個(gè)開始。（2）遇到的困難為：由于程序語(yǔ)言規(guī)定數(shù)組的下標(biāo)從0開始，而算法偽代碼要求從1開始，因此在定義數(shù)組大小的時(shí)候?qū)?shù)字加1，但是在編譯運(yùn)行的時(shí)候會(huì)得不到想要的結(jié)果，出現(xiàn)數(shù)組下標(biāo)訪問(wèn)錯(cuò)誤。 采取的解決方案為：在開始定義數(shù)組的時(shí)候，將數(shù)組的大小定義為一個(gè)較大的數(shù)字，如1000。避免在運(yùn)行時(shí)出現(xiàn)錯(cuò)誤，但是造成了空間的浪費(fèi)。較好的方案為使用動(dòng)態(tài)數(shù)組，如malloc函數(shù)。題目二： 1、題目描述：

6、實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列，即需要支持以下操作：INSERT(S,x):把元素x插入到集合S中；MAXMUM(S):返回S中具有最大key的元素；EXTRACT-MAX(S):去掉并返回S中的具有最大key的元素；INCREASE-KEY(S,x,k)：將元素x的關(guān)鍵字值增到k。 2、所用算法：堆排序，運(yùn)用堆來(lái)實(shí)現(xiàn)優(yōu)先隊(duì)列。 3、算法分析： （1）堆排序算法是引用堆這個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行信息管理。堆排序的時(shí)間復(fù)雜度是(nlgn),但是與歸并排序不同的是堆排序具有空間的原址性，任何時(shí)候都只需要常數(shù)個(gè)額外的元素空間存儲(chǔ)臨時(shí)數(shù)據(jù)。堆排序算法分為3個(gè)過(guò)程，MAX-HEAPIEY:調(diào)整堆以滿足小頂堆性質(zhì)，其時(shí)間復(fù)雜度為(

7、lgn)；BUILD-MAXHEAP:從無(wú)序的輸入數(shù)據(jù)數(shù)組中構(gòu)造小頂堆，其時(shí)間復(fù)雜度為線性時(shí)間;HEAP-SORT:對(duì)數(shù)組進(jìn)行原址排序，其時(shí)間復(fù)雜度為(nlgn)。 （2）在堆的基礎(chǔ)上實(shí)現(xiàn)優(yōu)先隊(duì)列INSERT、MAXMUM、EXTRACT-MAX、INCREASE-KEY，時(shí)間復(fù)雜度為(lgn)。 4、結(jié)果截圖： 5、總結(jié)： 遇到的困難：沒(méi)有理解將一個(gè)序列轉(zhuǎn)換成小頂堆的過(guò)程，因此剛開始很難將偽代碼用c語(yǔ)言進(jìn)行實(shí)現(xiàn)。從結(jié)果可以看出，在編寫MAX-EXSTRACT函數(shù)的時(shí)候，當(dāng)去掉第一個(gè)元素后，程序沒(méi)有調(diào)用MAX-HEAP進(jìn)行調(diào)整堆，因此最后序列是無(wú)序狀態(tài)。題目三： 1、題目描述：實(shí)現(xiàn)quick_

8、sort算法，并且回答以下兩個(gè)問(wèn)題：（1）待排數(shù)組中的元素值都相同的情況下，運(yùn)用quick_sort需要進(jìn)行多少次比較？（2）對(duì)于n個(gè)元素的數(shù)組，運(yùn)用quick_sort舉出需要進(jìn)行比較次數(shù)的上限和下限是多少？ 2、所用算法：快速排序算法 3、算法分析：快速排序采用分治策略，時(shí)間復(fù)雜度為(nlgn),但是最壞情況下為(n2),并且快速排序算法屬于原地排序，并不需要開辟空間?？焖倥判驈?fù)雜的步驟為其分解的步驟，分解的過(guò)程：數(shù)組Ap.r被劃分為兩個(gè)子數(shù)組Ap.q-1和Aq+1.r,使得Ap.q-1中的每個(gè)元素都小于Aq,而Aq也小于等于Aq+1.r中的每個(gè)元素。而在實(shí)現(xiàn)的過(guò)程總是選擇將Ar作為基準(zhǔn)點(diǎn)

9、進(jìn)行劃分Ap.r數(shù)組。 4、結(jié)果截圖： 5、總結(jié)： 問(wèn)題答案：（1）當(dāng)選取第一個(gè)或者最后一個(gè)為基準(zhǔn)點(diǎn)時(shí)，當(dāng)n個(gè)元素相同的時(shí)候?yàn)樽顗那闆r，比較次數(shù)為n*(n-1)/2;(2)快速排序比較次數(shù)最少為(nlgn),最大的比較次數(shù)為(n2)。題目四： 1、題目描述：運(yùn)用分治的策略將兩個(gè)已經(jīng)排好序的序列中，找出第k大的元素，且要求時(shí)間復(fù)雜度為(lgm+lgn),其中m和n分別為兩個(gè)序列的長(zhǎng)度。 2、所用策略：分治策略 3、算法分析： （1）分解：因?yàn)橐呀?jīng)是兩個(gè)獨(dú)立的的序列，所以不用進(jìn)行分解。 （2）解決：因?yàn)閮蓚€(gè)序列為已經(jīng)排好的序列，因此不用分開進(jìn)行排序。 （3）利用歸并排序中的merge函數(shù)，將這兩個(gè)

10、序列分別看成是L和R兩個(gè)數(shù)組，通過(guò)開辟一個(gè)新的數(shù)組，將兩個(gè)數(shù)組合并成一個(gè)新的排好序的序列，在根據(jù)要求的k值，對(duì)新的數(shù)組進(jìn)行取值。4、 結(jié)果截圖：5、 總結(jié)： （1）理解分治策略的三個(gè)步驟：分解、解決和合并對(duì)于具體問(wèn)題的具體表現(xiàn)，要善于根據(jù)時(shí)間復(fù)雜度與所學(xué)的算法進(jìn)行結(jié)合，找出可以利用的地方。 實(shí)驗(yàn)二 動(dòng)態(tài)規(guī)劃題目一： 1、題目描述：用動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)矩陣鏈乘，保證相乘的次數(shù)最少。 2、所用策略：動(dòng)態(tài)規(guī)劃 3、算法分析： （1）最優(yōu)子結(jié)構(gòu)為：如果最優(yōu)的加括號(hào)的方式將其分解為Ai.k與Ak+1.j的乘積，則分別對(duì)Ai.k與Ak+1.j加括號(hào)的方式也一定是最優(yōu)的。 （2）定義mi,j為計(jì)算矩陣Ai.j所需

11、標(biāo)量乘法次數(shù)的最小值，對(duì)于i=j時(shí),矩陣鏈乘只包含唯一的矩陣Ai,因此不需要做任何標(biāo)量乘法運(yùn)算，所以mi,i=0;當(dāng)i<j時(shí)利用最優(yōu)子結(jié)構(gòu)來(lái)計(jì)算mi,j。 （3）矩陣鏈乘的遞歸式： （4）在算法設(shè)計(jì)的時(shí)候，需要m數(shù)組記錄Ai.j最小相乘次數(shù)，s數(shù)組記錄構(gòu)造最優(yōu)解所需要的信息，其記錄的k值指出了AiAi+1Aj的最優(yōu)括號(hào)化方案的分割點(diǎn)應(yīng)在AkAk+1之間。 （5）矩陣鏈乘的時(shí)間復(fù)雜度為(n3) 4、結(jié)果截圖： 5、總結(jié)： 遇到的問(wèn)題：在構(gòu)建m數(shù)組和s數(shù)組的時(shí)候需要構(gòu)建二維數(shù)組，而c語(yǔ)言中函數(shù)的參數(shù)列表中二維數(shù)組要指明數(shù)組大小，但是還沒(méi)有輸入信息的時(shí)候并沒(méi)有方法確定數(shù)組大小。 采取的方案：由

12、于此次的例子只有兩種情況，因此對(duì)于 MATRIX_CHAIN_ORDER函數(shù)和PRINT_OPTIMAL_PARENS函數(shù)寫兩遍，大體的實(shí)現(xiàn)過(guò)程相同，只是數(shù)組的大小有所改變。并沒(méi)有解決這個(gè)情況，造成代碼的冗余。題目二： 1、題目描述：用動(dòng)態(tài)規(guī)劃求下列字符串的最長(zhǎng)公共子序列（LCS） 2、所用策略：動(dòng)態(tài)規(guī)劃 3、算法分析：（1） 最優(yōu)子結(jié)構(gòu)：令X=<x1,x2,.xm>和Y=<y1,y2,.,yn>為兩個(gè)序列，Z=<z1,z2,.,zk>為X和Y的任意LCS。1、如果xm=yn,則zk=xm=yn且Zk-1是Xm-1和Yn-1的一個(gè)LCS.2、如果xmyn,則

13、zkxm意味著Z是Xm-1和Y的一個(gè)LCS；3、如果xmyn,則zkyn意味著Z是X和Yn-1的一個(gè)LCS。（2） 定義一個(gè)bi,j指向表項(xiàng)對(duì)應(yīng)計(jì)算ci,j時(shí)所選擇的子問(wèn)題最優(yōu)解，過(guò)程返回表b和表c，cm,n保持X和Y的LCS長(zhǎng)度。（3） LCS的遞歸式為： （4） LCS的時(shí)間復(fù)雜度為(m+n),b表的空間復(fù)雜度為(mn)。 4、結(jié)果截圖： 5、總結(jié)： 用動(dòng)態(tài)規(guī)劃求取最長(zhǎng)公共子序列的時(shí)候，要理解b數(shù)組的用途和使用。 遇到的困難：編寫的代碼無(wú)法針對(duì)字符串大小未定情況下，進(jìn)行求解LCS這導(dǎo)致了代碼的冗余。題目三： 1、題目描述：用動(dòng)態(tài)規(guī)劃求取以下字符串的最長(zhǎng)公共子串。 2、所用策略：動(dòng)態(tài)規(guī)劃 3

14、、算法分析： （1）最優(yōu)子結(jié)構(gòu)：令X=<x1,x2,.xm>和Y=<y1,y2,.,yn>為兩個(gè)序列，Z=<z1,z2,.,zk>為X和Y的任意最長(zhǎng)公共子串。1、如果xm=yn,則zk=xm=yn且Zk-1是Xm-1和Yn-1的一個(gè)最長(zhǎng)公共子串.2、如果xmyn,則zkxm意味著Z是Xm-1和Y的一個(gè)最長(zhǎng)公共子串；3、如果xmyn,則zkyn意味著Z是X和Yn-1的一個(gè)最長(zhǎng)公共子串。 （2）定義Li,j為以xi和yj為結(jié)尾的相同子串的最大長(zhǎng)度。記錄著X和Y的最長(zhǎng)公共子串的最大長(zhǎng)度。 （3）最長(zhǎng)公共子串的遞歸式： （4）最長(zhǎng)公共子串的時(shí)間復(fù)雜度為(mn)，空間

15、復(fù)雜度為(mn)。 4、結(jié)果截圖： 5、總結(jié)： 要同上述的最長(zhǎng)公共子序列進(jìn)行對(duì)比，區(qū)分他們的不同之處。也要理解用動(dòng)態(tài)規(guī)劃求解時(shí)的相同之處和不同之處。題目四： 1、題目描述：給定n個(gè)整數(shù)（可能為負(fù)數(shù)）組成的序列，a1,a2.an,求該序列ai+ai+1.aj的子段和的最大值。 2、所用策略：動(dòng)態(tài)規(guī)劃 3、算法分析: (1)最優(yōu)子結(jié)構(gòu)：定義當(dāng)所給整數(shù)全為負(fù)數(shù)的時(shí)候，最大子段和為0,則最大子段和為max0,ai+ai+1.+aj,1ijn (2)引入一個(gè)輔助數(shù)組b,動(dòng)態(tài)規(guī)劃的分解分為兩步：(1)計(jì)算輔助數(shù)組的值；(2)計(jì)算輔助數(shù)組的最大值。輔助數(shù)組bj用來(lái)記錄以j為尾的子段以及集合中的最大子段和。

16、(3)最大子段和的遞歸式： (4)最大子段和使用動(dòng)態(tài)規(guī)劃進(jìn)行計(jì)算的時(shí)間復(fù)雜度為(n)。 4、結(jié)果截圖： 5、總結(jié)： 在求解集合的最大子段和的時(shí)候，要對(duì)比不同解決方法的不同之處，感受用動(dòng)態(tài)規(guī)劃解決的便捷。題目五： 1、題目描述：利用動(dòng)態(tài)規(guī)劃求出多段圖中的最短路徑 2、所用策略：動(dòng)態(tài)規(guī)劃 3、算法分析： （1）可以由圖可知，圖中的頂點(diǎn)講圖劃分7個(gè)階段，分別了解每個(gè)階段可以有幾種可供選擇的店，引入fk表示狀態(tài)k到終點(diǎn)狀態(tài)的最短距離。最優(yōu)子結(jié)構(gòu)為：當(dāng)前狀態(tài)的fk由上個(gè)狀態(tài)的fk-1和狀態(tài)k-1到狀態(tài)k的距離決定決策：當(dāng)前狀態(tài)應(yīng)在前一個(gè)狀態(tài)的基礎(chǔ)上獲得。決策需要滿足規(guī)劃方程,規(guī)劃方程：f(k)表示狀態(tài)k

17、到終點(diǎn)狀態(tài)的最短距離。 （2）多段圖最短路徑的遞歸式： 4、結(jié)果截圖： 無(wú)。 5、總結(jié)： （1）遇到的問(wèn)題：無(wú)法將多段圖的每個(gè)階段點(diǎn)的狀態(tài)表示并記錄下來(lái)。并不了解如何將動(dòng)態(tài)規(guī)劃與貪心算法的如迪杰斯特拉算法進(jìn)行對(duì)比，真正從最優(yōu)子結(jié)構(gòu)將最短路徑表示出來(lái)。實(shí)驗(yàn)三 貪心算法題目一： 1、題目描述：背包問(wèn)題，即分別計(jì)算出在0-1背包和分?jǐn)?shù)背包情況下的計(jì)算結(jié)果。 2、所用策略：動(dòng)態(tài)規(guī)劃和貪心策略 3、算法分析： （1）0-1背包問(wèn)題：所選擇的的貪心策略為按照選擇單位重量?jī)r(jià)值最大的物品順序進(jìn)行挑選。算法的步驟：設(shè)背包容量為C，共有n個(gè)物品，物品重量存放在數(shù)組Wn中，價(jià)值存放在數(shù)組Vn中，問(wèn)題的解存放在數(shù)組X

18、n中。第一步：改變數(shù)組W和V的排列順序，使其按單位重量?jī)r(jià)值Vi/Wi降序排列，并將數(shù)組Xn初始化為0；第二步初始化i=0，設(shè)計(jì)一個(gè)循環(huán)，循環(huán)終止條件為（Wi>C），循環(huán)體為將第i個(gè)物品放入背包：Xi=1;C=C-Wi;i+；最后一步：將結(jié)果存入到X數(shù)組中。 （2）分?jǐn)?shù)背包問(wèn)題：所選擇的的貪心策略為按照選擇單位重量?jī)r(jià)值最大的物品順序進(jìn)行挑選。算法的步驟：設(shè)背包容量為C，共有n個(gè)物品，物品重量存放在數(shù)組Wn中，價(jià)值存放在數(shù)組Vn中，問(wèn)題的解存放在數(shù)組Xn中。第一步：改變數(shù)組W和V的排列順序，使其按單位重量?jī)r(jià)值Vi/Wi降序排列，并將數(shù)組Xn初始化為0；第二步初始化i=0，設(shè)計(jì)一個(gè)循環(huán)，循環(huán)終

19、止條件為（Wi>C），循環(huán)體為將第i個(gè)物品放入背包：Xi=1;C=C-Wi;i+；最后一步：將結(jié)果存入到X數(shù)組中Xi=C/Wi。 （3）分?jǐn)?shù)背包問(wèn)題所采用的貪心策略之不能得到最優(yōu)解，是由于物品不允許分割，因此，無(wú)法保證最終能將背包裝滿，部分閑置的背包容量使背包的單位重量?jī)r(jià)值降低了。 （4）分?jǐn)?shù)背包問(wèn)題采用選擇單位重量?jī)r(jià)值最大的物品順序進(jìn)行挑選，其算法的時(shí)間復(fù)雜度為(nlgn)。 4、結(jié)果截圖： 5、總結(jié)： 使用貪心策略解決0-1背包問(wèn)題得出的結(jié)果并不是最優(yōu)解，這是由于所用的選擇策略不同。題目二： 1、題目描述：一個(gè)簡(jiǎn)單的調(diào)度問(wèn)題，給予工作編號(hào)為J1，J2.Jn，已知所以工作的運(yùn)行時(shí)間分別

20、為T1，T2.TN。有一個(gè)單獨(dú)的處理器，為了安排這些工作以到達(dá)減少平均完成時(shí)間的最好方法是什么。假定它是一個(gè)非搶占式調(diào)度：一旦工作開始，它必須運(yùn)行完成。 2、所用策略：貪心策略 3、算法分析： （1）由于是非搶占式調(diào)度，所以應(yīng)該盡量讓時(shí)間短的工作先做，然后再讓時(shí)間長(zhǎng)的工作做。這里我們使用堆進(jìn)行排序，建立一個(gè)小頂堆，然后每次拿出小頂堆上的最小元素，并使用sum中的公式就可以算出平均完成時(shí)間。堆排序的時(shí)間復(fù)雜度是O(nlgn)，其中BuildMinHeap的時(shí)間復(fù)雜度是O(n)，而BuildMinHeap()的時(shí)間復(fù)雜度是O(lgn)。其中HeapExtractMin(N)的時(shí)間復(fù)雜度是O(lgn

21、)。 4、結(jié)果截圖： 5、總結(jié)： 由于前面對(duì)于堆排序和優(yōu)先隊(duì)列的MIN-EXTRACT函數(shù)的錯(cuò)誤沒(méi)有解決，導(dǎo)致在調(diào)度中，需要每次去運(yùn)行時(shí)間最短的工作時(shí)發(fā)生了錯(cuò)誤。題目三： 1、題目描述:以A為源點(diǎn)，求出下圖的單源點(diǎn)最短路徑。 2、所用算法：由于圖中存在負(fù)權(quán)值，所以Dijkstra算法無(wú)法使用，因此采用Bellman-Ford算法求取圖的單源點(diǎn)最短路徑。 3、算法分析： （1）Bellman-Ford算法通過(guò)對(duì)邊進(jìn)行松弛操作來(lái)漸近地降低從源點(diǎn)A到每個(gè)結(jié)點(diǎn)的最短路徑的估計(jì)值，直到該估計(jì)值與實(shí)際的最短路徑權(quán)重(A,v)相同為止。該算法返回TRUE值當(dāng)且僅當(dāng)輸入圖中不包含可以從源結(jié)點(diǎn)到達(dá)的權(quán)重為負(fù)值的

22、環(huán)路。 （2）Bellman-Ford算法的執(zhí)行步驟：1、初始化：將除源點(diǎn)外的所有頂點(diǎn)的最短距離估計(jì)值dv+, ds0；2、迭代求解：反復(fù)對(duì)邊集E中的每條邊進(jìn)行松弛操作，使得頂點(diǎn)集V中的每個(gè)頂點(diǎn)v的最短距離估計(jì)值逐步逼近其最短距離；（運(yùn)行|v|-1次）3、檢驗(yàn)負(fù)權(quán)回路：判斷邊集E中的每一條邊的兩個(gè)端點(diǎn)是否收斂。如果存在未收斂的頂點(diǎn)，則算法返回false表明問(wèn)題無(wú)解；否則算法返回true，并且從源點(diǎn)可達(dá)的頂點(diǎn)v的最短距離保存在dv中。 （3）算法適用范圍和條件： 1.單源最短路徑(從源點(diǎn)A到其它所有頂點(diǎn)v)； 2.有向圖&無(wú)向圖(無(wú)向圖可以看作(u,v),(v,u)同屬于邊集E的有向圖)

23、； 3.邊權(quán)可正可負(fù)(如有負(fù)權(quán)回路輸出錯(cuò)誤提示)。 （4）Bellman-Ford算法的時(shí)間復(fù)雜度為(VE)。 4、結(jié)果截圖： 無(wú) 5、總結(jié)： 這次的實(shí)驗(yàn)并沒(méi)有成功，按照偽代碼進(jìn)行編寫代碼，編譯通過(guò)的時(shí)候卻沒(méi)有辦法輸出結(jié)果，或者結(jié)果是錯(cuò)誤的。題目四： 1、題目描述：求題3圖中每對(duì)結(jié)點(diǎn)的最短路徑問(wèn)題 2、所用算法：Floyd-Warshall算法。 3、算法分析： （1）設(shè)G的頂點(diǎn)為V=1,2,3.n，對(duì)于任意一對(duì)頂點(diǎn)i,j屬于V，假設(shè)i到j(luò)有路徑且中間節(jié)點(diǎn)皆屬于集合1,2,3.k，P是其中的一條最小權(quán)值路徑。就是i到j(luò)的最短路徑P所通過(guò)的中間頂點(diǎn)最大不超過(guò)k。 （2）設(shè)d(k)ij為從結(jié)點(diǎn)i到結(jié)點(diǎn)j的所有中間結(jié)點(diǎn)全部取自結(jié)合1,2,.,k的一條最短路徑的權(quán)重。d(k)ij的遞歸定義為 （3）F