数据结构：单源最短路径--Dijkstra算法

墨蓝 2022-06-12 04:24 257阅读 0赞

Dijkstra算法

### 单源最短路径 ###

给定一带权图，图中每条边的权值是非负的，代表着两顶点之间的距离。指定图中的一顶点为源点，找出源点到其它顶点的最短路径和其长度的问题，即是单源最短路径问题。

### Dijkstra算法 ###

求解单源最短路径问题的常用方法是Dijkstra(迪杰斯特拉)算法。该算法使用的是贪心策略：每次都找出剩余顶点中与源点距离最近的一个顶点。

### 算法思想 ###

带权图G=<V,E>，令S为已确定了最短路径顶点的集合，则可用V-S表示剩余未确定最短路径顶点的集合。假设V0是源点，则初始 S=\{ V0\}。用数组Distance表示源点V0到其余顶点的路径长度，用数组pre\[i\]表示最短路径序列上顶点i的前一个顶点。初始时，pre\[i\]都是源点的下标。接下来需重复两个步骤：

1.  从当前Distance\[i\]找出最小的一个，记录其下标v=i，源点V0到顶点Vv的最短路径即已确定，把Vv加入S。
2.  更新源点到剩余顶点的最短路径长度。更新方法是：以上一步的顶点Vv为中间点，若Distance\[v\]+weight(v,i)<Distance\[i\]，则修改值：pre\[i\]=v;Distance\[i\]=Distance\[v\]+weight(v,i);

重复以上两个步骤，直至所有顶点的最短路径都已找到。  
 需要指出，Dijkstra算法求解的不仅是有向图，无向图也是可以的。下面给出一个完整的有向带权图的实例：

### 实例 ###

有向带权图

![20140803195620968][]

Dijkstra算法的求解过程

![20140804183450419][]

其中，INF是infinity无穷大的意思。

### 代码 ###

类定义

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

print ?

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

#include<iostream>  
    #include<iomanip>
    #include<stack>
    using namespace std;
    #define MAXWEIGHT 100
    #ifdef INFINITY
    #undef INFINITY
    #endif
    #define INFINITY 1000
    class Graph
    {
    private:
    	//顶点数  
    	int numV;
    	//边数  
    	int numE;
    	//邻接矩阵  
    	int **matrix;
    public:
    	Graph(int numV);
    	//建图  
    	void createGraph(int numE);
    	//析构方法  
    	~Graph();
    	//迪杰斯特拉算法
    	void Dijkstra(int);
    	//打印邻接矩阵  
    	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. 求指定顶点vertex到其它顶点的最短路径
62. 不仅要得出最短路径长度，也要得到其序列
63. \*/
64. void Graph::Dijkstra(int vertex)
65. \{
66. int i;
67. //最短路径序列中每个顶点的直接前驱
68. int \*pre = new int\[numV\];
69. for (i = 0; i < numV; i++)
70. pre\[i\] = vertex;
71. //顶点vertex到各个顶点的路径长度
72. int \*Distance = new int\[numV\];
73. //初始化路径长度
74. for (i = 0; i < numV; i++)
75. Distance\[i\] = matrix\[vertex\]\[i\];
76. //标记各个顶点最短路径找到与否
77. bool \*find = new bool\[numV\];
78. memset(find, 0, numV);
79. find\[vertex\] = true;
80. int d, v, count;
81. count = 1, v = vertex;
82. while (count < numV)
83. \{
84. d = INFINITY;
85. //确定一个最短距离
86. for (i = 0; i < numV; i++)
87. \{
88. if (!find\[i\] && Distance\[i\] < d)
89. \{
90. d = Distance\[i\];
91. v = i;
92. \}
93. \}
94. find\[v\] = true;
95. //更新剩余顶点的前驱和最短距离
96. for (i = 0; i < numV; i++)
97. \{
98. if (!find\[i\])
99. \{
100. d = Distance\[v\] + matrix\[v\]\[i\];
101. if (d < Distance\[i\])
102. \{
103. pre\[i\] = v;
104. Distance\[i\] = d;
105. \}
106. \}
107. \}
108. count++;
109. \}
110. //打印最短路径序列和其长度
111. stack<int> s;
112. for (i = 0; i < numV; i++)
113. \{
114. if (Distance\[i\] == 0);
115. else if (Distance\[i\] == INFINITY)
116. cout << "顶点 " << vertex <<" 到顶点 " << i <<" 无路径！" << endl;
117. else
118. \{
119. cout << "顶点 " << vertex << " 到顶点 " << i
120. << " 最短路径长度是 " << Distance\[i\]
121. << " ，其序列是...";
122. v = i;
123. s.push(v);
124. do
125. \{
126. v = pre\[v\];
127. s.push(v);
128. \} while (v!=vertex);
129. //打印最短路径序列
130. while (!s.empty())
131. \{
132. cout << setw(3) << s.top();
133. s.pop();
134. \}
135. cout << endl;
136. \}
137. \}
138. cout << endl;
139. delete\[\]find;
140. delete\[\]pre;
141. delete\[\]Distance;
142. \}
143. //打印邻接矩阵 
144. void Graph::printAdjacentMatrix()
145. \{
146. int i, j;
147. cout.setf(ios::left);
148. cout << setw(7) << " ";
149. for (i = 0; i < numV; i++)
150. cout << setw(7) << i;
151. cout << endl;
152. for (i = 0; i < numV; i++)
153. \{
154. cout << setw(7) << i;
155. for (j = 0; j < numV; j++)
156. cout << setw(7) << matrix\[i\]\[j\];
157. cout << endl;
158. \}
159. \}
160. bool Graph::check(int tail, int head, int weight)
161. \{
162. if (tail < 0 || tail >= numV || head < 0 || head >= numV
163. || weight <= 0 || weight >= MAXWEIGHT)
164. return false;
165. return true;
166. \}

//构造函数，指定顶点数目
    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;
    }
    /*
    迪杰斯特拉算法
    求指定顶点vertex到其它顶点的最短路径
    不仅要得出最短路径长度，也要得到其序列
    */
    void Graph::Dijkstra(int vertex)
    {
    	int i;
    	//最短路径序列中每个顶点的直接前驱
    	int *pre = new int[numV];
    	for (i = 0; i < numV; i++)
    		pre[i] = vertex;
    	//顶点vertex到各个顶点的路径长度
    	int *Distance = new int[numV];
    	//初始化路径长度
    	for (i = 0; i < numV; i++)
    		Distance[i] = matrix[vertex][i];
    	//标记各个顶点最短路径找到与否
    	bool *find = new bool[numV];
    	memset(find, 0, numV);
    	find[vertex] = true;
    	int d, v, count;
    	count = 1, v = vertex;
    	while (count < numV)
    	{
    		d = INFINITY;
    		//确定一个最短距离
    		for (i = 0; i < numV; i++)
    		{
    			if (!find[i] && Distance[i] < d)
    			{
    				d = Distance[i];
    				v = i;
    			}
    		}
    		find[v] = true;
    		//更新剩余顶点的前驱和最短距离
    		for (i = 0; i < numV; i++)
    		{
    			if (!find[i])
    			{
    				d = Distance[v] + matrix[v][i];
    				if (d < Distance[i])
    				{
    					pre[i] = v;
    					Distance[i] = d;
    				}
    			}
    		}
    		count++;
    	}
    	//打印最短路径序列和其长度
    	stack<int> s;
    	for (i = 0; i < numV; i++)
    	{
    		if (Distance[i] == 0);
    		else if (Distance[i] == INFINITY)
    			cout << "顶点 " << vertex <<" 到顶点 " << i <<" 无路径！" << endl;
    		else
    		{
    			cout << "顶点 " << vertex << " 到顶点 " << i 
    				 << " 最短路径长度是 " << Distance[i] 
    				 << " ，其序列是...";
    			v = i;
    			s.push(v);
    			do
    			{
    				v = pre[v];
    				s.push(v);
    			} while (v!=vertex);
    			//打印最短路径序列
    			while (!s.empty())
    			{
    				cout << setw(3) << s.top();
    				s.pop();
    			}
    			cout << endl;
    		}
    	}
    	cout << endl;
    	delete[]find;
    	delete[]pre;
    	delete[]Distance;
    }
    //打印邻接矩阵  
    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 << "\*\*\*\*\*\*Dijkstra\*\*\*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 << "Dijkstra..." << endl;
13. for (int i = 0; i < numV; i++)
14. graph.Dijkstra(i);
15. system("pause");
16. return 0;
17. \}

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

运行

![20140803195620968][]![20140803195628093][]

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

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

若有所帮助，顶一个哦！

专栏目录：

*  [数据结构与算法][Link 1]
 *  [c指针][c]

[20140803195620968]: /images/20220612/49566623710a47078bfb32578836c233.png
[20140804183450419]: /images/20220612/1db151a2735b41ab8c9fd2396c99c5c6.png
[20140803195628093]: /images/20220612/53230eac81c1472f857f4947bd36c567.png
[Dijkstra]: http://download.csdn.net/detail/zhangxiangdavaid/7710273
[http_blog.csdn.net_zhangxiangdavaid_article_details_38360337]: http://blog.csdn.net/zhangxiangdavaid/article/details/38360337
[Link 1]: http://blog.csdn.net/zhangxiangdavaid/article/details/25082013
[c]: http://blog.csdn.net/zhangxiangdavaid/article/details/37885275#t1