Dijkstra算法多条最短路径下最短路径的记录

65 阅读 0 评论 43 点赞

我是靠谱客的博主矮小荔枝，这篇文章主要介绍Dijkstra算法多条最短路径下最短路径的记录，现在分享给大家，希望可以做个参考。

1. 我们在使用Dijkstra算法求解源点到其余顶点的最短路径的时候，在大多数情况下最短路径是只有一条的，但是也有可能存在着多条最短路径的情况，所以之前使用整型的pre[]数组来记录当前节点的前驱节点的方法就不再适用这个问题了，所以需要另外的数据结构来进行记录，而题目中告诉我们可能存在着多条最短的路径的时候往往会要求在多条最短路径下的另外一个条件，比如是边权之和最小或者最大，点权之和最小或者最大，我们最简单的想法就是先记录下所有的最短路径，然后使用dfs来选择出在满足多条最短路径下条件的的那一条路径

2. 下面是具体的过程：

① 使用Dijkstra算法记录所有的最短路径

由于此时需要记录所有的最短路径，因此每个节点就会存在着多个前驱节点，这样原先pre数组只能够记录一个前驱节点的方法就不再适用，为了适应多个前驱的情况，不妨把数组定义为vector类型"vector <int> pre[maxSize]"，这样对于每一个节点v来说，pre[v]就是一个变长的数组，里面用来存放节点v的所有能够产生最短路径的前驱节点，例如对于下面的图，pre数组的情况如下所示（假如需要查询某个顶点u是否在v的前驱中的题目，也可以将pre数组声明成set<int>数组，此时使用pre[v].count查询会更加方便一点）：

pre[7] = {5,6};
pre[6] = {3,4};
pre[5] = {1};
pre[4] = {2};
pre[3] = {2};
pre[2] = {1};
pre[1] = {1};

通过上面vector类型的pre数组，就可以使用dfs来获取所有的最短路径：

{v1-->v2-->v3-->v6-->v7}、{v1-->v2-->v4-->v6-->v7}、{v1-->v5-->v7}

下面是具体的pre数组求解的过程：

1）首先，假如d[u] + G[u][v] < d[v]说明以u作为中介点可以使d[v]更优，此时需要令v的前驱节点为u，并且即便原先的pre[v]存放了若干个节点都应该清空，然后再添加u，因为正是因为这个中介点才使得到达v这个节点的路径变短，所有之前到达v的所有节点都需要清除，然后将u节点添加进去

if(d[u] + G[u][v] < d[v]){
	d[v] = d[u] + G[u][v];
	pre[v].clear();
	pre[v].push_back(u);
}

2）如果d[u] + G[u][v] ==d[v]说明以u为中介点可以找到一条距离相等的路径，因此之前v的前驱节点需要在原先的基础上添加上u节点，而不必清空pre[v]

if(d[u] + G[u][v] == d[v]){
    pre[v].push_back(u);
}

经过上面的两个步骤就完成了pre数组的记录多条最短路径的求解过程

3. 下面是完整的代码：

vector <int> pre[maxSize];
void Dijstra(int s){
	fill(d, d + maxSize, INF);
	d[s] = 0;
	for(int i = 0; i < n; i++){
		int u = -1, min = INF;
		for(int j = 0; j < n; j++){
			if(vis[j] == false && d[j] < min){
				u = j;
				min = d[j];
			}
		}
		if(u == -1) return;
		vis[u] = true;
		for(int v = 0; v < n; v++){
			if(vis[v] == false && G[u][v] != INF){
				if(d[u] + G[u][v] < d[v]){
					d[v] = d[u] + G[u][v];
					pre[v].clear();
					pre[v].push_back(u);
				}
			}else if(d[u] + G[u][v] == d[v]){
				pre[v].push_back(u);
			}
		}
	}	
}