算法設(shè)計(jì)及分析-多段圖最短路徑問題

1、-. z.關(guān)于多段圖最短路徑問題的探討摘要：本文主要描述的是分別用動(dòng)態(tài)規(guī)劃法、貪心法和分支限界法來解決多段圖最短路徑問題時(shí)的情況，并在附錄中附有實(shí)際問題的程序來輔助闡述觀點(diǎn)。文章首先闡述了各個(gè)方法的原理，主要的思路是通過輸入一組數(shù)據(jù)，比擬三者的輸出結(jié)果的準(zhǔn)確性以及運(yùn)行時(shí)間，以之為根底來分析、討論三者的性能區(qū)別。另外，眾所周知，多段圖是有向圖的一個(gè)簡單的模型，它在有向圖的根底上忽略了兩點(diǎn)之間的線的雙向性的問題，并且對(duì)點(diǎn)與點(diǎn)之間的線有很多的要求，從而把圖簡化為可分為幾段的模式，文章最后講述了假設(shè)這幾種方法運(yùn)行到有向圖中的情況，幾種方法的比照和它們比擬適應(yīng)的使用情況的討論，并給出了自己的建議。關(guān)鍵字

2、：多段圖最短路徑問題動(dòng)態(tài)規(guī)劃法分支限界法多段圖與有向圖的關(guān)系有向圖最短路徑算法引言：當(dāng)前社會(huì)，關(guān)于最短路徑的問題屢屢出現(xiàn)。例如在開車自駕游的一個(gè)過程中，排除其他影響因素，從一個(gè)地點(diǎn)到另一點(diǎn)，這個(gè)時(shí)候必然是希望有一條距離最短的路程來盡量減少消耗的時(shí)間以及花費(fèi)的它們?cè)谀Ｐ椭斜环Q為代價(jià)，市場上對(duì)該問題的解決有很大的需求，因此，這里我將討論多段圖的最短路徑的問題。在早些時(shí)間的課程中，我們學(xué)習(xí)過數(shù)據(jù)構(gòu)造這門課程，其中就包括最短路徑這方面的討論。當(dāng)時(shí)教師給我們介紹了分別面向單源Dijkstra算法與非單源Floyd算法兩種問題的算法法-，這是我們最早的對(duì)最短路徑方面的理解，也是我們接觸的比擬早的關(guān)于圖的問

3、題。在這學(xué)期的算法課程中，我們學(xué)習(xí)了許多了方法，包括貪心法、動(dòng)態(tài)規(guī)劃法等算法，它們把以前學(xué)習(xí)的許多方法都命名并歸納分類起來，其中有許多算法都是可以用來解決這個(gè)最短路徑的問題的，并且該問題作為一個(gè)圖的問題，對(duì)該問題的繼續(xù)探討優(yōu)化的需求很大，本文將就不同算法在解決該最短路徑問題時(shí)的不同方法進(jìn)展比照并給出該問題在不同根底上不同的最終解決方案。由于時(shí)間的限制，本文將重點(diǎn)分析動(dòng)態(tài)規(guī)劃法下的情況，并會(huì)對(duì)圖的情況加以簡化、限制，最后會(huì)對(duì)其他的圖做一些拓展。首先，對(duì)多段圖最短路徑問題進(jìn)展介紹，設(shè)圖G=(V, E)是一個(gè)帶權(quán)有向連通圖，如果把頂點(diǎn)集合V劃分成k個(gè)互不相交的子集Vi2kn, 1ik，使得E中的任何

4、一條邊(u, v)，必有uVi，vVi+m1ik, 1i+mk，則稱圖G為多段圖，稱sV1為源點(diǎn)，tVk為終點(diǎn)。多段圖的最短路徑問題是求從源點(diǎn)到終點(diǎn)的最小代價(jià)路徑。由于多段圖將頂點(diǎn)劃分為k個(gè)互不相交的子集，所以，多段圖劃分為k段，每一段包含頂點(diǎn)的一個(gè)子集。不失一般性，將多段圖的頂點(diǎn)按照段的順序進(jìn)展編號(hào)，同一段內(nèi)頂點(diǎn)的相互順序無關(guān)緊要。假設(shè)圖中的頂點(diǎn)個(gè)數(shù)為n，則源點(diǎn)s的編號(hào)為0，終點(diǎn)t的編號(hào)為n-1，并且，對(duì)圖中的任何一條邊(u, v)，頂點(diǎn)u的編號(hào)小于頂點(diǎn)v的編號(hào)。這里我們討論的多段圖是可以分段的，各段之間的關(guān)系最好是單向的，即對(duì)該有向圖來說，圖中是沒有環(huán)的存在的。1.貪心法貪心法在解決問題的

5、策略上目光短淺，只根據(jù)當(dāng)前已有的信息就做出選擇，而且一旦做出了選擇，不管將來有什么結(jié)果，這個(gè)選擇都不會(huì)改變。換言之，貪心法并不是從整體最優(yōu)考慮，它所做出的選擇只是在*種意義上的局部最優(yōu)。這種局部最優(yōu)選擇并不總能獲得整體最優(yōu)解，但通常能獲得近似最優(yōu)解。本例中利用的貪心算法，是每當(dāng)要選擇下一個(gè)結(jié)點(diǎn)時(shí)，總是選擇與當(dāng)前結(jié)點(diǎn)間代價(jià)最小的點(diǎn)，這就叫做總是優(yōu)先局部最優(yōu)解。以此得到最終的解序列。這里舉一個(gè)貪心法的拓展例子Dijkstra算法。Dijkstra算法是一種最短路徑算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其它所有節(jié)點(diǎn)的最短路徑，動(dòng)態(tài)路由協(xié)議OSPF中就用到了Dijkstra算法來為路由計(jì)算最短路徑。算法本身并不是按

6、照我們的正常思維習(xí)慣，我們一般會(huì)，從原點(diǎn)遍歷所有與之相連的節(jié)點(diǎn)，找到最短路徑，再從最短路徑上的那個(gè)點(diǎn)遍歷與之相連的所有其它點(diǎn)原點(diǎn)除外，然后依次類推。這樣做雖然可以算出一個(gè)樹形，但是在大多數(shù)情況下，這種算法會(huì)產(chǎn)生很屢次優(yōu)路徑，也就是說非最短路徑。Dijkstra算法的大概過程：假設(shè)有兩個(gè)集合或者說兩個(gè)表，表A和表B表A表示生成路徑，表B表示最后確定的路徑1.從原點(diǎn)出發(fā)，遍歷檢查所有與之相連的節(jié)點(diǎn)，將原點(diǎn)和這些節(jié)點(diǎn)存放到表A中，并記錄下兩節(jié)點(diǎn)之間的代價(jià)。2.將代價(jià)最小的代價(jià)值和這兩節(jié)點(diǎn)移動(dòng)到表B中其中一個(gè)是原點(diǎn)。3.把這個(gè)節(jié)點(diǎn)所連接的子節(jié)點(diǎn)找出，放入到表A中，算出子節(jié)點(diǎn)到原點(diǎn)的代價(jià)4.重復(fù)第二步和

7、第三步直到表A為空。然后根據(jù)表B中的數(shù)據(jù)算出最優(yōu)樹。維基百科中還有另一種說法，Dijkstra算法的輸入包含了一個(gè)有權(quán)重的有向圖G，以及G中的一個(gè)來源頂點(diǎn)S。我們以V表示G中所有頂點(diǎn)的集合。每一個(gè)圖中的邊，都是兩個(gè)頂點(diǎn)所形成的有序元素對(duì)。(u,v)表示從頂點(diǎn)u到v有路徑相連。我們以E所有邊的集合，而邊的權(quán)重則由權(quán)重函數(shù)w:E0,定義。因此，w(u,v)就是從頂點(diǎn)u到頂點(diǎn)v的非負(fù)花費(fèi)值(cost)。邊的花費(fèi)可以想像成兩個(gè)頂點(diǎn)之間的距離。任兩點(diǎn)間路徑的花費(fèi)值，就是該路徑上所有邊的花費(fèi)值總和。有V中有頂點(diǎn)s及t，Dijkstra算法可以找到s到t的最低花費(fèi)路徑(i.e.最短路徑)。這個(gè)算法也可以在一

8、個(gè)圖中，找到從一個(gè)頂點(diǎn)s到任何其他頂點(diǎn)的最短路徑。具體算法見附錄。2.動(dòng)態(tài)規(guī)劃法這里先討論用動(dòng)態(tài)規(guī)劃法的解法?？紤]多段圖的最短路徑問題的填表形式。用一個(gè)數(shù)組costn作為存儲(chǔ)子問題解的表格，costi表示從頂點(diǎn)i到終點(diǎn)n-1的最短路徑，數(shù)組pathn存儲(chǔ)狀態(tài)，pathi表示從頂點(diǎn)i到終點(diǎn)n-1的路徑上頂點(diǎn)i的下一個(gè)頂點(diǎn)。則：costi=mincij+costj (ijn且頂點(diǎn)j是頂點(diǎn)i的鄰接點(diǎn)) 式6.7pathi=j (使cij+costj最小的j) 式6.8對(duì)多段圖的邊(u, v)，用cuv表示邊上的權(quán)值，將從源點(diǎn)s到終點(diǎn)t的最短路徑記為d(s, t)，則從源點(diǎn)0到終點(diǎn)9的最短路徑d(0,

9、 9)由下式確定：d(0, 9)=minc01+d(1, 9), c02+d(2, 9), c03+d(3, 9)，這是最后一個(gè)階段的決策，它依賴于d(1, 9)、d(2, 9)和d(3, 9)的計(jì)算結(jié)果，而由此模式推知，d(1, 9)=minc14+d(4, 9), c15+d(5, 9)，d(2, 9)=minc24+d(4, 9), c25+d(5, 9), c26+d(6, 9)，d(3, 9)=minc35+d(5, 9), c36+d(6, 9)，每一個(gè)di，n-1都是通過mincik+d(k,n-1)得到的ki&kn-1;再往后推的過程和以上的過程類似，將這些產(chǎn)生式得到以后，會(huì)發(fā)

10、現(xiàn)他們的求解除了兩點(diǎn)之間的代價(jià)外，在例子中，他們都依賴于d(7, 9)=c79和d(8, 9)=c89，而他們都是可以從圖上直接得到的。這樣再從末尾一層一層往上推就可以得到最終的答案了。算法主要由三局部組成：第一局部是初始化局部，其時(shí)間性能為O(n)；第二局部是依次計(jì)算各個(gè)頂點(diǎn)到終點(diǎn)的最短路徑，由兩層嵌套的循環(huán)組成，外層循環(huán)執(zhí)行n-1次，內(nèi)層循環(huán)對(duì)所有出邊進(jìn)展計(jì)算，并且在所有循環(huán)中，每條出邊只計(jì)算一次。假定圖的邊數(shù)為m，則這局部的時(shí)間性能是O(m)；第三局部是輸出最短路徑經(jīng)過的頂點(diǎn)，其時(shí)間性能是O(n)。所以，算法的時(shí)間復(fù)雜性為O(n+m)。為了實(shí)現(xiàn)時(shí)間的分析，在程序后添加了輸出運(yùn)行時(shí)間的函數(shù)

11、，以便于比照分析。具體算法、具體代碼及實(shí)驗(yàn)結(jié)果見附錄1。3.分支限界法再討論當(dāng)用分支限界法用來解決多段圖路徑問題的過程：首先對(duì)該多段圖應(yīng)用貪心法求得近似解，并算出其代價(jià)路徑。將其作為多段圖最短路徑問題的上界。而把每一段最小的代價(jià)相加，可以得到一個(gè)非常簡單的下界。于是，就可以得到了目標(biāo)函數(shù)的一個(gè)大致的*圍。由于多段圖將頂點(diǎn)劃分為k個(gè)互不相交的子集，所以，多段圖劃分為k段，一旦*條路徑的一些段被確定后，就可以并入這些信息并計(jì)算局部解的目標(biāo)函數(shù)值的下界。一般情況下，對(duì)于一個(gè)正在生成的路徑，假設(shè)已經(jīng)確定了i段1ik，其路徑為(r1, r2, , ri, ri+1)，此時(shí)，該局部解的目標(biāo)函數(shù)值的計(jì)算方法

12、即限界函數(shù)如下：應(yīng)用分支限界法同樣求解附錄中圖所示多段圖的最短路徑問題，具體的搜索過程是這樣進(jìn)展的，首先考慮根節(jié)點(diǎn)，根據(jù)限界函數(shù)算出目標(biāo)函數(shù)的值，然后下一個(gè)結(jié)點(diǎn)的選擇在本例中有三種情況，這里每種情況下的目標(biāo)函數(shù)值下界都要算出來并且加以比擬，下界的計(jì)算方法為除了加上選定點(diǎn)與初始點(diǎn)之間的距離外，以后的第一個(gè)點(diǎn)選擇一選定點(diǎn)為初始點(diǎn)到下段最小代價(jià)的路徑，以后的段與段之間的代價(jià)都按他們之間最小的代價(jià)來計(jì)算。這樣再加上根節(jié)點(diǎn)與初始階段之間的最小代價(jià)，就得到這種情況下的解了。在得到的代價(jià)中，找出最小的代價(jià)，并以之為初始結(jié)點(diǎn)循環(huán)往下做，直到到達(dá)目標(biāo)結(jié)點(diǎn)。結(jié)論：程序的運(yùn)行截圖如附錄所示。分析各個(gè)方法的整個(gè)過程得

13、到以下思考：1.貪心法、動(dòng)態(tài)規(guī)劃法和分支限界法都可以用來解決多段最短路徑問題，然而在這種情況相比之下，貪心法的運(yùn)算效率比擬高，因?yàn)樗幌窳硗鈨煞N方法一樣，需要涉及到許多的點(diǎn)。由于這里并沒有找到函數(shù)有效地給程序計(jì)時(shí)time函數(shù)很不準(zhǔn)確，而對(duì)于小程序來說，就沒有什么參考性。因此這里我們就以此題的數(shù)據(jù)為例，用一個(gè)笨方法，看各個(gè)方法訪問了多少數(shù)據(jù)，可以看到，動(dòng)態(tài)規(guī)劃法由于需要填表，并有一個(gè)相關(guān)的迭代問題，它幾乎涉及了所有的點(diǎn)；而分支限界法，它通過貪心法設(shè)置的上下限，并以他們?yōu)橐罁?jù)進(jìn)展剪枝，減少了許多的運(yùn)算量。而貪心法，訪問了最少的點(diǎn)。2.就結(jié)果準(zhǔn)確性來看，就此題例子來看，貪心法結(jié)果為0 2 4 7 9

14、，路徑的代價(jià)為20；動(dòng)態(tài)分配法采取的路徑為：0 3 5 8 9，路徑的代價(jià)為16；而分支限界法，結(jié)果為0 3 5 8 9，路徑的代價(jià)為16。可以看出，在這個(gè)方面，動(dòng)態(tài)分配法和分支限界法都到達(dá)了預(yù)期的結(jié)果，相比直線，貪心法的誤差就比擬大了。由以上的討論，我們可以看出分支限界法的綜合性能比擬好，他和動(dòng)態(tài)規(guī)劃法在解決多段最短路徑問題時(shí)都可以得到正確解，而貪心法雖然可以省時(shí)間與空間，但結(jié)果不準(zhǔn)確是它的缺點(diǎn)。各方法都是有利有弊的。因此在選擇方法時(shí)，還應(yīng)當(dāng)根據(jù)實(shí)際情況。當(dāng)只需要大概的一個(gè)解時(shí)，當(dāng)然是要用省時(shí)省力的貪心法；如果對(duì)結(jié)果又比擬高的要求的話，則就要采取動(dòng)態(tài)規(guī)劃法或分支限界法。則dijkstra算法

15、呢，他的明顯優(yōu)點(diǎn)就是它的多用性，他可以求任意一點(diǎn)到其他*一點(diǎn)的距離，但是他訪問的數(shù)據(jù)量很大，幾乎要訪問所有的邊相對(duì)于貪心法而言，因此這里來說，在單純的解決多段最短路徑問題時(shí)，他們的功能都差不多，而在解決其他較復(fù)雜的圖時(shí)，Dijkstra算法有明顯的優(yōu)越性，但當(dāng)然，作為貪心法的一種，他的結(jié)果的準(zhǔn)確性不是則的高。Dijkstra算法在本質(zhì)上為貪心算法,每一步的選擇為當(dāng)前步的最優(yōu),復(fù)雜度為O(n*n)。動(dòng)態(tài)規(guī)劃法是可以看作是對(duì)分支限界法的改良。分支限界算法,每一步的擴(kuò)散為當(dāng)前耗散度的最優(yōu),復(fù)雜度為(沒算)其實(shí)，他們各有各的優(yōu)缺點(diǎn)，可以嘗試將他們混合起來用，揚(yáng)長避短，像動(dòng)態(tài)規(guī)劃法和分支限界法，我們是不

16、是可以試著在動(dòng)態(tài)規(guī)劃法的過程中像分支限界法里一樣，設(shè)置*圍，并且過程中對(duì)肯定不會(huì)是最后結(jié)果的數(shù)據(jù)剪枝。這樣就可以提高運(yùn)行速率了。結(jié)論必須準(zhǔn)確、有條理、清晰與簡要：建議直接從結(jié)論中得出：附錄Dijstra算法邊的拓展While!(每一個(gè)dv=最短路徑)If存在一條從u到v的邊 If(du+w(u,v)=0; i-)2.1 對(duì)頂點(diǎn)i的每一個(gè)鄰接點(diǎn)j，根據(jù)式6.7計(jì)算costi;2.2 根據(jù)式6.8計(jì)算pathi;3輸出最短路徑長度cost0;4. 輸出最短路徑經(jīng)過的頂點(diǎn)：4.1 i=04.2 循環(huán)直到pathi=n-1 4.2.1 輸出pathi;4.2.2 i=pathi;用分支限界法求解多段圖

17、的最短路徑問題的算法：1根據(jù)限界函數(shù)計(jì)算目標(biāo)函數(shù)的下界down；采用貪心法得到上界up； 2將待處理結(jié)點(diǎn)表PT初始化為空； 3for (i=1; i=1) 5.1 對(duì)頂點(diǎn)u的所有鄰接點(diǎn)v 5.1.1 根據(jù)式9.3計(jì)算目標(biāo)函數(shù)值lb; 5.1.2 假設(shè)lb=up，則將i,lb存儲(chǔ)在表PT中； 5.2 如果i= =k-1且葉子結(jié)點(diǎn)的lb值在表PT中最小，則輸出該葉子結(jié)點(diǎn)對(duì)應(yīng)的最優(yōu)解； 5.3 否則，如果i= =k-1且表PT中的葉子結(jié)點(diǎn)的lb值不是最小，則 5.3.1 up=表PT中的葉子結(jié)點(diǎn)最小的lb值; 5.3.2 將表PT中目標(biāo)函數(shù)值超出up的結(jié)點(diǎn)刪除； 5.4 u=表PT中l(wèi)b最小的結(jié)點(diǎn)的

18、v值； 5.5 i=表PT中l(wèi)b最小的結(jié)點(diǎn)的i值；i+;動(dòng)態(tài)規(guī)劃法解決多段圖最短路徑問題：/*多段圖最短路徑問題總結(jié):costi表示從頂點(diǎn)i到終點(diǎn)n-1的最短路徑，pathi表示從頂點(diǎn)i到終點(diǎn)n-1的路徑上頂點(diǎn)i的下一個(gè)頂點(diǎn)；下面的公式重點(diǎn)：costi=minc(ij)+costjpathi=使c(ij)+costj最小的j; c(ij)表示i和j頂點(diǎn)之間的距離*/具體代碼如下：#include#include#define INFINITY 32767#define MA* 20_int64 start,end;int min6,Part;typedef structchar ve*sMA*

19、; /頂點(diǎn)信息int ve*num,arum; int arcsMA*MA*; /保存兩個(gè)頂點(diǎn)之間的邊長Graph; /圖的構(gòu)造體struct nodeint part,node1,node2,lb,previous;struct node *ne*t;void CreateGraph(Graph &G)/初始化多段圖int i,j;start=clock();printf(請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)：);/scanf(%d %d,&G.ve*num,&G.arum);G.ve*num=10; /頂點(diǎn)數(shù)G.arum=18; /邊的數(shù) for(i=0;iG.ve*num;i+)G.ve*si=i;for

20、(i=0;iG.ve*num;i+)for(j=0;jG.ve*num;j+)G.arcsij=INFINITY;printf(請(qǐng)按以下格式輸入邊的代價(jià)頂點(diǎn)1 頂點(diǎn)2 兩點(diǎn)之間邊的代價(jià)，頂點(diǎn)標(biāo)號(hào)從0開場：n);for(k=0;kG.arum;k+)scanf(%d %d %d,i,j,G.arcsij);int getDown(Graph G)/分支限界法求下界int j,k,i,n,n0,down=0,initial620;/initial數(shù)組用來存儲(chǔ)第i段有哪些結(jié)點(diǎn)min0=INFINITY;for(i=0;i6;i+)for(j=0;j20;j+)initialij=0;j=0;for(

21、i=0;iG.ve*num;i+)if(G.arcs0iINFINITY)initial0j+=i;if(G.arcs0imin0)min0=G.arcs0i;Part=1;down+=mini;i=0;while(initiali+0!=G.ve*num-1)n=0;j=0;mini=INFINITY;while(initiali-1j+!=0)k=0;n0=n;while(k+)G.ve*num)if(G.arcsinitiali-1j-1k-1INFINITY)initialin+=k-1;if(G.arcsinitiali-1j-1k-1mini)mini=G.arcsinitiali

22、-1j-1k-1;if(miniINFINITY)down+=mini;Part+;return down;int Greedy(Graph G,int flag,int up)/貪心法int min=INFINITY,m=flag;printf(%d,flag);for(int i=0;iG.ve*num;i+)if(G.arcsmimin)min=G.arcsmi;flag=i;if(flag);up=Greedy(G,flag,up);else printf(-%dn,flag);return up+min;void path(Graph G,int up)/分支限界法int down,

23、i,j,k,u,lb,flag=1,previous=0;struct node *p,*end,*PT,*q,*ST,*End,*mins;down=getDown(G);printf(n假設(shè)用分支限界法，該題的結(jié)果取值*圍為%d,%d。n,down,up);PT=NULL;end=NULL;ST=NULL,End=NULL;/PT用來存儲(chǔ)合格的點(diǎn)，ST表用來存儲(chǔ)由于拓展被刪除的點(diǎn)i=1;u=0; /求解第i段,u表示頂點(diǎn)，u是那個(gè)已確定的頂點(diǎn)while(flag)/ 5.1對(duì)頂點(diǎn)u的所有鄰接點(diǎn)v/5.1.1 根據(jù)式9.3計(jì)算目標(biāo)函數(shù)值lb;/5.1.2 假設(shè)lb=up，則將i,lb存儲(chǔ)在表

24、PT中；for(j=0;jG.arcsuj)for(k=0;kG.ve*num;k+)/確定了結(jié)點(diǎn)以后找到由他出發(fā)最小的代價(jià)if(G.arcsjkmini)mini=G.arcsjk;lb=G.arcsuj+mini;for(int l=i+1;l0)/計(jì)算lblb+=G.arcsPreviousU;while(Previous!=0)p=PT;while(p!=NULL)if(p-node1=Previous&p-node2=U)lb+=G.arcsPreviousU;U=Previous;Previous=p-previous;break;if(lbpart=i+1;p-node1=u;p

25、-node2=j;p-lb=lb;p-ne*t=NULL;p-previous=previous;printf(%d-%d,代價(jià)%d,上一個(gè)結(jié)點(diǎn)為%dn,p-node1,p-node2,p-lb,p-previous);if(PT=NULL) PT=p;else end-ne*t=p;end=p;end-ne*t=NULL;q=PT;lb=INFINITY;while(q!=NULL)if(q-lblb;q=q-ne*t;printf(%d %d lb=%d,mins-node1,mins-node2,lb);if(p=q & G.arcsend-node2G.ve*num-1node2;ar

26、rayPart-2=p-node1;i=Part-3;while(i=0)arrayi=p-previous;i-;q=PT;while(q-node2!=arrayp-previous)q+;if(i0)arrayi-1=q-node1;p=q;printf(最短路徑為：);for(i=0;i,arrayi);if(inode1=mins-node1&p-node2=mins-node2)/刪除PT鏈表中已被拓展的結(jié)點(diǎn)并把他添加到ST鏈表中if(ST=NULL)ST=p-ne*t;elseEnd-ne*t=p-ne*t;End=p-ne*t;End-ne*t=NULL;PT=PT-ne*t;/printf(刪除的結(jié)點(diǎn)是：%d %dn,p-ne*t-node1,p-ne*t-node2);/*elseprintf(刪除的結(jié)點(diǎn)是：%d %dn,p-ne*t-node1,p-ne*t-node2);while(p-ne*t!=NULL)if(p-ne*t-node1=mins-node1&p-ne*t-node2=mins-node2)if(ST=NULL)ST=p-ne*t;elseEnd-ne*t=p-ne*t;End=p-ne*t;End-ne*t=NULL;p-ne*t