一、最短路徑
①在非網圖中,最短路徑是指兩頂點之間經曆的邊數最少的路徑。
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsISM9AnYldnJwAzN9c3Pn5Gcu4WNHNWdBpXTykkaNBzZ610MwkXTxUFRNFTSU1kMFpnT4VERNRTRE1UewkWT00kaONTRU1kdFRUT0UERNlHOp1ENNpmTzUEVNZ3YyI2cKJDT0ljMZVXTzold41WW15UbMNTRE1UeNhlWuZ0ViBXO5xkNNh0YwIFSh9CXt92YuM3YltWas5iclN3Ztl2Lc9CX6MHc0RHaiojIsJye.png)
AE:1 ADE:2 ADCE:3 ABCE:3
②在網圖中,最短路徑是指兩頂點之間經曆的邊上權值之和最短的路徑。
AE:100 ADE:90 ADCE:60 ABCE:70
③單源點最短路徑問題
問題描述:給定帶權有向圖G=(V, E)和源點v∈V,求從v到G中其餘各頂點的最短路徑。
應用執行個體——計算機網絡傳輸的問題:怎樣找到一種最經濟的方式,從一台計算機向網上所有其它計算機發送一條消息。
④每一對頂點之間的最短路徑
問題描述:給定帶權有向圖G=(V, E),對任意頂點vi,vj∈V(i≠j),求頂點vi到頂點vj的最短路徑。
解決辦法1:每次以一個頂點為源點,調用Dijkstra算法n次。顯然,時間複雜度為O(n3)。 解決辦法2:弗洛伊德提出的求每一對頂點之間的最短路徑算法——Floyd算法,其時間複雜度也是O(n3),但形式上要簡單些。
二、Dijkstra算法
①基本思想:設定一個集合S存放已經找到最短路徑的頂點,S的初始狀态隻包含源點v,對vi∈V-S,假設從源點v到vi的有向邊為最短路徑。以後每求得一條最短路徑v, …, vk,就将vk加入集合S中,并将路徑v, …, vk , vi與原來的假設相比較,取路徑長度較小者為最短路徑。重複上述過程,直到集合V中全部頂點加入到集合S中。
②設計資料結構 :
1、圖的存儲結構:帶權的鄰接矩陣存儲結構 。
2、數組dist[n]:每個分量dist[i]表示目前所找到的從始點v到終點vi的最短路徑的長度。初态為:若從v到vi有弧,則dist[i]為弧上權值;否則置dist[i]為∞。
3、數組path[n]:path[i]是一個字元串,表示目前所找到的從始點v到終點vi的最短路徑。初态為:若從v到vi有弧,則path[i]為vvi;否則置path[i]空串。
4、數組s[n]:存放源點和已經生成的終點,其初态為隻有一個源點v。
③Dijkstra算法——僞代碼
1 1. 初始化數組dist、path和s;
2 2. while (s中的元素個數<n)
3 2.1 在dist[n]中求最小值,其下标為k;
4 2.2 輸出dist[j]和path[j];
5 2.3 修改數組dist和path;
6 2.4 将頂點vk添加到數組s中;
④C++代碼實作
1 #include<iostream>
2 #include<fstream>
3 #include<string>
4 using namespace std;
5 #define MaxSize 10
6 #define MAXCOST 10000
7 // 圖的結構
8 template<class T>
9 struct Graph
10 {
11 T vertex[MaxSize];// 存放圖中頂點的數組
12 int arc[MaxSize][MaxSize];// 存放圖中邊的數組
13 int vertexNum, arcNum;// 圖中頂點數和邊數
14 };
15 // 最短路徑Dijkstra算法
16 void Dijkstra(Graph<string> G,int v)
17 {
18 int dist[MaxSize];// i到j的路徑長度
19 string path[MaxSize];// 路徑的串
20 int s[MaxSize];// 已找到最短路徑的點的集合
21 bool Final[MaxSize];//Final[w]=1表示求得頂點V0至Vw的最短路徑
22 // 初始化dist\path
23 for (int i = 0; i < G.vertexNum; i++)
24 {
25 Final[i] = false;
26 dist[i] = G.arc[v][i];
27 if (dist[i] != MAXCOST)
28 path[i] = G.vertex[v] + G.vertex[i];
29 else
30 path[i] = " ";
31 }
32 s[0] = v; // 初始化s
33 Final[v] = true;
34 int num = 1;
35 while (num < G.vertexNum)
36 {
37 // 在dist中查找最小值元素
38 int k = 0,min= MAXCOST;
39 for (int i = 0; i < G.vertexNum; i++)
40 {
41 if (i == v)continue;
42 if (!Final[i] && dist[i] < min)
43 {
44 k = i;
45 min = dist[i];
46 }
47 }
48 cout << dist[k]<<path[k]<<endl;
49 s[num++] = k;// 将新生成的結點加入集合s
50 Final[k] = true;
51 // 修改dist和path數組
52 for (int i = 0; i < G.vertexNum; i++)
53 {
54 if (!Final[i]&&dist[i] > dist[k] + G.arc[k][i])
55 {
56 dist[i] = dist[k] + G.arc[k][i];
57 path[i] = path[k] + G.vertex[i];
58 }
59 }
60 }
61 }
62 int main()
63 {
64 // 建立圖
65 Graph<string> G;
66 string temp[]= { "v0","v1","v2","v3","v4" };
67 /*int length = sizeof(temp) / sizeof(temp[0]);
68 G.vertexNum = length;
69 G.arcNum = 7;*/
70 ifstream in("input.txt");
71 in >> G.vertexNum >> G.arcNum;
72 // 初始化圖的頂點資訊
73 for (int i = 0; i < G.vertexNum; i++)
74 {
75 G.vertex[i] = temp[i];
76 }
77 //初始化圖G的邊權值
78 for (int i =0; i <G.vertexNum; i++)
79 {
80 for (int j = 0; j <G.vertexNum; j++)
81 {
82 G.arc[i][j] = MAXCOST;
83 }
84 }
85 for (int i = 0; i < G.arcNum; i++)
86 {
87 int m, n,cost;
88 in >> m >> n >> cost;
89 G.arc[m][n] = cost;
90 }
91 Dijkstra(G, 0);
92 system("pause");
93 return 0;
94 }
// input.txt
1 5 7
2 0 1 10
3 0 3 30
4 0 4 100
5 1 2 50
6 2 4 10
7 3 2 20
8 3 4 60
三、Floyd算法
①基本思想:對于從vi到vj的弧,進行n次試探:首先考慮路徑vi,v0,vj是否存在,如果存在,則比較vi,vj和vi,v0,vj的路徑長度,取較短者為從vi到vj的中間頂點的序号不大于0的最短路徑。在路徑上再增加一個頂點v1,依此類推,在經過n次比較後,最後求得的必是從頂點vi到頂點vj的最短路徑。
②設計資料結構
1、圖的存儲結構:帶權的鄰接矩陣存儲結構 。
2、數組dist[n][n]:存放在疊代過程中求得的最短路徑長度。疊代公式:
3、數組path[n][n]:存放從vi到vj的最短路徑,初始為path[i][j]="vivj"。
③C++代碼實作
1 #include<iostream>
2 #include<fstream>
3 #include<string>
4 using namespace std;
5 #define MaxSize 10
6 #define MAXCOST 10000
7 int dist[MaxSize][MaxSize];// 存放在疊代過程中求得的最短路徑
8 string path[MaxSize][MaxSize];// vi到vj的最短路徑
9 // 圖的結構
10 template<class T>
11 struct Graph
12 {
13 T vertex[MaxSize];// 存放圖中頂點的數組
14 int arc[MaxSize][MaxSize];// 存放圖中邊的數組
15 int vertexNum, arcNum;// 圖中頂點數和邊數
16 };
17 void Floyd(Graph<string> G)
18 {
19 // 初始化
20 for(int i=0;i<G.vertexNum;i++)
21 for (int j = 0; j < G.vertexNum; j++)
22 {
23 if (i == j) { dist[i][j] = 0; path[i][j] = ""; }
24 dist[i][j] = G.arc[i][j];
25 if (dist[i][j] != MAXCOST)
26 path[i][j] = G.vertex[i] + G.vertex[j];
27 else
28 path[i][j] = " ";
29 }
30 // 進行n次疊代
31 for(int k=0;k<G.vertexNum;k++)
32 for(int i=0;i<G.vertexNum;i++)
33 for (int j = 0; j < G.vertexNum; j++)
34 if (dist[i][k] + dist[k][j] < dist[i][j])
35 {
36 dist[i][j] = dist[i][k] + dist[k][j];
37 path[i][j] = path[i][k] + path[k][j];
38 }
39 }
40 int main()
41 {
42 int i, j, cost;
43 Graph<string> G;// 存放圖的資訊
44 ifstream in("input.txt");
45 in >> G.vertexNum >> G.arcNum;
46 string temp[] = { "a","b","c" };
47 // 初始化圖的頂點資訊
48 for (int i = 0; i < G.vertexNum; i++)
49 {
50 G.vertex[i] = temp[i];
51 }
52 //初始化圖G
53 for (i = 0; i < G.vertexNum; i++)
54 {
55 for (j = 0; j < G.vertexNum; j++)
56 {
57 G.arc[i][j] = MAXCOST;
58 }
59 }
60 //建構圖G
61 for (int k = 0; k <G.arcNum; k++)
62 {
63 in >> i >> j >> cost;
64 G.arc[i][j] = cost;
65 }
66 Floyd(G);
67 for (i = 0; i < G.vertexNum; i++)
68 {
69 for (j = 0; j < G.vertexNum; j++)
70 {
71 if (i != j)
72 {
73 cout << "頂點" << i << "到頂點" << j << "的最短路徑長度為" << dist[i][j] << endl;
74 cout << "具體路徑為:" << path[i][j] << endl;
75 }
76 }
77 }
78 system("pause");
79 return 0;
80 }
// input.txt
3 5
0 1 4
1 0 6
0 2 11
2 0 3
1 2 2
參考文獻:
[1]王紅梅, 胡明, 王濤. 資料結構(C++版)[M]. 北京:清華大學出版社。