當前位置：首頁 > 人文社科 > 生活经验 >内容正文

生活经验

数据结构与算法（7-4）最短路径（迪杰斯特拉(Dijkstra)算法、弗洛伊德(Floyd)算法）

發布時間：2023/11/27 生活经验 32 豆豆

生活随笔收集整理的這篇文章主要介紹了数据结构与算法（7-4）最短路径（迪杰斯特拉(Dijkstra)算法、弗洛伊德(Floyd)算法）小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

一、最短路徑概念

二、迪杰斯特拉(Dijkstra)算法（單源最短路徑）

1、原理

2、過程

?3、代碼

三、弗洛伊德(Floyd)算法（多源最短路徑）

1、原理

2、存儲

3、遍歷

4、代碼

參考資料

一、最短路徑概念

最短路徑，顧名思義，兩結點之間最短的路徑（可以是非鄰接結點）。

最小生成樹和最短路徑區別：

最小生成樹：連通圖的最短路徑。

最短路徑：兩任意結點之間（可以非鄰接）的最短路徑。

二、迪杰斯特拉(Dijkstra)算法（單源最短路徑）

優點：效率較高，時間復雜度為O(n^2)。

缺點：只能求一個頂點到所有頂點的最短路徑。（單源最短路）

1、原理

1、先選定一個根結點，并選定一個數組，先確定未遍歷前的初始距離，把距離最短的鄰接結點選定為中間結點，并標記訪問過，開始往下遍歷，挨個訪問那個中間結點的鄰接結點。計算出根結點到中間結點+中間結點到新鄰接結點的距離，作為新距離，對比新距離和舊距離，如果新距離大，則把新距離替換掉舊距離，否則不變。

2、一輪訪問結束后，從未標記的結點中選定距離最短的，把它作為中間結點，繼續往下訪問。若都標記過，則算法結束。

2、過程

?1、保存根結點及到其他結點的權（距離）

?2、?訪問最近結點作為中間結點

3、對比新距離（根結點到中間結點+中間結點到新結點）和舊距離（根結點直接到新結點）?

?4、若新距離短，修改保存到數組

?5、繼續訪問后面的，把未訪問的距離根最近結點作為中間結點，繼續訪問它的鄰接結點

?6、繼續對比新距離和舊距離

?7、若新距離短，則修改保存到數組

?8、?繼續以距離根結點最短的結點為對象，訪問它的鄰接結點

?9、全部訪問完畢，結束算法

欣賞一下自己的稿書：?

?3、代碼

//迪杰斯特拉(Dijkstra)算法
/*測試案例
ABCDEFGHI
B 1 C 5
A 1 C 3 D 7 E 5
A 5 B 3 E 1 F 7
B 7 E 2 G 3
B 5 C 1 F 3 H 9 G 6 D 2
C 7 E 3 H 5
D 3 E 6 H 2 I 7
F 5 E 9 G 2 I 4
G 7 H 4
*/
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>#define MAXSIZE 20
#define MAX 65535					//代表無窮大
int length = 0;							//頂點個數
int root = 0;								//根頂點
int rootDist[MAXSIZE];				//根頂點（記錄根到其他頂點的距離）
bool visit[MAXSIZE];				//記錄各結點是否訪問//圖（頂點和權）
typedef struct
{char vertex[MAXSIZE];int weight[MAXSIZE][MAXSIZE];			//權可以代替邊（自身為0，相連有值，不相連無窮大）
}Graph;
Graph G;//輸入頂點
void InputVertex()
{int i;char ch;printf("請輸入圖的頂點：\n");scanf("%c", &ch);for (i = 0; i < MAXSIZE && ch != '\n'; i++){G.vertex[i] = ch;scanf("%c", &ch);}length = i;
}//圖權重初始化
void GraphWeightInit()
{int i, j;for (i = 0; i < length; i++){for (j = 0; j < length; j++){if (i == j)							//指向自己G.weight[i][j] = 0;elseG.weight[i][j] = MAX;	//無窮大}}
}//根據數據查找圖頂點下標
int FindIndex(char ch)
{int i;for (i = 0; i < length; i++){if (G.vertex[i] == ch)return i;}return -1;
}//創建圖
void CreateGraph()
{int i, j, index, weight;char ch;for (i = 0; i < length; i++){printf("請輸入%c的鄰接頂點及權重（空格分隔，換行結束）：\n", G.vertex[i]);scanf("%c", &ch);while (ch != '\n'){while (ch == ' ')				//為空格{scanf("%c", &ch);			//輸入字符continue;}index = FindIndex(ch);scanf("%d", &weight);		//輸入權重while (weight == 32)		//32為空格的ASCII碼{scanf("%d", &weight);continue;}G.weight[i][index] = weight;	//存入權重scanf("%c", &ch);				//(下一輪)輸入字符}}
}//根結點初始化
void Init()
{int i;printf("請輸入根結點：\t");scanf("%d", &root);for (i = 0; i < length; i++){rootDist[i] = G.weight[root][i];		//把0作為根，初始化visit[i] = false;								//未訪問}
}//取最小（在未訪問的結點中）
int GetMinInVisit()
{int i, min = 0;for (i = 0; i < length; i++){//未訪問if (!visit[i]){//找到最小下標（不能是自身）if (rootDist[min] > rootDist[i] || rootDist[min] == 0){min = i;}}}return min;
}//檢查是否訪問完畢
bool IsNull()
{bool flag = true;for (int i = 0; i < length; i++){if (!visit[i])				//還有未訪問的flag = false;}return flag;
}//迪杰斯特拉(Dikstra)算法（生成根到其他頂點的最短路徑）
void Dijkstra(int index)
{int i;visit[index] = true;						//標記訪問printf("%c %d\t", G.vertex[index], rootDist[index]);//遍歷中間結點的鄰接結點，對比新舊距離for (i = 0; i < length; i++){//若 舊距離 > 新距離（改變新距離覆蓋舊距離）if (rootDist[i] > (rootDist[index] + G.weight[index][i])){rootDist[i] = rootDist[index] + G.weight[index][i];}}//退出判斷if (IsNull())return;index = GetMinInVisit();				//取出最小鄰接結點，作為中間結點Dijkstra(index);								//遞歸調用Dijkstra()
}//輸出測試
void Print()
{for (int i = 0; i < length; i++){printf("\n%c結點鄰接結點：\t", G.vertex[i]);for (int j = 0; j < length; j++){if (G.weight[i][j] != 0 && G.weight[i][j] != MAX)		//有鄰接結點{printf("%c %d\t", G.vertex[j], G.weight[i][j]);}}}
}int main()
{InputVertex();				//輸入頂點GraphWeightInit();		    //圖權重初始化CreateGraph();				//創建圖Init();						//初始化Dijkstra(root);				//迪杰斯特拉算法（先以根結點為中間結點遍歷）（生成根到其他頂點的最短路徑）//Print();					//測試輸出return 0;
}

三、弗洛伊德(Floyd)算法（多源最短路徑）

優點：求所有頂點到所有頂點的最短路徑。（多源最短路）

缺點：效率較低，時間復雜度為O(n^3)。??

1、原理

基本思想：

不斷找點進行中轉，比較中轉前后的最小距離。

原理：

最優子結構：圖結構中一個顯而易見的定理：最短路徑的子路徑仍然是最短路徑?,這個定理顯而易見，比如一條從a到e的最短路徑a->b->c->d->e 那么 a->b->c 一定是a到c的最短路徑，c->d->e一定是c到e的最短路徑，反過來，（原理）如果一條最短路必須要經過點k，那么i->k的最短路徑+k->j的最短路徑一定是i->j 經過k的最短路徑，因此，最優子結構可以保證。

（左邊矩陣是改進前的，右邊矩陣是改進后的。）

弗洛伊德算法定義了兩個二維矩陣：

D矩陣存放最小權(最短路徑)，P矩陣存放最短前驅(中轉點)

1、矩陣D記錄頂點間的最小路徑
例如D[1][2]= 3，說明頂點1?到 2?的最短路徑為3；
2、矩陣P記錄頂點間最小路徑中的中轉點
例如P[1][2]= 0?說明，1?到 2的最短路徑軌跡為：1?-> 0?-> 2。
它通過3重循環，medium為中轉點，begin為起點，end為終點，循環比較D[begin][end] 和 D[begin][medium] + D[medium][end] 之間的最小值，如果(D[begin][medium] + D[medium][end] )為更小值，則把(D[begin][medium] + D[medium][end] )覆蓋保存在(D[begin][end])中。

2、存儲

弗洛伊德算法定義了兩個二維矩陣：

D矩陣存放最小權(最短路徑)，P矩陣存放最短前驅(中轉點)

?思考：如果求任意兩點之間的最短路徑，兩點之間可以直接到達但卻不是最短的路徑，要讓任意兩點（例如從頂點a點到頂點b）之間的路程變短，只能引入第三個點（頂點medium），并通過這個頂點medium中轉即a->medium->b，才可能縮短原來從頂點a點到頂點b的路程。那么這個中轉頂點medium是1~n中的哪個點呢？甚至有時候不只通過一個點，而是經過兩個點或者更多中轉點會更短。

下面給出一些例子深入理解一下：

例：????????4 -> 3? ? ? ? ? 一、直接：D[4][3] = 12? ? ? ?二、過1：D[4][1]+D[1][3]=11? ?

過1更短，????????則D[4][3] = 11????????且P[4][3] = P[4][1] = 1

例：? ? ? ? 1?->3? ? ? ???一、直接：D[1][3] = 6????????二、過2：D[1][2]+D[2][3] = 5

過2更短，????????則D[1][3] = 6? ? ? ? ? 且P[1][3] = P[1][2] = 2

?1、假如現在只允許經過1號頂點，求任意兩點的最短路徑我們應該怎么求呢？？

?我們只需要判斷 (D[begin][end])?與 (D[begin][1] + D[1][end]) 的大小。（前者直接到達，后者經歷中轉）

//只經過1號中轉頂點
for (begin = 1; begin <= n; begin++)for (end = 1; end <= n; end++)if (D[begin][end] > D[begin][1] + D[1][end])D[begin][end] = D[begin][1] + D[1][end];

?在只允許經過1號中轉頂點的情況下，任意兩點之間的路程更新為：

2、繼續求在只允許經過1和2號兩個中轉頂點的情況下任意兩點之間的最短路程

//只經過1號中轉頂點
for (begin = 1; begin <= n; begin++)for (end = 1; end <= n; end++)if (D[begin][end] > D[begin][1] + D[1][end])D[begin][end] = D[begin][1] + D[1][end];//只經過2號中轉頂點
for (begin = 1; begin <= n; begin++)for (end = 1; end <= n; end++)if (D[begin][end] > D[begin][2] + D[2][end])D[begin][end] = D[begin][2] + D[2][end];

在只允許更新1號和2號頂點的情況下，任意兩點之間的路徑更新為：

?3、..........繼續往后，運行經過n個中轉頂點（即全部）

//運行經過所有中轉頂點
for(medium = 0; medium <= n; medium++)for (begin = 1; begin <= n; begin++)for (end = 1; end <= n; end++)if (D[begin][end] > D[begin][medium] + D[medium][end])D[begin][end] = D[begin][medium] + D[medium][end];

允許經過所有中轉頂點，最后的兩點路徑更新：?

3、遍歷

//遍歷弗洛伊德算法
//確定begin -> end：從最近的前驅開始，一點一點往后追溯
void Traverse_Floyd()
{int medium = 0;for (int begin = 0; begin < length; begin++){for (int end = 0; end < length; end++){printf("\n%c", G.vertex[begin]);medium = P[begin][end];                     //開始追溯（此為最近的前驅）while (medium != end)						//未追溯到尾{printf("->%c", G.vertex[medium]);		//打印中間結點medium = P[medium][end];				//向后追溯}}}
}

4、代碼

//弗洛伊德(Floyd)算法
/*測試案例
ABCDEFGHI
B 1 C 5
A 1 C 3 D 7 E 5
A 5 B 3 E 1 F 7
B 7 E 2 G 3
B 5 C 1 F 3 H 9 G 6 D 2
C 7 E 3 H 5
D 3 E 6 H 2 I 7
F 5 E 9 G 2 I 4
G 7 H 4
*/
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>#define MAXSIZE 20
#define MAX 65535							//代表無窮大
int length = 0;									//頂點個數
int D[MAXSIZE][MAXSIZE];		//存放頂點之間的權
int P[MAXSIZE][MAXSIZE];		//存放頂點之間的前驅（中間結點）//圖（頂點和權）
typedef struct
{char vertex[MAXSIZE];int weight[MAXSIZE][MAXSIZE];			//權可以代替邊（自身為0，相連有值，不相連無窮大）
}Graph;
Graph G;//輸入頂點
void InputVertex()
{int i;char ch;printf("請輸入圖的頂點：\n");scanf("%c", &ch);for (i = 0; i < MAXSIZE && ch != '\n'; i++){G.vertex[i] = ch;scanf("%c", &ch);}length = i;
}//圖權重初始化
void GraphWeightInit()
{int i, j;for (i = 0; i < length; i++){for (j = 0; j < length; j++){if (i == j)							//指向自己G.weight[i][j] = 0;elseG.weight[i][j] = MAX;	//無窮大}}
}//根據數據查找圖頂點下標
int FindIndex(char ch)
{int i;for (i = 0; i < length; i++){if (G.vertex[i] == ch)return i;}return -1;
}//創建圖
void CreateGraph()
{int i, j, index, weight;char ch;for (i = 0; i < length; i++){printf("請輸入%c的鄰接頂點及權重（空格分隔，換行結束）：\n", G.vertex[i]);scanf("%c", &ch);while (ch != '\n'){while (ch == ' ')				//為空格{scanf("%c", &ch);			//輸入字符continue;}index = FindIndex(ch);scanf("%d", &weight);		//輸入權重while (weight == 32)		//32為空格的ASCII碼{scanf("%d", &weight);continue;}G.weight[i][index] = weight;	//存入權重scanf("%c", &ch);				//(下一輪)輸入字符}}
}//弗洛伊德算法
void Floyd()
{int medium, begin, end;//初始化矩陣for (int i = 0; i < length; i++)for (int j = 0; j < length; j++){D[i][j] = G.weight[i][j];P[i][j] = j;}//開始正式修改（最短路徑及前驅）for (medium = 0; medium < length; medium++)	//中間結點for (begin = 0; begin < length; begin++)			//前驅結點for (end = 0; end < length; end++)				//后繼結點{//經過中間結點路徑更小，則1、需要覆蓋掉原來的路徑；2、替換掉前驅（中間結點）if (D[begin][end] > (D[begin][medium] + D[medium][end])){D[begin][end] = D[begin][medium] + D[medium][end];		//覆蓋路徑（只達標的話，只要這一句就夠了）P[begin][end] = P[begin][medium];										//更新前驅（中間結點）//不能直接賦值medium：跨越結點之間的追溯，存放的是最近前驅，需要一個一個往后追溯}}
}//測試矩陣輸出
void PrintArray()
{//遍歷輸出printf("遍歷輸出D矩陣（最短路徑）：\n");for (int i = 0; i < length; i++){printf("\n");for (int j = 0; j < length; j++){printf("%3d", D[i][j]);}}printf("\n遍歷輸出P矩陣（前驅）：\n");for (int i = 0; i < length; i++){printf("\n");for (int j = 0; j < length; j++){printf("%3d", P[i][j]);}}
}//遍歷弗洛伊德算法
//確定begin -> end：從最近的前驅開始，一點一點往后追溯
void Traverse_Floyd()
{int medium = 0;for (int begin = 0; begin < length; begin++){for (int end = 0; end < length; end++){printf("\n%c", G.vertex[begin]);medium = P[begin][end];						//開始追溯（此為最近的前驅）while (medium != end)							//未追溯到尾{printf("->%c", G.vertex[medium]);		//打印中間結點medium = P[medium][end];				//向后追溯}}}
}//輸出測試
void Print()
{for (int i = 0; i < length; i++){printf("\n%c結點鄰接結點：\t", G.vertex[i]);for (int j = 0; j < length; j++){if (G.weight[i][j] != 0 && G.weight[i][j] != MAX)		//有鄰接結點{printf("%c %d\t", G.vertex[j], G.weight[i][j]);}}}
}int main()
{InputVertex();			//輸入頂點GraphWeightInit();		//圖權重初始化CreateGraph();			//創建圖Floyd();				//弗洛伊德算法（生成最短路徑）Traverse_Floyd();		//遍歷弗洛伊德算法//PrintArray();			//測試弗洛伊德矩陣輸出//Print();				//測試輸出return 0;
}

參考資料

《大話數據結構》?

https://www.bilibili.com/video/BV1uX4y137Hf?from=search&seid=9442880507495572891

https://blog.csdn.net/jeffleo/article/details/53349825?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522162842804216780271587280%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=162842804216780271587280&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-53349825.pc_search_result_control_group&utm_term=%E5%BC%97%E6%B4%9B%E4%BC%8A%E5%BE%B7%E7%AE%97%E6%B3%95&spm=1018.2226.3001.4187

https://blog.csdn.net/yuewenyao/article/details/81021319?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522162842804216780271587280%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=162842804216780271587280&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-2-81021319.pc_search_result_control_group&utm_term=%E5%BC%97%E6%B4%9B%E4%BC%8A%E5%BE%B7%E7%AE%97%E6%B3%95&spm=1018.2226.3001.4187

https://zhuanlan.zhihu.com/p/33162490?

總結

以上是生活随笔為你收集整理的数据结构与算法（7-4）最短路径（迪杰斯特拉(Dijkstra)算法、弗洛伊德(Floyd)算法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇： OpenCV（六）形态学操作1--基础：
下一篇： OpenCV（基础补充）图像二值化

生活经验

数据结构与算法（7-4）最短路径（迪杰斯特拉(Dijkstra)算法、弗洛伊德(Floyd)算法）

一、最短路徑概念

二、迪杰斯特拉(Dijkstra)算法（單源最短路徑）

1、原理

2、過程

?3、代碼

三、弗洛伊德(Floyd)算法（多源最短路徑）

1、原理

2、存儲

3、遍歷

4、代碼

參考資料

總結

一、最短路徑概念

二、迪杰斯特拉(Dijkstra)算法（單源最短路徑）

1、原理

?3、代碼

1、原理

3、遍歷