最短路径算法-Dijkstra算法

oneNeko 于 2021-06-17 发布

Dijkstra算法是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。Dijkstra算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

基础算法

问题：有N个节点，M条边，求某节点到另一节点的最短距离 输入：先输入N(从0开始)代表N个节点，M条边，随后跟随N行，p1,p2,d，最后输入起始点st和终点ed 输出：求最短距离 例：

输入：
7 10
0 1 3
0 5 1
1 2 1
1 3 1
2 3 5
2 5 1
3 4 3
3 6 1
4 5 2
4 6 1
0 6
输出：
4

算法描述：

代码如下：

#include <stdio.h>
#include <iostream>
using namespace std;

#define MAXV 1024
#define INF  1000000000

int N, M;				// 节点个数,边个数
int dis[MAXV];			// 储存起点到各点的距离，默认为极大量不可访问
bool visited[MAXV];		// 标记是否访问，默认为false
int edge[MAXV][MAXV];	// 储存各条边的的距离，默认为极大量不可访问

// Dijkstra算法
void Dijkstra(int st) {
	dis[st] = 0;
	for (int i = 0; i < N; i++) {
		int u = -1, min = INF;

		// 寻找距离新加入点最短的节点
		for (int j = 0; j < N; j++) {
			if (visited[j] == false && dis[j] < min) {
				u = j;
				min = dis[j];
			}
		}

		// 未找到则退出
		if (u == -1) {
			return;
		}

		visited[u] = true;
		for (int v = 0; v < N; v++) {
			if (visited[v] == false && edge[u][v] != INF) {
				if (dis[u] + edge[u][v] <= dis[v]) {
					dis[v] = dis[u] + edge[u][v];
				}
			}
		}
	}
}

int main() {
	// 初始化值
	memset(visited, false, sizeof(visited));
	fill(dis, dis + MAXV, INF);
	fill(edge[0], edge[0] + MAXV * MAXV, INF);

	// 输入值
	int st, ed;
	scanf("%d%d", &N, &M);

	int s1, s2, d;
	for (int i = 0; i < M; i++) {
		scanf("%d%d%d", &s1, &s2, &d);
		edge[s1][s2] = edge[s2][s1] = d;
	}

	scanf("%d%d", &st, &ed);
	Dijkstra(st);

	printf("distance=%d\n", dis[ed]);

	return 0;
}

路径输出

路径输出只需要在更新dis数组时记录下上一个节点的信息，算法结束后回溯输出即可

#include <stdio.h>
#include <iostream>
using namespace std;

#define MAXV 1024
#define INF  1000000000

int N, M;				// 节点个数,边个数
int dis[MAXV];			// 储存起点到各点的距离，默认为极大量不可访问
bool visited[MAXV];		// 标记是否访问，默认为false
int edge[MAXV][MAXV];	// 储存各条边的的距离，默认为极大量不可访问
int path[MAXV];			// 记录路径

// Dijkstra算法
void Dijkstra(int st) {
	path[st] = INF;	//标记一下起始点，方便回溯
	dis[st] = 0;
	for (int i = 0; i < N; i++) {
		int u = -1, min = INF;

		// 寻找距离已访问点最短的边
		for (int j = 0; j < N; j++) {
			if (visited[j] == false && dis[j] < min) {
				u = j;
				min = dis[j];
			}
		}

		// 未找到则退出
		if (u == -1) {
			return;
		}

		visited[u] = true;
		for (int v = 0; v < N; v++) {
			if (visited[v] == false && edge[u][v] != INF) {
				if (dis[u] + edge[u][v] <= dis[v]) {
					dis[v] = dis[u] + edge[u][v];
					path[v] = u;	// 记录上一个节点信息，同时也是最短路径
				}
			}
		}
	}
}

// 回溯输出路径
void PrintPath(int ed) {
	if (path[ed] == INF) {
		printf("%d", ed);
		return;
	}
	PrintPath(path[ed]);
	printf("->%d", ed);
}

int main() {
	// 初始化值
	memset(visited, false, sizeof(visited));
	fill(dis, dis + MAXV, INF);
	fill(edge[0], edge[0] + MAXV * MAXV, INF);
	memset(path, -1, sizeof(path));

	// 输入值
	int st, ed;
	scanf("%d%d", &N, &M);

	int s1, s2, d;
	for (int i = 0; i < M; i++) {
		scanf("%d%d%d", &s1, &s2, &d);
		edge[s1][s2] = edge[s2][s1] = d;
	}

	scanf("%d%d", &st, &ed);
	Dijkstra(st);

	printf("distance=%d\n", dis[ed]);
	printf("route:");
	PrintPath(ed);

	return 0;
}

输出为：

distance=4
route:0->5->4->6

优化

复杂度分析

算法最多需要更新N个点才能得到最短路径，每次遍历节点也需要查询N遍其他节点与该节点的关系，所以空间复杂度应该是O(n^2)；我们使用了N*N邻接表储存边，所以空间复杂度是O(n^2)

空间优化

邻接矩阵实现简单，但是浪费很多空间，在稀疏图中就更加严重了。我们可以使用邻接表来进行优化，邻接表是图中常用的存储结构之一，采用链表来存储，每个顶点都有一个链表，链表的数据表示和当前顶点直接相邻的顶点的数据，即顶点 和边权。 它的优点是：对于稀疏图不会有数据浪费；缺点就是实现相对邻接矩阵来说较麻烦，需要自己实现链表，动态分配内存。 C++可以使用vector代替实现功能

struct Edge{
    int u;  // 节点
    int v;  // 边长
};
vector<Edge> edges[maxn];

在之前代码中，为了更新dis距离，需要遍历N个节点，使用邻接表也可以缩短这个过程，复杂度从O(n^2)->O(m)，即每条边只遍历一次

时间优化

在搜索尚未访问过的离起点最近的点时，需要遍历N个节点。所以如果使用排序算法快速获取距离最近的点，就可以降低整个算法时间复杂度，比如使用堆就可以快速得到最小值。STL中可以使用优先队列priority_queue，它的底层用堆实现，这样总的时间复杂度可以降到O(nlog2n)

参考

https://mp.weixin.qq.com/s/Q4eB7jtY7dtu3Bj1WGl_GQ