简介
这里记录我用优先队列以及vis数组优化的Dijkstra解法，这个优化后的模板也可以用于其他Dijkstra算法解决的题目，用例题阈值距离内邻居最少的城市进行讲解，以下例题中优化后的解法的Dijkstra代码就可以当成模板。
Problem: 1334. 阈值距离内邻居最少的城市
思路
这一题是一道要求在指定距离找到最少邻近城市的城市，而要找到一个城市有多少个邻近城市在指定距离中，则需要计算出该城市到其他所有城市的距离，当然为了准确，肯定是需要计算最短路径，那这个问题就简化成了求解全源最短路径问题，然后再对每个城市到其他城市距离是否在指定范围内进行计数，找出最少的并且编号最大，并且返回该编号。
当然这题最简单的解法就是Floyd算法进行解决，因为Floyd算法就是一个求解全源最短路径的算法，只需要执行一遍Floyd算法就能得出我n遍的Dijkstra算法答案。但是有很多小伙伴们学习算法并没有学习Floyd算法，所以我这套题解可以给这类人群一点思路。
解题方法
要利用Dijkstra算法求解全源最短路问题，则需要对每个城市求解一次单源最短路径(也就是执行一次Dijkstra算法)，而如果但用队列和不做去除反复访问问题的情况下，也是能过的，但是用的时间较长。
我们这里就是需要对重复访问以及队列问题进行一个优化，能够得到一个不一样的效率，我们的优先队列是要小根堆形式的，存储数据结构也就是当前节点的最短路径和当前节点(Dijkstra算法是对当前节点周边城市搜索，所以这里不是下一个访问城市节点而是当前节点)，而这里则会形成一种每次出队的都是最短路径减少了多余的非最短路径的计算。而vis数组就是记录当前城市是否访问过，用来避免重复访问问题。
将最后得出的全源最短路径用一个二维数组minroad记录下来后，我们就可以遍历每个城市的最短路数组，也就是minroad[i]表示当前城市，minroad[i][j]表示i城市到j城市的最短路径，因此我们只需要对每个城市的最短路径数组遍历，将其满足距离的进行计数，然后找出最小值的最大城市编号，因此遍历是从左到右遍历
这是没用优先队列以及vis数组的结果
优化前
class Solution {
public:
int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
const int INF=0x3f3f3f3f;
int **dist = new int*[n];
int **minroad = new int*[n];
for (int i = 0; i < n; ++i) {
dist[i] = new int[n];
minroad[i] = new int[n];
memset(dist[i], INF, sizeof(int) * n);
memset(minroad[i], INF, sizeof(int) * n);
dist[i][i] = 0;
}
for (const auto edge : edges) {
dist[edge[0]][edge[1]] = edge[2];
dist[edge[1]][edge[0]] = edge[2];
}
auto dijkstra=[&](int u){
queue<int>q;
q.push(u);
minroad[u][u]=0;
while(!q.empty()){
int v=q.front();
q.pop();
for(int i=0;i<n;++i){
if(minroad[u][v]!=INF&&dist[v][i]+minroad[u][v]<minroad[u][i]){
minroad[u][i]=dist[v][i]+minroad[u][v];
q.push(i);
}
}
}
};
for(int i=0;i<n;++i){
dijkstra(i);
}
// 统计每个城市到达其他城市的数量
int minReachableCities = n + 1;
int result = -1;
for (int i = 0; i < n; ++i) {
int reachableCities = 0;
for (int j = 0; j < n; ++j) {
if (i != j && minroad[i][j] <= distanceThreshold) {
++reachableCities;
}
}
if (reachableCities <= minReachableCities) {
minReachableCities = reachableCities;
result = i;
}
}
return result;
}
};
这是利用优先队列和vis数组优化的结果
优化后
class Solution {
public:
int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
const int INF=0x3f3f3f3f;
int **dist = new int*[n];
int **minroad = new int*[n];
for (int i = 0; i < n; ++i) {
dist[i] = new int[n];
minroad[i] = new int[n];
memset(dist[i], INF, sizeof(int) * n);
memset(minroad[i], INF, sizeof(int) * n);
dist[i][i] = 0;
}
for (const auto edge : edges) {
dist[edge[0]][edge[1]] = edge[2];
dist[edge[1]][edge[0]] = edge[2];
}
auto dijkstra=[&](int u){
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
pq.push({0,u});
vector<bool>vis(n,false);
minroad[u][u]=0;
while(!pq.empty()){
int v=pq.top().second;
pq.pop();
if(vis[v]) continue;
vis[v]=true;
for(int i=0;i<n;++i){
//找出u到i城市的最短路径
if(minroad[u][v]!=INF&&dist[v][i]+minroad[u][v]<minroad[u][i]){
minroad[u][i]=dist[v][i]+minroad[u][v];
pq.push({minroad[u][i],i});
}
}
}
};
for(int i=0;i<n;++i){
dijkstra(i);
}
// 统计每个城市到达其他城市的数量
int minReachableCities = n + 1;
int result = -1;
for (int i = 0; i < n; ++i) {
int reachableCities = 0;
for (int j = 0; j < n; ++j) {
if (i != j && minroad[i][j] <= distanceThreshold) {
++reachableCities;
}
}
if (reachableCities <= minReachableCities) {
minReachableCities = reachableCities;
result = i;
}
}
return result;
}
};