圖的應(yīng)用：最短路徑

• 思維導(dǎo)圖：
• 最短路徑的定義：
• BFS算法：(無(wú)權(quán)單源最短路徑)
• Dijkstra算法：(無(wú)權(quán)單源、帶權(quán)單源)
• • Dijkstra算法原理：
  • 算法實(shí)現(xiàn)中的輔助數(shù)組：
  • 例：
  • 如何通過(guò)path[]數(shù)組找到0到其他頂點(diǎn)的路徑？
  • Dijkstra算法的代碼實(shí)現(xiàn)：
  • Dijkstra算法適用范圍及性能：
• Floyd算法：
• • Floyd算法原理：（動(dòng)態(tài)規(guī)劃）
  • 例：
  • Floyd算法的代碼實(shí)現(xiàn)：
  • 性能分析：
  • 例：
  • 缺點(diǎn)：
• 三種算法的對(duì)比：

思維導(dǎo)圖：

最短路徑的定義：

BFS算法：(無(wú)權(quán)單源最短路徑)

void BFS_Distance(Graph G，int v){for(int i=0;i<G.vexnum;++i)d[i] = MAX;visited[v] = true;d[v] = 0;EnQueue(Q,v);while(!isEmpty(Q)){ //不空還有未遍歷到的節(jié)點(diǎn) DeQueue(Q,v); //出隊(duì)v for(w = FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)) //找到所有符合條件的鄰接節(jié)點(diǎn) if(!visited[w]){ //w是否被訪問(wèn) visited[w] = true; //修改該頂點(diǎn)對(duì)應(yīng)數(shù)組的值為trued[w] = d[v] + 1;EnQueue(Q,w); //入隊(duì) }} }

Dijkstra算法：(無(wú)權(quán)單源、帶權(quán)單源)

后續(xù)補(bǔ)充：至原理之前

Dijkstra算法原理：

注： 此算法只解決單源問(wèn)題，即從一個(gè)確定頂點(diǎn)到其他所有頂點(diǎn)的路徑問(wèn)題

ps：

1、先初始化一個(gè)空結(jié)果集 2、讓某一節(jié)點(diǎn)進(jìn)入結(jié)果集 3、從非結(jié)果集中的頂點(diǎn)中選出一條最小權(quán)重的邊，并將該邊的另一個(gè)頂點(diǎn)加入結(jié)果集 4、從結(jié)果集的頂點(diǎn)出發(fā)到新加入的頂點(diǎn)的路徑不止一條，要從多條路徑中選出最短的一條，并修改對(duì)應(yīng)數(shù)組值 5、重復(fù)3、4操作直到所有的頂點(diǎn)都加入到結(jié)果集中

要是實(shí)在看不懂，下面有具體實(shí)例講解

算法實(shí)現(xiàn)中的輔助數(shù)組：

算法實(shí)現(xiàn)中用到的輔助數(shù)組：

1、s[]數(shù)組：標(biāo)記已經(jīng)加入了結(jié)果集的頂點(diǎn) 2、dist[]數(shù)組：從一個(gè)v0（某一個(gè)確定的節(jié)點(diǎn)）出發(fā)到各個(gè)節(jié)點(diǎn)的最短路徑，若有多條路徑選擇最短的一條記錄 3、path[]數(shù)組：記錄到達(dá)該節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)的數(shù)組下標(biāo)，A->B->C,到達(dá)C的前驅(qū)節(jié)點(diǎn)為B

例：

這是重點(diǎn)，幫助理解；這是重點(diǎn)，幫助理解

后續(xù)的思路與上述相同，就不再贅述。

如何通過(guò)path[]數(shù)組找到0到其他頂點(diǎn)的路徑？

ps：
因?yàn)閜ath[4] = 2,即4的前驅(qū)是2
又path[2] = 0,即2的前驅(qū)又是0
又path[0] = -1，即0就是序列頭節(jié)點(diǎn)
所有得到了序列0—>2—>4
其他原理類似，不在贅述

Dijkstra算法的代碼實(shí)現(xiàn)：

void Dijkstra(Graph G,int v){ //圖和源點(diǎn) //初始化三個(gè)數(shù)組 int s[G.vexnum];int path[G.vexnum];int dist[G.vexnum];for(int i=0;i<G.vexnum;i++){ dist[i] = G.edge[v][i];s[i] = 0;if(G.edge[v][i] < MAX)path[i] = v;elsepath[i] = -1;} s[v] = 1;path[v] = -1;//尋找dist[]數(shù)組最小值 for(i=0;i<G.vexnum;i++){int min = MAX;int u;for(int j=0;j<G.vexnum;j++)if(s[j]==0 && dist[j]<min){min = dist[j];u = j;}s[u] = 1; //將u加入結(jié)果集 //加入了新的節(jié)點(diǎn)，更新數(shù)組 for(int j=0;j<G.vexnum;j++)if(s[j]==0 && dist[u]+G.Edge[u][j] < dist[j]){dist[j] = dist[u]+G.Edge[u][j];path[j] = u;}} }

Dijkstra算法適用范圍及性能：

時(shí)間復(fù)雜度：O(|V|2)
存在負(fù)權(quán)值的圖無(wú)法用Dijkstra算法

Floyd算法：

后期補(bǔ)充：至算法原理之前

Floyd算法原理：（動(dòng)態(tài)規(guī)劃）

A(0)矩陣表示加入0節(jié)點(diǎn)后的矩陣
A(1)矩陣表示加入節(jié)點(diǎn)1后的矩陣
ps：
在原來(lái)的結(jié)果集中加入一個(gè)節(jié)點(diǎn)k
節(jié)點(diǎn)i到節(jié)點(diǎn)k原有路徑 與 經(jīng)過(guò)k的路徑比較
選最短的一條

例：

Floyd算法的代碼實(shí)現(xiàn)：

void Floyd(Graph G){int A[G.vexnum][G.vexnum];//初始化for(int i=0;i<G.vexnum;i++)for(intj=0;j<G.vexnum;j++)A[i][j] = G.Edge[i][j];//對(duì)每一個(gè)值進(jìn)行修改for(int k=0;k<G.vexnum;k++) //考慮以Vk作為中轉(zhuǎn)點(diǎn)//修改某個(gè)值for(int i=0;i<G.vexnum;i++) //遍歷矩陣i為行號(hào)，j為列號(hào)for(intj=0;j<G.vexnum;j++)if(A[i][j] > A[i][k] + a[k][j]) //判斷路徑是否最優(yōu)A[i][j] = A[i][k] + a[k][j]; //更新最短路徑長(zhǎng)度//path[i][j] = k; }

性能分析：

時(shí)間復(fù)雜度：O(|V|^3)
空間復(fù)雜度：O(|V|^2)

例：

缺點(diǎn)：

三種算法的對(duì)比：

總結(jié)

以上是生活随笔為你收集整理的数据结构之图的应用：最短路径（Dijkstra、Floyd）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。