Dijksta+DFS求最短路径问题

你的名字 2021-09-21 07:26 376阅读 0赞

### Dijkstra+DFS ###

*   *   *  Dijkstra+DFS思想
         *  Dijkstra实现
         *  DFS实现
         *  例题

> 对于简单的求最短路径的问题，用Dijkstra算法就可以实现。当然，对于加了第二标尺的：比如:如果最短路径有多条，选择边权最小的（花费最小）或者是点权最大的（物质数目多的），也可以用Dijkstra算法，在路径相等的时候去更新第二标尺。然而，对于一些有多个标尺等更复杂的问题的时候。用Dijkstra+DFS算法。难度会降低许多。

### Dijkstra+DFS思想 ###

这个算法的思想是这样的：首先通过Dijkstra算法计算出最短路径，并且得到每个结点的前驱结点（也就是通过该前驱结点可以使得该点到起点的距离最小，这样的结点可能是不唯一的）。这样就可以得到所有的最短路径，然后我们只需要在所有的最短路径中计算出第2，第3等标尺。更新最优路径即可。

### Dijkstra实现 ###

该算法和之前的类似，只不过之前用的是一个数组`pre[n]`来记录每个顶点的前驱结点。这里需要用`vector<int>pre[n]`来记录每一个顶点的前驱结点（因为结果可能不止一个）。同时，当存在顶点u，使得u到v的距离可以更优时，需要先清空pre\[v\]中的结点，然后将u加入。若存在相等的情况，则直接将u加入到v中。

#include<cstdio>
    #include<algorithm>
    #include<vector>
    using namespace std;
    const int INF = 0x3fffffff;
    const int maxn = 520;
    int G[maxn][maxn];//存储图
    vector<int>pre[maxn]; //记录每个顶点的前驱结点 
    vector<int>path,tempPath; //记录最终路径和临时路径 
    int optValue = INF; //第二标尺
    int d[maxn];//最短路径长度
    bool vis[maxn]={ false};
    int n,m,st,ed; //顶点数，边数,起点，终点 
    //找最短路径 
    void Dijskstra(int s){ 
    	fill(d,d+maxn,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(G[u][v] + d[u] < d[v]){ 
    					d[v] = G[u][v]+d[u];
    					pre[v].clear();
    					pre[v].push_back(u);
    				}
    				if(G[u][v] + d[u] == d[v]){ 
    					pre[v].push_back(u);
    				}
    			}
    		}
    	}
    }

### DFS实现 ###

DFS是一个递归函数，考虑递归边界和递归式。递归边界就是到达起点。而递归式就是在到达起点前每次递归的去遍历pre\[v\]中的点。这里要注意最短路径的求法。用tempPath来存放最短的路径。在访问v顶点时就可以把该顶点加入到tempPath中，然后递归遍历pre\[v\]。要注意在到达起点的时候需要将起点也加入到tempPath中，这时候tempPath就存放了**起点到终点的逆序**。在此基础上就可以进行其他标尺的计算了。然后需要压出tempPath中最后加入的结点（起点），该层递归结束。

//这里以花费为第二标尺为例
    void DFS(int v){ 
    	if(v==st){  //到达起点 
    		tempPath.push_back(v); //压入起点 
    		int value = 0; //计算费用
    		for(int i=tempPath.size()-1; i>0; i--){ 
    			int index = tempPath[i];
    			int next = tempPath[i-1];
    			value += cost[index][next];
    		}
    		if(value < optValue){ 
    			//更新
    			optValue = value;
    			path = tempPath; 
    		}
    		tempPath.pop_back();//弹出起点 
    		return; 
    	}
    	tempPath.push_back(v); //压入当前结点 
    	for(int i=0; i<pre[v].size(); i++){ 
    		DFS(pre[v][i]);
    	}
    	tempPath.pop_back(); //for循环结束，说明以末尾tempPath的结点去更新最短路径的情况已经枚举完，需要弹出 
    }

通过上面的计算，最佳路径被存储在path中，最小花费（第二标尺)是optValue中。最短距离在d\[n\]中。这样会很容易求出答案。

### 例题 ###

最后记一到[PAT A 1087 All Roads Lead To Rome][] 的题目。  
这道题目第一标尺是花费（可以看作是结点之间的距离）。在花费相同的情况下，第二标尺是点权之和。若点权之和还是相同，这一平均点权最大来衡量最优。这道题用Dijkstra+DFS就容易做的多。因为在最短路径找到的情况下，求出最短路径上的点权之和和平均点权十分容易。代码如下：注意这里需要将城市名和下标对应。自己在解题的时候，在城市名和点权输入的时候只映射了城市名到下标，忘了映射下标到城市名。。。结果不知道为何例子跑得出来就是一直是0分。。。

#include<iostream>
    #include<string>
    #include<algorithm>
    #include<map>
    #include<vector>
    using namespace std;
    const int INF = 0x3fffffff;
    const int maxn = 250;
    int G[maxn][maxn];
    int d[maxn],weight[maxn];//最短路径（花费),结点权重 
    bool vis[maxn]={ false}; 
    vector<int>pre[maxn];//记录前驱结点
    vector<int>tempPath,path;
    int optSumHappiness=0;
    double optAvgHappiness=0;
    int n,m,st; //结点数，路径条数，起点 
    map<string,int>cityToIndex;
    map<int,string>indexToCity;
    int nums = 0; //最短路径的条数 
    
    void Dijsktra(int s){ 
    	fill(d,d+maxn,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);
    				}
    			}
    		}
    	} 
    }
    
    
    void DFS(int v){ 
    	//到达边界 
    	if(v == st){ 
    		nums++; 
    		tempPath.push_back(v); //加入起点
    		int sumHappiness = 0;
    		for(int i=tempPath.size()-2; i>=0; i--){ 
    			int index = tempPath[i];
    			sumHappiness += weight[index];
    		}
    		double avgHappiness = 1.0*sumHappiness / (tempPath.size()-1);
    		if(sumHappiness > optSumHappiness){ 
    			optSumHappiness = sumHappiness;
    			optAvgHappiness = avgHappiness;
    			path = tempPath;
    		}else if(sumHappiness == optSumHappiness){ 
    			if(avgHappiness > optAvgHappiness){ 
    				optAvgHappiness = avgHappiness;
    				path = tempPath;
    			}
    		}
    		tempPath.pop_back();
    		return;
    	}
    	tempPath.push_back(v);
    	for(int i=0; i<pre[v].size();i++){ 
    		DFS(pre[v][i]);	
    	}
    	tempPath.pop_back();
    }
    
    int main(){ 
    	string start,city1,city2;
    	cin>>n>>m>>start;
    	cityToIndex[start] = 0;
    	indexToCity[0] = start;
    	for(int i=1;i<=n-1; i++){ 
    		cin>>city1>>weight[i];
    		cityToIndex[city1] = i;
    		indexToCity[i] = city1;
    	}
    	
    	//初始化为无穷
    	fill(G[0],G[0]+maxn*maxn,INF); 
    	for(int i=0; i<m; i++){ 
    		cin>>city1>>city2;
    		int c1 = cityToIndex[city1],c2 = cityToIndex[city2];
    		cin>>G[c1][c2];
    		G[c2][c1] = G[c1][c2];
    	}
    	Dijsktra(0);
    	int rom = cityToIndex["ROM"];
    	DFS(rom);
    	printf("%d %d %d %d\n",nums,d[rom],optSumHappiness,(int)optAvgHappiness);
    	for(int i = path.size()-1; i>=0; i--){ 
    		cout<<indexToCity[path[i]];
    		if(i != 0) cout<<"->";
    	}
    	return 0;
    	
    }

[PAT A 1087 All Roads Lead To Rome]: https://pintia.cn/problem-sets/994805342720868352/problems/994805379664297984