所以在解决一些基于dijikstra的leetcode问题时，这个问题出现在我的脑海中。我们在每一步的优先队列中都有节点、距离对。
堆中是否存在重复节点取决于一件事，即当我们将节点标记为已访问(i)时。E确认我们已经找到它的最短长度)。如果在推入队列时标记，则不会有任何重复对象，如果在弹出队列后标记，则可能会有重复对象。
https://leetcode.com/problems/network-delay-time/在这个问题中，我们可以将节点标记为仅在从优先级队列弹出后才访问，否则我们将错过一些可能导致更短路径的边缘。例:[[1、2、1],[2、3、2],[1,3,4]]3.1
如果我们边加边插入我们会在探索1的邻居时得到错误的答案我们所做的是，1->2 queue={2,1} visited={1,2}1->3 queue{(2,1)， (3,4)}因为现在所有的节点都被访问了，我们永远不会遇到路径1->2->3距离=1+2=3。
但在其他问题中，我们可以在插入到优先级队列之前做一个带有visit标记的dijikstra，例如:https://leetcode.com/problems/swim-in-rising-water/
为什么dijikstra with visited标记在插入前是有效的
BFS用于盲目访问节点(可能假设所有权重为1)，Dijkstra将优先考虑权重最小的路径。
Dijkstra算法中堆中何时可以有重复节点?
a
4/ 2
/
b ---- c
| 1
4 |
d
1. here start Dijkstra from a. queue = (a, 0)
2. b, c pushed with path cost into p_queue. queue = (b, 4), (c, 2)
3. c popped. b with another cost pushed. queue = (b, 4), (b, 3) here the new (b, 3) has (ac + cb) cost
4. least b popped. d pushed queue = (b, 4), (d, 7)
5. As we check and mark after pop. b popped. queue = (d, 7)
6. But already visited so returned
7. Process d
但是在其他问题中，我们可以在插入到优先级队列之前做一个带有访问标记的Dijkstra，例如:https://leetcode.com/problems/swim-in-rising-water为什么Dijkstra在插入之前有访问标记有效?
很大程度上取决于问题本身。对于这个特殊的问题，我们直接从节点中获取权值，无论之前或之后推它，它都会同时弹出，但保持访问检查before push可以防止冗余推。
这是我接受的实现，您可以注释掉或保留after pop或before push标记&检查访问的节点，两个都将被接受。
class Solution {
struct PosWeight {
pair<int, int> pos;
int weight;
PosWeight(pair<int, int> a, int weight): pos(a), weight(weight){}
};
int visited[51][51] = {0};
int traverse(vector<vector<int>>& grid) {
int row = size(grid);
int column = size(grid[0]);
vector<pair<int, int>> directions = { {0,1}, {1,0}, {-1,0}, {0,-1} };
auto isValidTo = [&grid, row, column]
(pair<int, int> direction, pair<int, int> pos) {
if (pos.first + direction.first >= row) return false;
if (pos.first + direction.first < 0) return false;
if (pos.second + direction.second >= column) return false;
if (pos.second + direction.second < 0) return false;
return true;
};
auto comp = [](PosWeight &a, PosWeight &b) {
return a.weight > b.weight;
};
int maxx =INT_MIN;
priority_queue<PosWeight, vector<PosWeight>, decltype(comp)> pq(comp);
pq.emplace(make_pair(0,0), grid[0][0]);
while(!pq.empty()) {
auto elem = pq.top();
pq.pop();
// You can comment out this portion and keep the later one before pushing in queue
if (visited[elem.pos.first][elem.pos.second]) continue;
visited[elem.pos.first][elem.pos.second] = 1;
// ---
maxx = max(maxx, elem.weight);
if (elem.pos.first == row - 1 && elem.pos.second == column - 1)
return maxx;
for(auto direction: directions)
if (isValidTo(direction, elem.pos)) {
pair<int,int> toGo = make_pair( direction.first + elem.pos.first,
direction.second + elem.pos.second );
auto weight = grid[toGo.first][toGo.second];
// You can comment out this portion and keep the later one before pushing in queue
// if (visited[toGo.first][toGo.second]) continue;
// visited[toGo.first][toGo.second] = 1;
// -----
pq.emplace(toGo, weight);
}
}
return maxx;
}
public:
int swimInWater(vector<vector<int>>& grid) {
return traverse(grid);
}
};
但是，对于https://leetcode.com/problems/network-delay-time这个问题，检查必须是after pop，因为这样做before push将导致早期所有节点访问，而不是优先考虑您在问题中所述的最短。
class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
auto comp = [](pair<int,int> &a, pair<int,int> &b) {
return a.second > b.second;
};
priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(comp)> que(comp);
vector<vector<int>> rel(n, vector<int>(n, -1));
for (auto &time: times)
rel[time[0] - 1][time[1] - 1] = time[2];
vector<int> visit(n, 0);
que.push({k-1, 0});
int sz = n;
while (size(que)) {
auto now = que.top();
que.pop();
if (visit[now.first]) continue;
visit[now.first] = 1;
if (!--sz) return now.second;
auto id = now.first, val = now.second;
for (int i = 0; i < n; ++i)
if (rel[id][i] != -1) {
// cant do checking here
que.push({i, val + rel[id][i]});
}
}
return -1;
}
};
所以，归根结底，这取决于问题的性质和要求。