Dijkstra算法

求图的最短路径问题具有很强的现实意义，在实际生活的很多方面都有应用。同时也有很多种算法解决该问题，这里我们讨论Dijkstra算法。

问题描述

已知加权图$G=(V,E)$，求G（结点和路径组成的)中任意结点之间的最短路径。

分析设计

解决最短路径问题最常见的有两种算法，Floyd算法和Dijkstra算法。
Floyd算法详见博客https://blog.csdn.net/weixin_42182525/article/details/98075539

下面介绍Dijkstra算法。

Dijkstra算法使用了广度优先遍历解决赋权有向图或者无向图的单源最短路径问题。Dijkstra算法采用的是一种贪心的策略，每次选取最优的点，逐渐拓展至整个图，以求出整个图的最短路径。

与Floyd算法不同的是：

• Floyd算法可以同时求所有点到其他点最短路径，Dijkstra算法必须以图中一个点为起始点，求到图中其他点的最短距离。
• Floyd算法可以求任意加权图的最短路径算法，但Dijkstra算法只能计算正权加权图，不能有负权。

Dijkstra算法的基本思想是：

1. 我们采用二维数组邻接矩阵的形式储存图并将图初始化；
2. 选择其中一个顶点作为计算最短路径的起点。
3. 构造一个d一维数组dis[n]，其中n是顶点个数，dis用来记录最短路径距离。初始化dis，其值为图中各点到起点的直接距离（即邻接顶点记为其权值，不相邻的顶点记为∞）；
4. 每次中dis数组中找出最小值，该值就是起点到该点的最短路径距离，（可以将该点加一个标志位已记录该点路径已确定）；
5. 在加入了一个新的确定了点之后就需要更新dis数组，看其余点能否通过这个确定的点到达起始点且距离能够更短。
6. 重复4、5步，直到所有点都找到了最短路径。

举个栗子

在此图中，求点A到其他点的最短路径。

1. 首先，初始化dis数组，用集合S代表已找到最短路径的点；

A	B	C	D	E
0	10	3	∞	∞

S = { A } S =\{ A\} S={A}

2. 我们找出dis数组中最小值3，对应点C，将C加入集合S；

A	B	C	D	E
0	10	3	∞	∞

S = { A , C } S =\{ A,C\} S={A,C}

3. 根据点C，更新dis数组，从A经过C到其他点的距离；

A	B	C	D	E
0	7	3	11	5

S = { A , C } S =\{ A,C\} S={A,C}

4. 选出dis中最小值5，对应点E，将E加入集合S；

A	B	C	D	E
0	7	3	11	5

S = { A , C , E } S =\{ A,C,E\} S={A,C,E}

5. 根据点E更新dis数组（发现没有距离比之前更短，因此不变）；

A	B	C	D	E
0	7	3	11	5

S = { A , C , E } S =\{ A,C,E\} S={A,C,E}

6. 选出dis最小值7，对应点B，将B加入集合S；

A	B	C	D	E
0	7	3	11	5

S = { A , C , E , B } S =\{ A,C,E,B\} S={A,C,E,B}

7. 根据点B，更新dis数组；

A	B	C	D	E
0	7	3	9	5

S = { A , C , E , B } S =\{ A,C,E,B\} S={A,C,E,B}

8. 只剩最后一个点D，将D加入集合S，此时所有点都在集合S中（即所有点都找到了最短路径）；

A	B	C	D	E
0	7	3	9	5

S = { A , C , E , B , D } S =\{ A,C,E,B,D\} S={A,C,E,B,D}

这就是Dijkstra算法的基本过程解法。

gif制作来源于VisuAlgohttps://visualgo.net/zh/sssp?slide=1

源代码

#include<iostream>
#include <vector>
#include <algorithm>
using namespace std;

//点
typedef struct Point{
	int dis = INT_MAX;
	bool visit = false;
};

//输出
void output(vector<Point> p, int start) {
	cout << endl;
	cout << "最短路径的计算起始点为：" << start << endl;
	for (int i = 1; i < p.size(); i++) {
		if (i == start)
			continue;
		if(p[i].dis==INT_MAX)
			cout << "点" << i << "的最短路径为：无最短路径" << endl;
		else
			cout << "点" << i << "的最短路径为：" << p[i].dis << endl;
	}
}

//dij算法
void Dijkstra(vector<vector<int> > g) {
	int vex = g.size() - 1;	//顶点数
	int start;	//计算最短距离的起点
	cout << "输入计算最短路径的点：";
	cin >> start;

	vector<Point> points(vex + 1);	//记录点的信息

	for (int i = 1; i <= vex; i++) 
		points[i].dis = g[start][i];	//初始化dis，记录起点到各点的直接距离
	points[start].visit = true;		//起点访问

	for (int i = 1; i <= vex; i++) {
		int MINdis = INT_MAX;
		int MINvex = 0;
		for (int j = 1; j <= vex; j++) {
			if (!points[j].visit && points[j].dis < MINdis) {	//找出距离最近的点
				MINdis = points[j].dis;
				MINvex = j;
			}
		}
		points[MINvex].visit = true;	//距离最近的点的最短距离确定
		
		for (int i = 1; i <= vex; i++)	//更新dis数组
			if(g[MINvex][i]<INT_MAX)
				points[i].dis = min(points[i].dis, g[MINvex][i] + points[MINvex].dis);
	}

	output(points, start);	//输出结果
}


int main() {
	int vexNum, edgeNum;
	cout << "输入顶点个数和边数：";
	cin >> vexNum >> edgeNum;
	vector<vector<int> > graph(vexNum + 1, vector<int>(vexNum + 1, INT_MAX));
	cout << "输入邻接边和权值a b w：" << endl;
	int a, b, w;
	for (int i = 0; i < edgeNum; i++) {
		cin >> a >> b >> w;
		graph[a][b] = w;
	}
	for (int i = 1; i <= vexNum; i++) {
		graph[i][i] = 0;
	}

	Dijkstra(graph);	//dij算法

	system("pause");
	return 0;
}

/*
1 2 10
1 3 3
2 3 1
2 4 2
3 2 4
3 4 8
3 5 2
4 5 7
5 4 9
*/

运行结果