数据结构：点对之间最短距离--Floyd算法

骑猪看日落 2022-06-12 04:24 231阅读 0赞

Floyd算法

### Floyd算法 ###

Dijkstra算法是用于解决单源最短路径问题的，Floyd算法则是解决点对之间最短路径问题的。Floyd算法的设计策略是动态规划，而Dijkstra采取的是贪心策略。当然，贪心算法就是动态规划的特例。

### 算法思想 ###

点对之间的最短路径只会有两种情况：

1.  两点之间有边相连，weight(Vi,Vj)即是最小的。
2.  通过另一点：中介点，两点相连，使weight(Vi,Vv)+weight(Vv,Vj)最小。

Min\_Distance(Vi,Vj)=min\{ weight(Vi,Vj),weight(Vi,Vv)+weight(Vv,Vj)\}。正是基于这种背后的逻辑，再加上动态规划的思想，构成了Floyd算法。故当Vv取完所有顶点后，Distance(Vi,Vj)即可达到最小。Floyd算法的起点就是图的[邻接矩阵][Link 1]。

题外话：代码本身不重要，算法思想才是精髓。思想极难得到，而有了思想，稍加经验即可写出代码。向思想的开创者致敬！

思想很难，代码却比较简单，直接上代码

### 代码 ###

类定义

**\[cpp\]**  view plain  copy

print ?

1.  \#include<iostream> 
2.  \#include<iomanip>
3.  \#include<stack>
4.  using namespace std;
5.  \#define MAXWEIGHT 100
6.  \#undef INFINITY
7.  \#define INFINITY 1000
8.  class Graph
9.  \{
10. private:
11. //顶点数 
12. int numV;
13. //边数 
14. int numE;
15. //邻接矩阵 
16. int \*\*matrix;
17. public:
18. Graph(int numV);
19. //建图 
20. void createGraph(int numE);
21. //析构方法 
22. ~Graph();
23. //Floyd算法
24. void Floyd();
25. //打印邻接矩阵 
26. void printAdjacentMatrix();
27. //检查输入 
28. bool check(int, int, int);
29. \};

#include<iostream>  
    #include<iomanip>
    #include<stack>
    using namespace std;
    #define MAXWEIGHT 100
    #undef INFINITY
    #define INFINITY 1000
    class Graph
    {
    private:
    	//顶点数  
    	int numV;
    	//边数  
    	int numE;
    	//邻接矩阵  
    	int **matrix;
    public:
    	Graph(int numV);
    	//建图  
    	void createGraph(int numE);
    	//析构方法  
    	~Graph();
    	//Floyd算法
    	void Floyd();
    	//打印邻接矩阵  
    	void printAdjacentMatrix();
    	//检查输入  
    	bool check(int, int, int);
    };

类实现

**\[cpp\]**  view plain  copy

print ?

1.  //构造函数，指定顶点数目
2.  Graph::Graph(int numV)
3.  \{
4.  //对输入的顶点数进行检测
5.  while (numV <= 0)
6.  \{
7.  cout << "顶点数有误！重新输入 ";
8.  cin >> numV;
9.  \}
10. this\->numV = numV;
11. //构建邻接矩阵，并初始化
12. matrix = new int\*\[numV\];
13. int i, j;
14. for (i = 0; i < numV; i++)
15. matrix\[i\] = new int\[numV\];
16. for (i = 0; i < numV; i++)
17. for (j = 0; j < numV; j++)
18. \{
19. if (i == j)
20. matrix\[i\]\[i\] = 0;
21. else
22. matrix\[i\]\[j\] = INFINITY;
23. \}
24. \}
25. void Graph::createGraph(int numE)
26. \{
27. /\*
28.  对输入的边数做检测
29.  一个numV个顶点的有向图，最多有numV\*(numV - 1)条边
30.  \*/
31. while (numE < 0 || numE > numV\*(numV - 1))
32. \{
33. cout << "边数有问题！重新输入 ";
34. cin >> numE;
35. \}
36. this\->numE = numE;
37. int tail, head, weight, i;
38. i = 0;
39. cout << "输入每条边的起点(弧尾)、终点(弧头)和权值" << endl;
40. while (i < numE)
41. \{
42. cin >> tail >> head >> weight;
43. while (!check(tail, head, weight))
44. \{
45. cout << "输入的边不正确！请重新输入 " << endl;
46. cin >> tail >> head >> weight;
47. \}
48. matrix\[tail\]\[head\] = weight;
49. i++;
50. \}
51. \}
52. Graph::~Graph()
53. \{
54. int i;
55. for (i = 0; i < numV; i++)
56. delete\[\] matrix\[i\];
57. delete\[\]matrix;
58. \}
59. /\*
60. 弗洛伊德算法
61. 求各顶点对之间的最短距离
62. 及其路径
63. \*/
64. void Graph::Floyd()
65. \{
66. //为了不修改邻接矩阵，多用一个二维数组
67. int \*\*Distance = new int\*\[numV\];
68. int i, j;
69. for (i = 0; i < numV; i++)
70. Distance\[i\] = new int\[numV\];
71. //初始化
72. for (i = 0; i < numV; i++)
73. for (j = 0; j < numV; j++)
74. Distance\[i\]\[j\] = matrix\[i\]\[j\];
75. 
76. //prev数组
77. int \*\*prev = new int\*\[numV\];
78. for (i = 0; i < numV; i++)
79. prev\[i\] = new int\[numV\];
80. //初始化prev
81. for (i = 0; i < numV; i++)
82. for (j = 0; j < numV; j++)
83. \{
84. if (matrix\[i\]\[j\] == INFINITY)
85. prev\[i\]\[j\] = -1;
86. else
87. prev\[i\]\[j\] = i;
88. \}
89. 
90. int d, v;
91. for (v = 0; v < numV; v++)
92. for (i = 0; i < numV; i++)
93. for (j = 0; j < numV; j++)
94. \{
95. d = Distance\[i\]\[v\] + Distance\[v\]\[j\];
96. if (d < Distance\[i\]\[j\])
97. \{
98. Distance\[i\]\[j\] = d;
99. prev\[i\]\[j\] = v;
100. \}
101. \}
102. //打印Distance和prev数组
103. cout << "Distance..." << endl;
104. for (i = 0; i < numV; i++)
105. \{
106. for (j = 0; j < numV; j++)
107. cout << setw(3) << Distance\[i\]\[j\];
108. cout << endl;
109. \}
110. cout << endl << "prev..." << endl;
111. for (i = 0; i < numV; i++)
112. \{
113. for (j = 0; j < numV; j++)
114. cout << setw(3) << prev\[i\]\[j\];
115. cout << endl;
116. \}
117. cout << endl;
118. //打印顶点对最短路径
119. stack<int> s;
120. for (i = 0; i < numV; i++)
121. \{
122. for (j = 0; j < numV; j++)
123. \{
124. if (Distance\[i\]\[j\] == 0);
125. else if (Distance\[i\]\[j\] == INFINITY)
126. cout << "顶点 " << i << " 到顶点 " << j << " 无路径！" << endl;
127. else
128. \{
129. s.push(j);
130. v = j;
131. do\{
132. v = prev\[i\]\[v\];
133. s.push(v);
134. \} while (v != i);
135. //打印路径
136. cout << "顶点 " << i << " 到顶点 " << j << " 的最短路径长度是 "
137. << Distance\[i\]\[j\] << " ，其路径序列是...";
138. while (!s.empty())
139. \{
140. cout << setw(3) << s.top();
141. s.pop();
142. \}
143. cout << endl;
144. \}
145. \}
146. cout << endl;
147. \}
148. //释放空间
149. for (i = 0; i < numV; i++)
150. \{
151. delete\[\] Distance\[i\];
152. delete\[\] prev\[i\];
153. \}
154. delete\[\]Distance;
155. delete\[\]prev;
156. \}
157. //打印邻接矩阵 
158. void Graph::printAdjacentMatrix()
159. \{
160. int i, j;
161. cout.setf(ios::left);
162. cout << setw(7) << " ";
163. for (i = 0; i < numV; i++)
164. cout << setw(7) << i;
165. cout << endl;
166. for (i = 0; i < numV; i++)
167. \{
168. cout << setw(7) << i;
169. for (j = 0; j < numV; j++)
170. cout << setw(7) << matrix\[i\]\[j\];
171. cout << endl;
172. \}
173. \}
174. bool Graph::check(int tail, int head, int weight)
175. \{
176. if (tail < 0 || tail >= numV || head < 0 || head >= numV
177. || weight <= 0 || weight >= MAXWEIGHT)
178. return false;
179. return true;
180. \}

//构造函数，指定顶点数目
    Graph::Graph(int numV)
    {
    	//对输入的顶点数进行检测
    	while (numV <= 0)
    	{
    		cout << "顶点数有误！重新输入 ";
    		cin >> numV;
    	}
    	this->numV = numV;
    	//构建邻接矩阵，并初始化
    	matrix = new int*[numV];
    	int i, j;
    	for (i = 0; i < numV; i++)
    		matrix[i] = new int[numV];
    	for (i = 0; i < numV; i++)
    	for (j = 0; j < numV; j++)
    	{
    		if (i == j)
    			matrix[i][i] = 0;
    		else
    			matrix[i][j] = INFINITY;
    	}
    }
    void Graph::createGraph(int numE)
    {
    	/*
    	对输入的边数做检测
    	一个numV个顶点的有向图，最多有numV*(numV - 1)条边
    	*/
    	while (numE < 0 || numE > numV*(numV - 1))
    	{
    		cout << "边数有问题！重新输入 ";
    		cin >> numE;
    	}
    	this->numE = numE;
    	int tail, head, weight, i;
    	i = 0;
    	cout << "输入每条边的起点(弧尾)、终点(弧头)和权值" << endl;
    	while (i < numE)
    	{
    		cin >> tail >> head >> weight;
    		while (!check(tail, head, weight))
    		{
    			cout << "输入的边不正确！请重新输入 " << endl;
    			cin >> tail >> head >> weight;
    		}
    		matrix[tail][head] = weight;
    		i++;
    	}
    }
    Graph::~Graph()
    {
    	int i;
    	for (i = 0; i < numV; i++)
    		delete[] matrix[i];
    	delete[]matrix;
    }
    /*
    弗洛伊德算法
    求各顶点对之间的最短距离
    及其路径
    */
    void Graph::Floyd()
    {
    	//为了不修改邻接矩阵，多用一个二维数组
    	int **Distance = new int*[numV];
    	int i, j;
    	for (i = 0; i < numV; i++)
    		Distance[i] = new int[numV];
    	//初始化
    	for (i = 0; i < numV; i++)
    	for (j = 0; j < numV; j++)
    		Distance[i][j] = matrix[i][j];
    
    	//prev数组
    	int **prev = new int*[numV];
    	for (i = 0; i < numV; i++)
    		prev[i] = new int[numV];
    	//初始化prev
    	for (i = 0; i < numV; i++)
    	for (j = 0; j < numV; j++)
    	{
    		if (matrix[i][j] == INFINITY)
    			prev[i][j] = -1;
    		else
    			prev[i][j] = i;
    	}
    	
    	int d, v;
    	for (v = 0; v < numV; v++)
    	for (i = 0; i < numV; i++)
    	for (j = 0; j < numV; j++)
    	{
    		d = Distance[i][v] + Distance[v][j];
    		if (d < Distance[i][j])
    		{
    			Distance[i][j] = d;
    			prev[i][j] = v;
    		}
    	}
    	//打印Distance和prev数组
    	cout << "Distance..." << endl;
    	for (i = 0; i < numV; i++)
    	{
    		for (j = 0; j < numV; j++)
    			cout << setw(3) << Distance[i][j];
    		cout << endl;
    	}
    	cout << endl << "prev..." << endl;
    	for (i = 0; i < numV; i++)
    	{
    		for (j = 0; j < numV; j++)
    			cout << setw(3) << prev[i][j];
    		cout << endl;
    	}
    	cout << endl;
    	//打印顶点对最短路径
    	stack<int> s;
    	for (i = 0; i < numV; i++)
    	{
    		for (j = 0; j < numV; j++)
    		{
    			if (Distance[i][j] == 0);
    			else if (Distance[i][j] == INFINITY)
    				cout << "顶点 " << i << " 到顶点 " << j << " 无路径！" << endl;
    			else
    			{
    				s.push(j);
    				v = j;
    				do{
    					v = prev[i][v];
    					s.push(v);
    				} while (v != i);
    				//打印路径
    				cout << "顶点 " << i << " 到顶点 " << j << " 的最短路径长度是 "
    					<< Distance[i][j] << " ，其路径序列是...";
    				while (!s.empty())
    				{
    					cout << setw(3) << s.top();
    					s.pop();
    				}
    				cout << endl;
    			}
    		}
    		cout << endl;
    	}
    	//释放空间
    	for (i = 0; i < numV; i++)
    	{
    		delete[] Distance[i];
    		delete[] prev[i];
    	}
    	delete[]Distance;
    	delete[]prev;
    }
    //打印邻接矩阵  
    void Graph::printAdjacentMatrix()
    {
    	int i, j;
    	cout.setf(ios::left);
    	cout << setw(7) << " ";
    	for (i = 0; i < numV; i++)
    		cout << setw(7) << i;
    	cout << endl;
    	for (i = 0; i < numV; i++)
    	{
    		cout << setw(7) << i;
    		for (j = 0; j < numV; j++)
    			cout << setw(7) << matrix[i][j];
    		cout << endl;
    	}
    }
    bool Graph::check(int tail, int head, int weight)
    {
    	if (tail < 0 || tail >= numV || head < 0 || head >= numV
    		|| weight <= 0 || weight >= MAXWEIGHT)
    		return false;
    	return true;
    }

主函数

**\[cpp\]**  view plain  copy

print ?

1.  int main()
2.  \{
3.  cout << "\*\*\*\*\*\*Floyd\*\*\*by David\*\*\*" << endl;
4.  int numV, numE;
5.  cout << "建图..." << endl;
6.  cout << "输入顶点数 ";
7.  cin >> numV;
8.  Graph graph(numV);
9.  cout << "输入边数 ";
10. cin >> numE;
11. graph.createGraph(numE);
12. cout << endl << "Floyd..." << endl;
13. graph.Floyd();
14. system("pause");
15. return 0;
16. \}

int main()
    {
    	cout << "******Floyd***by David***" << endl;
    	int numV, numE;
    	cout << "建图..." << endl;
    	cout << "输入顶点数 ";
    	cin >> numV;
    	Graph graph(numV);
    	cout << "输入边数 ";
    	cin >> numE;
    	graph.createGraph(numE);
    	cout << endl << "Floyd..." << endl;
    	graph.Floyd();
    	system("pause");
    	return 0;
    }

运行

![20140804130040671][]![20140804130050156][]

### 小结 ###

Floyd算法代码看似很长，其实并不难。代码中很多都是用于准备工作和输出，关键代码就是三层for循环。

完整代码下载：[Floyd算法][Floyd]

转载请注明出处，本文地址：[http://blog.csdn.net/zhangxiangdavaid/article/details/38366923][http_blog.csdn.net_zhangxiangdavaid_article_details_38366923]

若有所帮助，顶一个哦！

专栏目录：

*  [数据结构与算法目录][Link 2]
 *  [c指针][c]

[Link 1]: http://blog.csdn.net/zhangxiangdavaid/article/details/38321327
[20140804130040671]: https://img-blog.csdn.net/20140804130040671
[20140804130050156]: /images/20220612/a7a1b51b777b42489223869f1031b174.png
[Floyd]: http://download.csdn.net/detail/zhangxiangdavaid/7712387
[http_blog.csdn.net_zhangxiangdavaid_article_details_38366923]: http://blog.csdn.net/zhangxiangdavaid/article/details/38366923
[Link 2]: http://blog.csdn.net/zhangxiangdavaid/article/details/25082013
[c]: http://blog.csdn.net/zhangxiangdavaid/article/details/37885275#t1