前言：

?????一直想去外面的世界看看，中國(guó)城市那么多，那么美，怎么樣才可以用最少的錢，最短的時(shí)間游遍我想去的城市呢？（我在做夢(mèng)？不不不！迪杰斯特拉算法和弗洛伊德算法來了）
?????這兩個(gè)算法有著廣泛的用途，讓我們來康康：

（***后附代碼演示哦！！！*** ）

多么厲害的應(yīng)用啊，那么讓我們來一起學(xué)習(xí)吧！

一、迪杰斯特拉算法（Dijkstra）

?????首先說說迪杰斯特拉算法的求解過程：

• 對(duì)于網(wǎng)N=（V，E），將N中的頂點(diǎn)分成兩組：
• 第一組 S：已求出的最短路徑的終點(diǎn)集合（初始時(shí)只包含源點(diǎn)v0）
• 第二組V-S：尚未求出的最短路徑的頂點(diǎn)集合（初始時(shí)為V-{v0}）
• 算法將按各頂點(diǎn)與v0間最短路徑長(zhǎng)度遞增的次序，逐個(gè)將集合V-S中的頂點(diǎn)加入到集合S中去。在這個(gè)過程中，總保持v0到集合S中各頂點(diǎn)的路徑長(zhǎng)度始終不大于到集合V-S中各頂點(diǎn)的路徑長(zhǎng)度。

總結(jié)歸納：首先我們知道，這點(diǎn)很重要！

在這條路徑上，必定只含一條邊，并且這條邊是所有從源點(diǎn)v0出發(fā)的所有邊中權(quán)值最小的一條。那么你想，到其它邊最小的，肯定要經(jīng)過之前最小的鄰接邊，所以核心思想我們可以說成是依各條最短路徑的長(zhǎng)度遞增的次序依次求得各條路徑。

• 下一條路徑長(zhǎng)度次短的最短路徑的特點(diǎn):
• （假設(shè)其終點(diǎn)為vk）
• 它只可能有兩種情況:
  或者是直接從源點(diǎn)到該頂點(diǎn)的邊: <v0?vk> (只含一條邊)；
  或者是，從源點(diǎn)經(jīng)過頂點(diǎn)u，再到達(dá)該頂點(diǎn)的兩條邊組成: <v0 ?u> < u ?vk>。
  • 依次類推：
  • 一般情況下,下一條最短路徑的特點(diǎn)： 它或者是直接從源點(diǎn)直達(dá)該頂點(diǎn)的一條弧；
    或者是，從源點(diǎn)經(jīng)過已求得了最短路徑的頂點(diǎn)集合中的頂點(diǎn)，再到達(dá)該頂點(diǎn)。

算法步驟：

這里需要知道存儲(chǔ)結(jié)構(gòu)一點(diǎn)知識(shí)有： 鄰接矩陣G[n][n] (或者鄰接表) 輔助數(shù)組： 數(shù)組S[n]： 記錄相應(yīng)頂點(diǎn)是否已求出最短路徑
數(shù)組D[n]： 記錄當(dāng)前所求出的從源點(diǎn)到相應(yīng)頂點(diǎn)的最短路徑長(zhǎng)度 數(shù)組Path[n]： 記錄相應(yīng)頂點(diǎn)路徑中的前驅(qū)頂點(diǎn)

(1)初始化：

• 將源點(diǎn)v0加到S中，即S[v0]=true;
• 將v0到各個(gè)終點(diǎn)的最短路徑長(zhǎng)度初始化為權(quán)值，即D[i]=G.arcs[v0][vi]，(vi∈V-S);
• 如果v0和頂點(diǎn)vi之間有弧，則將vi的前驅(qū)置為v0，即Path[i]=v0，否則Path[i]=-1。
  （2）循環(huán)n-1次，執(zhí)行以下操作：
• 選擇下一條最短路徑的終點(diǎn)vk，使得：
  ????D[k]=Min{D[i]|vi∈V-S}
• 將vk加到S中，即S[k]=true;
• 根據(jù)條件更新從v0出發(fā)到集合V-S上任一頂點(diǎn)的最短路徑的長(zhǎng)度，若條件D[k]+G.arcs[k][i]<D[i]成立，則更新D[i]=D[k]+G.arcs[k][i]，同時(shí)更改vi的前驅(qū)為vk；Path[i]=k。
  為了更好的理解，將上面的總結(jié)就是：

1.初始化：先找出從源點(diǎn)v0到各終點(diǎn)vk的直達(dá)路徑（v0,vk），即通過一條弧到達(dá)的路徑。
2.選擇：從這些路徑中找出一條長(zhǎng)度最短的路徑（v0,u）。
3.更新：然后對(duì)其余各條路徑進(jìn)行適當(dāng)調(diào)整：
判斷：若在圖中存在弧（u,vk），且（v0,u）+（u,vk）<（v0,vk）,
則以路徑（v0,u,vk）代替（v0,vk）。
在調(diào)整后的各條路徑中，再找長(zhǎng)度最短的路徑，
依此類推。

看這個(gè)例子更好的理解：

求這個(gè)圖的最短路徑就有：

二、弗洛伊德算法

?????迪杰斯特拉是從一個(gè)點(diǎn)到其余各點(diǎn)的最短路徑，二弗洛伊德則是每對(duì)頂點(diǎn)之間的最短路徑。這個(gè)時(shí)候聰明的你是不是想到調(diào)用迪杰斯特拉算法呢？一起來看看趴
?????弗洛伊德算法的基本思想是：
????????????????????從 vi 到 vj 的所有可能存在的路徑中，選出一條長(zhǎng)度最短的路徑
算法：
若<vi,vj>存在，則存在路徑{vi,vj}
// 路徑中不含其它頂點(diǎn)
若<vi,v1>,<v1,vj>存在，則存在路徑{vi,v1,vj}
// 路徑中所含頂點(diǎn)序號(hào)不大于1
若{vi,…,v2}, {v2,…,vj}存在，
則存在一條路徑{vi, …, v2, …vj}
// 路徑中所含頂點(diǎn)序號(hào)不大于2
…
依次類推，則 vi 至 vj 的最短路徑應(yīng)是上述這些路徑中，路徑長(zhǎng)度最小者。

****下面演示代碼：
迪杰斯特拉算法：

//算法 迪杰斯特拉算法#include <iostream> using namespace std;#define MaxInt 32767 //表示極大值，即∞ #define MVNum 100 //最大頂點(diǎn)數(shù) typedef char VerTexType; //假設(shè)頂點(diǎn)的數(shù)據(jù)類型為字符型 typedef int ArcType; //假設(shè)邊的權(quán)值類型為整型int *D=new int[MVNum]; //用于記錄最短路的長(zhǎng)度 bool *S=new bool[MVNum]; //標(biāo)記頂點(diǎn)是否進(jìn)入S集合 int *Path=new int[MVNum]; //用于記錄最短路頂點(diǎn)的前驅(qū)//------------圖的鄰接矩陣----------------- typedef struct{VerTexType vexs[MVNum]; //頂點(diǎn)表ArcType arcs[MVNum][MVNum]; //鄰接矩陣int vexnum,arcnum; //圖的當(dāng)前點(diǎn)數(shù)和邊數(shù) }AMGraph;int LocateVex(AMGraph G , VerTexType v){//確定點(diǎn)v在G中的位置for(int i = 0; i < G.vexnum; ++i)if(G.vexs[i] == v)return i;return -1; }//LocateVexvoid CreateUDN(AMGraph &G){//采用鄰接矩陣表示法，創(chuàng)建無向網(wǎng)Gint i , j , k;cout <<"請(qǐng)輸入總頂點(diǎn)數(shù)，總邊數(shù)，以空格隔開:";cin >> G.vexnum >> G.arcnum; //輸入總頂點(diǎn)數(shù)，總邊數(shù)cout << endl;cout << "輸入點(diǎn)的名稱:，如a" << endl;for(i = 0; i < G.vexnum; ++i){cout << "請(qǐng)輸入第" << (i+1) << "個(gè)點(diǎn)的名稱:";cin >> G.vexs[i]; //依次輸入點(diǎn)的信息}cout << endl;for(i = 0; i < G.vexnum; ++i) //初始化鄰接矩陣，邊的權(quán)值均置為極大值MaxIntfor(j = 0; j < G.vexnum; ++j)G.arcs[i][j] = MaxInt;cout << "輸入邊依附的頂點(diǎn)及權(quán)值，如a b 7" << endl;for(k = 0; k < G.arcnum;++k){ //構(gòu)造鄰接矩陣VerTexType v1 , v2;ArcType w;cout << "請(qǐng)輸入第" << (k + 1) << "條邊依附的頂點(diǎn)及權(quán)值:";cin >> v1 >> v2 >> w; //輸入一條邊依附的頂點(diǎn)及權(quán)值i = LocateVex(G, v1); j = LocateVex(G, v2); //確定v1和v2在G中的位置，即頂點(diǎn)數(shù)組的下標(biāo)G.arcs[i][j] = w; //邊<v1, v2>的權(quán)值置為wG.arcs[j][i] = G.arcs[i][j]; //置<v1, v2>的對(duì)稱邊<v2, v1>的權(quán)值為w}//for }//CreateUDNvoid ShortestPath_DIJ(AMGraph G, int v0){//用Dijkstra算法求有向網(wǎng)G的v0頂點(diǎn)到其余頂點(diǎn)的最短路徑int v , i , w , min;int n = G.vexnum; //n為G中頂點(diǎn)的個(gè)數(shù)for(v = 0; v < n; ++v){ //n個(gè)頂點(diǎn)依次初始化S[v] = false; //S初始為空集D[v] = G.arcs[v0][v]; //將v0到各個(gè)終點(diǎn)的最短路徑長(zhǎng)度初始化為弧上的權(quán)值if(D[v] < MaxInt) Path [v] = v0; //如果v0和v之間有弧，則將v的前驅(qū)置為v0else Path [v] = -1; //如果v0和v之間無弧，則將v的前驅(qū)置為-1}//forS[v0]=true; //將v0加入SD[v0]=0; //源點(diǎn)到源點(diǎn)的距離為0/*―初始化結(jié)束，開始主循環(huán)，每次求得v0到某個(gè)頂點(diǎn)v的最短路徑，將v加到S集―*/for(i = 1;i < n; ++i){ //對(duì)其余n-1個(gè)頂點(diǎn)，依次進(jìn)行計(jì)算min= MaxInt;for(w = 0; w < n; ++w)if(!S[w] && D[w] < min){ //選擇一條當(dāng)前的最短路徑，終點(diǎn)為vv = w;min = D[w];}//ifS[v]=true; //將v加入Sfor(w = 0;w < n; ++w) //更新從v0出發(fā)到集合V?S上所有頂點(diǎn)的最短路徑長(zhǎng)度if(!S[w] && (D[v] + G.arcs[v][w] < D[w])){D[w] = D[v] + G.arcs[v][w]; //更新D[w]Path [w] = v; //更改w的前驅(qū)為v}//if}//for }//ShortestPath_DIJvoid DisplayPath(AMGraph G , int begin ,int temp ){//顯示最短路if(Path[temp] != -1){DisplayPath(G , begin ,Path[temp]);cout << G.vexs[Path[temp]] << "-->";} }//DisplayPathint main() {cout << "************迪杰斯特拉算法**************" << endl << endl;AMGraph G;int i , j ,num_start , num_destination;VerTexType start , destination;CreateUDN(G);cout <<endl;cout << "*****無向網(wǎng)G創(chuàng)建完成！*****" << endl;for(i = 0 ; i < G.vexnum ; ++i){for(j = 0; j < G.vexnum; ++j){if(j != G.vexnum - 1){if(G.arcs[i][j] != MaxInt)cout << G.arcs[i][j] << "\t";elsecout << "∞" << "\t";}else{if(G.arcs[i][j] != MaxInt)cout << G.arcs[i][j] <<endl;elsecout << "∞" <<endl;}}}//forcout << endl;cout << "請(qǐng)依次輸入起始點(diǎn)、終點(diǎn)名稱：";cin >> start >> destination;num_start = LocateVex(G , start);num_destination = LocateVex(G , destination);ShortestPath_DIJ(G , num_start);cout << endl <<"最短路徑為：";DisplayPath(G , num_start , num_destination);cout << G.vexs[num_destination]<<endl;return 0; }//main

演示例子的話可以用上圖哦。

弗洛伊德算法：

//算法 弗洛伊德算法#include <iostream> using namespace std;#define MaxInt 32767 //表示極大值，即∞ #define MVNum 100 //最大頂點(diǎn)數(shù)typedef char VerTexType; //假設(shè)頂點(diǎn)的數(shù)據(jù)類型為字符型 typedef int ArcType; //假設(shè)邊的權(quán)值類型為整型int Path[MVNum][MVNum]; //最短路徑上頂點(diǎn)vj的前一頂點(diǎn)的序號(hào) int D[MVNum][MVNum]; //記錄頂點(diǎn)vi和vj之間的最短路徑長(zhǎng)度//------------圖的鄰接矩陣--------------- typedef struct{VerTexType vexs[MVNum]; //頂點(diǎn)表ArcType arcs[MVNum][MVNum]; //鄰接矩陣int vexnum,arcnum; //圖的當(dāng)前點(diǎn)數(shù)和邊數(shù) }AMGraph;int LocateVex(AMGraph G , VerTexType v){//確定點(diǎn)v在G中的位置for(int i = 0; i < G.vexnum; ++i)if(G.vexs[i] == v)return i;return -1; }//LocateVexvoid CreateUDN(AMGraph &G){//采用鄰接矩陣表示法，創(chuàng)建有向網(wǎng)Gint i , j , k;cout <<"請(qǐng)輸入總頂點(diǎn)數(shù)，總邊數(shù)，以空格隔開:";cin >> G.vexnum >> G.arcnum; //輸入總頂點(diǎn)數(shù)，總邊數(shù)cout << endl;cout << "輸入點(diǎn)的名稱，如a" << endl;for(i = 0; i < G.vexnum; ++i){cout << "請(qǐng)輸入第" << (i+1) << "個(gè)點(diǎn)的名稱:";cin >> G.vexs[i]; //依次輸入點(diǎn)的信息}cout << endl;for(i = 0; i < G.vexnum; ++i){ //初始化鄰接矩陣，邊的權(quán)值均置為極大值MaxIntfor(j = 0; j < G.vexnum; ++j){if(j != i)G.arcs[i][j] = MaxInt;elseG.arcs[i][j] = 0;}//for}//forcout << "輸入邊依附的頂點(diǎn)及權(quán)值，如a b 3" << endl;for(k = 0; k < G.arcnum;++k){ //構(gòu)造鄰接矩陣VerTexType v1 , v2;ArcType w;cout << "請(qǐng)輸入第" << (k + 1) << "條邊依附的頂點(diǎn)及權(quán)值:";cin >> v1 >> v2 >> w; //輸入一條邊依附的頂點(diǎn)及權(quán)值i = LocateVex(G, v1); j = LocateVex(G, v2); //確定v1和v2在G中的位置，即頂點(diǎn)數(shù)組的下標(biāo)G.arcs[i][j] = w; //邊<v1, v2>的權(quán)值置為w}//for }//CreateUDNvoid ShortestPath_Floyed(AMGraph G){//用Floyd算法求有向網(wǎng)G中各對(duì)頂點(diǎn)i和j之間的最短路徑int i , j , k ;for (i = 0; i < G.vexnum; ++i) //各對(duì)結(jié)點(diǎn)之間初始已知路徑及距離for(j = 0; j < G.vexnum; ++j){D[i][j] = G.arcs[i][j];if(D[i][j] < MaxInt && i != j) Path[i][j]=i; //如果i和j之間有弧，則將j的前驅(qū)置為ielse Path [i][j] = -1; //如果i和j之間無弧，則將j的前驅(qū)置為-1}//forfor(k = 0; k < G.vexnum; ++k)for(i = 0; i < G.vexnum; ++i)for(j = 0; j < G.vexnum; ++j)if(D[i][k] + D[k][j] < D[i][j]){ //從i經(jīng)k到j(luò)的一條路徑更短D[i][j] = D[i][k]+D[k][j]; //更新D[i][j]Path[i][j] = Path[k][j]; //更改j的前驅(qū)為k}//if }//ShortestPath_Floyedvoid DisplayPath(AMGraph G , int begin ,int temp ){//顯示最短路徑if(Path[begin][temp] != -1){DisplayPath(G , begin ,Path[begin][temp]);cout << G.vexs[Path[begin][temp]] << "-->";} }//DisplayPathint main(){cout << "************弗洛伊德算法**************" << endl << endl;AMGraph G;char start , destination;int num_start , num_destination;CreateUDN(G);cout <<endl;cout << "有向網(wǎng)G創(chuàng)建完成！" << endl;ShortestPath_Floyed(G);cout << "請(qǐng)依次輸入路徑的起點(diǎn)與終點(diǎn)的名稱：";cin >> start >> destination;num_start = LocateVex(G , start);num_destination = LocateVex(G , destination);DisplayPath(G , num_start , num_destination);cout << G.vexs[num_destination] << endl;cout << "最短路徑的長(zhǎng)度為：" << D[num_start][num_destination] << endl;cout <<endl;return 0; }//main

后記：

?????這里我著重迪杰斯特拉算法，因?yàn)楦ヂ逡恋缕鋵?shí)本質(zhì)也是一樣的，如果需要了解更多可以去查閱其它資料哦。
????ps別攔著我，我要去看世界了…竟然沒錢！！哭了，看來巧婦難為無米之炊啊。那么我要去搬磚賺錢啦，期待下一篇博客，沖鴨，搬磚去啦！

總結(jié)

以上是生活随笔為你收集整理的别说了，世界那么大我想去看看！（最短路径-迪杰斯特拉算法弗洛伊德算法）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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