C++用Dijkstra(迪杰斯特拉)求最短路径的算法解析_C

算法介绍

迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。

算法思想

按路径长度递增次序产生算法：

把顶点集合V分成两组：

（1）S：已求出的顶点的集合（初始时只含有源点V0）

（2）V-S=T：尚未确定的顶点集合
将T中顶点按递增的次序加入到S中，保证：

（1）从源点V0到S中其他各顶点的长度都不大于从V0到T中任何顶点的最短路径长度

（2）每个顶点对应一个距离值

S中顶点：从V0到此顶点的长度

T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度

依据：可以证明V0到T中顶点Vk的，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和

应用举例

（1）题目：编写一个校园导游程序，为来访的客人提供各种信息查询服务。

主要功能：1.设计学校的校园平面图，所含景点不少于10个：顶点表示景点，边表示路径等；

2.为客人提供图中任意景点相关信息的查询；

3.为客人提供图中任意景点的问路查询，即查询人以景点间的一条最短路径。

要求：1.设计一个主界面；

2.设计功能菜单，供用户选择

3.有一定的实用性。

（2）设计思路：

1、该题主要有算法思路以及程序的逻辑思路，首先从逻辑思路讲，进入程序，首先设计一个主菜单，选项有景点信息查询，最短路径查询以及显示景点的平面视图三个子菜单，然后根据用户的输入选择的子菜单前的编号，分进入不同的子菜单；该功能是由if….else if…. 语句实现。在景点信息查询和最短路径查询子菜单下还有二级子菜单，都是列出所有景点并在前面编号，查询景点信息时，输入景点前面的编号即可，查询最短路径时，先输入起点的编号，再输入终点的编号。而显示景点视图则调用景点平面图函数即可显示。

2、算法思路主要是迪杰斯特拉算法的思路，利用迪杰斯特拉算法求最短路径。

3、先定义好图的储存结构，本题采用邻接矩阵的方式来表示图，并在主函数中初始化该图；

4、定义三个全局一维数组，一个bool类型数组S[]用来记录从v0到vi是否已经确定了最短路径，是则记S[i]=true,否记S[i]= flase；一个int 类型数组Path[]用来记录从v0到vi的当前最短路径上的vi的直接前驱顶点编号，若v 到vi之间有边则记Path[i] = v的编号，否则记Path[i] = -1；最后一个数组D[]用来记录从v0到vi之间的最短路径长度，存在则记v0到vi之间边的权值或者权值和，否则记为MAX

5、定义一个求最短路径的函数，传入的参数为图和起点，首先进行初始化工作，初始化S[]数组全为false，D[]数组初始化为起点到各个顶点的权值，Path[]数组初始化为起点是否与各顶点有边，有则记v0否则记-1；

6、然后进行n-1次for循环，找出vo到其余n-1个顶点之间的最短路径，比较当前D[]数组中最小值，找到最小值的编号v，该编号就是从v0出发到所有顶点中距离最短的顶点编号，然后把S[v]的值置为true。说明从v0出发到顶点v已经找到最短路径；

7、接着就要更新D[]数组，因为D[]数组是记录最短路径的，现在已经找到了一个顶点的最短路径，已该顶点v为中间点，判断从该顶点v出发到剩下的顶点的路径长度加上该点到v0的路径长度是否小于直接从v0出发到其余顶点的路径长度，如果小于，则更新D[i]为以该顶点v为中间点求得的路径长度。更新Path[i] = v；即i的前驱不再是v0而是v;

8、循环（6）（7）两步n-1次即可得到D[]数组，输出D[]数组既是v0到所有顶点的最短路径长度；

（3）源代码：

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

#include

usingnamespacestd;

/**

*作者：Dmego

*时间：2016-12-12

#define MAX 1000000 //表示极大值∞

#define max 10

boolS[max];//记录从源点V0到终点Vi是否已经确定为最短路径，确定了记true，否则记false

intPath[max];//记录从源点V0到终点Vi的当前最短路径上终点Vi的直接前驱顶点序号，若V0到Vi之间有边前驱为V0否则为-1

intD[max];//记录源点到终点之间最短路径的长度，存在记V0到Vi的边的权值，否则记为MAX

typedefstruct

{

string vexs[max];//顶点表

intarcs[max][max];//邻接矩阵

intvexnum, arcnum;//图当前点数和边数

}AMGraph;

//利用迪杰斯特拉算法求最短路径

voidShortestPath_DIJ(AMGraph &G,intv0)

{//使用迪杰斯特拉算法求有向网G中的V0 定点到其余顶点的最短路径

intn = G.vexnum;//顶点数

for(intv = 0; v < n; v++)//n个顶点依次初始化

{

S[v] =false;//S初始化为空集

D[v] = G.arcs[v0][v];//将v0到各个终点的最短路径长度初始化为边上的权值

if(D[v] < MAX)

Path[v] = v0;//如果v0和v之间有边，则将v的前驱初始化为v0

else

Path[v] = -1;//如果v0和v之间无边，则将v的前驱初始化为-1

}

S[v0] =true;//将v0加入s

D[v0] = 0;//源点到源点的权值为0

//---------初始化结束，开始主循环，每次求得v0到某个顶点的最短路径，将v加到S数组

for(inti = 1; i < n; i++)//依次对其余n-1个顶点进行计算

{

intmin = MAX;

intv = v0;

for(intw = 0; w < n; w++)

{

if(!S[w] && D[w] < min)

{//选择一条当前最短路径，终点为v

v = w;

min = D[w];

}

S[v] =true;//将v加到s集合中

for(intw = 0; w < n; w++)

{//更新从v0出发到集合V-S上所有顶点的最短路径长度

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的前驱为v

}

//背景函数

voidbackGround()

{

cout <<"|*****************************************************************| 100="" 125="" 135="" 140="" 145="" 150="" 160="" 200="" 230="" cout="" ------="">>>请选择：";

}

//景点信息查询二级菜单

voidjmenu()

{

cout <<"|*****************************************************************| cout="">>>请要查询的景点编号：";

}

//最短路径查询二级菜单

voidpmenu()

{

cout <<"|*****************************************************************| cout="">>>请依次输入起点编号和终点编号：";

}

voidmain()

{

//初始化操作

AMGraph amg = { {"信息学院","综合餐厅","西操场","体育馆","春晖楼",

"基教","九教","九栋","沁园","翠园"},

//-1代表两边不相连，权值无限大

//邻接矩阵 /* 信综西体春基教栋沁翠*/

{{MAX,MAX,MAX,140,MAX,200,150,MAX,100,125 },

{MAX,MAX,MAX,MAX,145,230,MAX,100,MAX,MAX },

{MAX,MAX,MAX,150,MAX,MAX,200,MAX,MAX,MAX },

{140,MAX,150,MAX,MAX,MAX,MAX,MAX,100,MAX },

{MAX,145,MAX,MAX,MAX,150,MAX,MAX,MAX,MAX },

{200,230,MAX,MAX,150,MAX,MAX,160,MAX,135 },

{150,MAX,200,MAX,MAX,MAX,MAX,MAX,MAX,MAX },

{MAX,200,MAX,MAX,MAX,160,MAX,MAX,MAX,MAX },

{100,MAX,MAX,100,MAX,MAX,MAX,MAX,MAX,MAX },

{125,MAX,MAX,MAX,MAX,135,MAX,MAX,MAX,MAX }

},10,14};

intf, ff;

intstart, end;

while(true)

{

cout << endl;

menu();

cin >> f;

if(f == 1)

{

jmenu();

cin >> ff;

//景点信息从文件中读取

ifstream outfile("schooltravel.txt", ios :: out | ios :: binary);

if(!outfile)

{

cerr <<"读取景点介绍文件失败！ string="" inti="m-1;" cout="" ff="=" f="=" cin="" start="" -="" inttemp="end-1;</div" m="0;</div" end="" temp1="temp" temp2="Path[temp1];</div" temp="temp2;</div" i="">";

}

cout << endl;

cout <<"最短路径值为： end="" -="" f="=" cout="">>>退出成功！"<< endl;

exit(0);

}

（4）运行截图：

总结

以上就是关于C++用Dijkstra算法(迪杰斯特拉算法)求最短路径的全部内容了，希望本文的内容对大家的学习或者工作带来一定的帮助，如果有疑问大家可以留言交流。

搜索

热门标签:

C++用Dijkstra(迪杰斯特拉)求最短路径的算法解析