算法設(shè)計(jì)與分析 課件 10.3.2-綜合應(yīng)用-最短路徑問題-迪杰斯特拉算法

信息工程大學(xué)算法設(shè)計(jì)與分析綜合應(yīng)用—最短路徑問題迪杰斯特拉算法國家級(jí)實(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)編號(hào)為1~n(1≤n≤100)。求從u到G中所有其余頂點(diǎn)的最短路徑長度。50102060100301012534uu1u2…uk-1ukuk+1vuu1u2…uk-1ukuk+1uu1uu1u2…最短路徑長度遞增迪杰斯特拉(Dijkstra)提出：按最短路徑長度遞增的次序，依次產(chǎn)生每個(gè)點(diǎn)的最短路徑。最短路徑問題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)：u到v的最短路徑包含u到該路徑上其它各點(diǎn)的最短路徑。邊的權(quán)值為非負(fù)判斷題。Dijkstra算法按路徑長度遞增的次序依次產(chǎn)生源點(diǎn)到各點(diǎn)的最短路徑。A.錯(cuò)誤

B.正確uu1u2…uk-1ukuk+1vuu1u2…uk-1ukuk+1uu1uu1u2…最短路徑長度遞增Dijkstra提出：按最短路徑長度遞增的次序，依次產(chǎn)生每個(gè)點(diǎn)的最短路徑。進(jìn)一步可知：第一條最短路徑：直達(dá)其他：利用已得到最短路徑的點(diǎn)，求未知點(diǎn)的最短路徑集合集合SS’S中的點(diǎn)表示已找到該點(diǎn)的最短路徑S’中的點(diǎn)表示未找到最短路徑的點(diǎn)1.將圖中點(diǎn)分成兩個(gè)集合：S和S’;集合集合SS’1.將圖中點(diǎn)分成兩個(gè)集合：S和S’；2.計(jì)算從源點(diǎn)u出發(fā)，經(jīng)S中點(diǎn)到S’中各點(diǎn)的最短路徑長度；集合集合SS’1.將圖中點(diǎn)分成兩個(gè)集合：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)分成兩個(gè)集合：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.對(duì)各點(diǎn)所處集合的狀態(tài)進(jìn)行標(biāo)記，使用數(shù)組s；2.需要存儲(chǔ)S’中各點(diǎn)的距離，使用數(shù)組dist；3.記錄點(diǎn)的前驅(qū)，使用數(shù)組pre；初始時(shí)，先將源點(diǎn)u放入S。對(duì)u之外的每個(gè)頂點(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(對(duì)每個(gè)相鄰于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)的編號(hào)，從1開始*/intdist=0x3f3f3f3f;/*dist表示長度，初值為一個(gè)較大的值*/intprev=0;/*prev表示源點(diǎn)到該點(diǎn)的最短路徑中該點(diǎn)的前驅(qū)頂點(diǎn)的編號(hào)*/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存儲(chǔ)頂點(diǎn)信息，u表示源點(diǎn)編號(hào)*/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ù)”