我写了一个模板，把 Dijkstra 算法变成了默写题 :: labuladong的算法小抄 #1050
Replies: 50 comments 20 replies
-
"因为优先级队列自动排序的性质，每次从队列里面拿出来的都是 distFromStart 值最小的，所以当你从队头拿出一个节点，如果发现这个节点就是终点 end，那么 distFromStart 对应的值就是从 start 到 end 的最短距离。" 以上判断好像有问题 |
Beta Was this translation helpful? Give feedback.
-
|
你忘记更新条件了，如果已经记录到ac距离是3，距离是4的路径就不会被更新上去，反之，如果是4，那么最后肯定会被3更新掉，使用贪心一定程度上可以优化效率，但是这里的贪心并不保证一定正确 |
Beta Was this translation helpful? Give feedback.
-
|
虽然你按照4的那个路径先添加了c，但是加进去不代表就立刻访问到，因为前面肯定会有比4小的，在你访问完比4小的节点时候，4已经被更新为3了 |
Beta Was this translation helpful? Give feedback.
-
|
re: doubleSkinMilk |
Beta Was this translation helpful? Give feedback.
-
|
东哥好，大家好。我有个问题没想明白。在第 743 题「网络延迟时间」中，为什么curDistFromStart > distTo[curId]。也就是当前路径长度小于dp table里储存的路径长度时，不去更新distTo[curId]啊。 int[] dijkstra(int start, List<int[]>[] graph){
int[] distTo = new int[graph.length];
Arrays.fill(distTo, Integer.MAX_VALUE);
distTo[start] = 0;
PriorityQueue<State> pq = new PriorityQueue<>(
graph.length, (a,b) ->(a.distFromStart - b.distFromStart)
);
pq.offer(new State(start,0));
while(!pq.isEmpty()){
State curState = pq.poll();
int curId = curState.id;
int curDistFromStart = curState.distFromStart;
if(curDistFromStart > distTo[curId]){
continue;
}else{
// distTo[curId] = curDistFromStart;
for(int[] nextNode : graph[curId]){
int nextId = nextNode[0];
int nextDistFromStart = distTo[curId] + nextNode[1];
if(nextDistFromStart < distTo[nextId]){
distTo[nextId] = nextDistFromStart;
pq.offer(new State(nextId, nextDistFromStart));
}
}
}
}
return distTo;
} |
Beta Was this translation helpful? Give feedback.
-
|
distTo[nextId] = nextDistFromStart; |
Beta Was this translation helpful? Give feedback.
-
|
他的意思是为啥注释掉这一行，结果还是正确的。我也不是很理解。 |
Beta Was this translation helpful? Give feedback.
-
|
从起点开始推，第一次是起点到起点自己这条路径，距离为0，那么对于后续节点的遍历，本轮要更新的距离实际上一轮就已经更新过了 |
Beta Was this translation helpful? Give feedback.
-
|
我觉得可以理解为，一开始只添加一个节点。与第一个节点相连的节点，都由offer函数添加，而满足offer条件的时候，已经在if代码块中完成了distTo[curId] 的赋值，所以可以想象，后续poll出来的每一个节点的distTo[curState.id] 与 curState.distFromStart两个值一定相等，都是由满足条件更新节点后才添加进pq中的。 |
Beta Was this translation helpful? Give feedback.
-
|
因为curDistFromStart = curState.distFromStart的值是从pq里poll出来了，而poll之前肯定要offer到pq里，而curDistFromStart 对应的节点在被offer到pq里面之前，已经使用了if(nextDistFromStart < distTo[nextId])语句判断了是否要更新该节点对应的distTo的值，如果要更新的话，那么就说明curDistFromStart 的值比上一个distTo[nextId])的值要小，因此必然不存在curDistFromStart < distTo[curId]的情况 |
Beta Was this translation helpful? Give feedback.
-
|
我刚才试了下，加上 distTo[curId] = curDistFromStart;对结果没有影响。我能想明白加上的逻辑，但想不明白为什么去掉后算法还是对的呢？ |
Beta Was this translation helpful? Give feedback.
-
|
这一句是不是可以拿掉呢？ if(curDistFromStart > distTo[curId]){ |
Beta Was this translation helpful? Give feedback.
-
|
我也有这个疑问,到现在还没想明白 |
Beta Was this translation helpful? Give feedback.
-
|
这句是可以拿掉的，要么distTo[curId]已经更新了，那此时：curDistFromStart == distTo[curId]； |
Beta Was this translation helpful? Give feedback.
-
|
@doubleSkinMilk 仔细想一下确实有问题，不知道东哥能不能出来解释下？ |
Beta Was this translation helpful? Give feedback.
-
|
@YZG112358 "在你举得例子中 b->c 会先于 f->c 被遍历到，因为distFromStart是一个Priority Queue，而distFromStart[b] < distFromStart[f]"，理论上来说f在b后面是没有问题的，关键有可能还没有到b呢f就先到了终点c，我还是很难理解这种思路 |
Beta Was this translation helpful? Give feedback.
-
|
@doubleSkinMilk @southrivers
由此可以推断
用公式表达
|
Beta Was this translation helpful? Give feedback.
-
|
大佬解释的很详细 |
Beta Was this translation helpful? Give feedback.
-
|
这里关于为什么priortyQueue可以提前结束循环最好的解释！ |
Beta Was this translation helpful? Give feedback.
-
|
@JackShang94 for(int[] nextNode : graph[curId]){
int nextId = nextNode[0];
int nextDistFromStart = distTo[curId] + nextNode[1];
if(nextDistFromStart < distTo[nextId]){
//******************************************************
distTo[nextId] = nextDistFromStart;
//******************************************************
pq.offer(new State(nextId, nextDistFromStart));
}
} |
Beta Was this translation helpful? Give feedback.
-
|
@Goolloo,我有相同的疑问，请问为什么这个地方nextDistFromStart = distTo[curId] + nextNode[1];这么更新之后再加入PriorityQueue也是对的呢？这个时候distTo[curId] >= curDistFromStart，不应该先更新distTo[curId] = curDistFromStart吗？ |
Beta Was this translation helpful? Give feedback.
-
|
@JackShang94 @XiaoyuZhou-hub 关于你们的疑问， @Goolloo 说的是对的，入队的时候已经。你可以先不考虑 Dijkstra 算法，就考虑 常规 BFS 算法，也是要在入队之前把节点加入 至于为什么要在入队的时候加入 由于可能多次访问同一节点（走回头路），所以在一个节点 Dijkstra 算法作为进阶版的 BFS 算法，也是同样的道理， @JackShang94 你在那里加代码不会产生任何影响，因为 进一步，你甚至可以尝试把 |
Beta Was this translation helpful? Give feedback.
-
|
@doubleSkinMilk @southrivers 你们说的不对，可能对算法的执行过程还是不熟悉，不妨自己画个图手动执行一下算法逻辑就理解了。 以你们说的例子，节点 |
Beta Was this translation helpful? Give feedback.
-
|
@apache1011, 第三题确实感觉转换成计算最小的failure_rate再结合东哥的模板和思路会更加好理解. import heapq
class Solution:
def _build_graph(self, n, edges, succ_probs):
graph = [[] for _ in range(n)]
for edge, succ_prob in zip(edges, succ_probs):
graph[edge[0]].append([edge[1], succ_prob])
graph[edge[1]].append([edge[0], succ_prob])
return graph
def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
# build the graph for N nodes - by using edges and succ_prob lists
graph = self._build_graph(n, edges, succProb)
# set max value as place holder to help to calc the smaller failure rates
path_probs = [float('inf')] * n
# init failure rate should be 0
path_probs[start] = 0
pq = [State(start, 0)]
while pq:
curr_node = heapq.heappop(pq)
curr_id = curr_node.id
curr_prob = curr_node.prob
if curr_id == end:
# return 1 - the smallest_failure_rate
return 1 - curr_prob
# the current failure rate has been the smaller one
if path_probs[curr_id] < curr_prob:
continue
for nei_id, nei_prob in graph[curr_id]:
# 1 - (1 - failure_rate) * success_rate = evolved_failure_rate
nxt_node_prob = 1 - (1-path_probs[curr_id]) * nei_prob
if path_probs[nei_id] > nxt_node_prob:
path_probs[nei_id] = nxt_node_prob
heapq.heappush(pq, State(nei_id, nxt_node_prob))
return 0
class State:
def __init__(self, id, prob):
self.id = id
self.prob = prob
def __lt__(self, other):
# track the failure rate - needs to return smaller one
# so that 1 - smallest_failure_rate = max_success_rate
return self.prob < other.prob |
Beta Was this translation helpful? Give feedback.
-
|
东哥 捉个插件虫 1514的思路是1631的 |
Beta Was this translation helpful? Give feedback.
-
|
@ireneli0 感谢指出，已修复 |
Beta Was this translation helpful? Give feedback.
-
|
js 版 dijkstra 模板 function dijkstra(start, /* end */) {
// 图中节点的个数
const n = graph.length;
// 记录最短路径的权重，你可以理解为 dp table
// 定义：distTo[i] 的值就是节点 start 到达节点 i 的最短路径权重
// 求最小值，所以初始化为正无穷
const distTo = new Array(n).fill(Infinity);
// base case，start 到 start 的最短距离就是 0
distTo[start] = 0;
// 优先级队列，dist 较小的排在前面
const q = new PriorityQueue((a, b) => a[1] < b[1]);
// 从起点 start 开始进行 BFS
q.push([start, 0]);
while (!q.isEmpty()) {
const [v, dist] = q.pop();
// // 如果只要到 end, 在这里加一个判断就行了，其他代码不用改
// if (v === end) {
// return dist;
// }
if (dist > distTo[v]) {
// 已经有一条更短的路径到达 v 节点了
continue;
}
// 将相邻节点装入队列
for (const n of graph[v]) {
let distToN = distTo[v] + weight(v, n);
// 看看从 v 达到 n 的距离是否会更短
if (distToN < distTo[n]) {
// 更新 dp table
distTo[n] = distToN;
q.push([n, distToN]);
}
}
}
// // 如果只要到 end, 如果运行到这里，说明从 start 无法走到 end
// return Infinity
return distTo;
} |
Beta Was this translation helpful? Give feedback.
-
|
我觉得从算法证明的角度来理解dijkstra算法会更容易一些。dijkstra算法的证明也比较简单，主要是用反证法的思想，个人感觉用这种思想理解本文中的题目相对而言更简单且更透彻一些。希望东哥可以考虑一下讲解dijkstra算法的证明 ^_^ |
Beta Was this translation helpful? Give feedback.
-
|
1514 python3 from heapq import heappush, heappop
#Dijkstra Algorithm解决“最长路径问题”
#要求每次增加路径，路径权值减少
#标准最短路径要求无负数权值边，即为要求增加路径，路径权值增加
#求最短路径和最长路径问题为完全镜像
class Solution:
def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
graph = [[] for i in range(n)]
for i in range(len(edges)):
nodeA = edges[i][0]
nodeB = edges[i][1]
prob = succProb[i]
graph[nodeA].append((nodeB,prob))
graph[nodeB].append((nodeA,prob))
probTo = [float('-inf')] * n
probTo[start] = 1
heap = []
heappush(heap, ((-1)*probTo[start],start))
while heap:
probToCur, curNode = heappop(heap)
probToCur = probToCur*(-1)
if curNode == end:
return probTo[curNode]
if probToCur < probTo[curNode]:
continue
for nextPair in graph[curNode]:
nextNode = nextPair[0]
probToNext = nextPair[1]
if probToCur * probToNext > probTo[nextNode]:
probTo[nextNode] = probToCur * probToNext
heappush(heap,((-1)*probTo[nextNode],nextNode))
return 0 |
Beta Was this translation helpful? Give feedback.
-
|
didi打卡 这篇好难。看的中间还被打断了一下。 |
Beta Was this translation helpful? Give feedback.
-
|
概率最大的路径 class Solution {
public:
class state{
public:
int id;
double distFromStart;
friend bool operator <(const state& a, const state& b){
return a.distFromStart<b.distFromStart;//大的放在前面
}
state(int id,double distFromStart):id(id),distFromStart(distFromStart){}
};
double dijistra(int n, vector<vector<vector<double>>>& graph, int start, int end){
priority_queue<state> que;
vector<int> vec;
state start_state= state(start,1);//note 1 neither 0
que.push(start_state);
vector<double> node_cost(n,-1);//初始化为一个特殊值
node_cost[start]=1;//note init
vector<int> res;
while(!que.empty()){
state cur_node=que.top();
que.pop();
double cur_cost=cur_node.distFromStart;
int cur_id=cur_node.id;
if(cur_id==end){
res.push_back(cur_id);
return cur_cost;
break;
}
if(cur_cost<node_cost[cur_id]){
//已经有一条更大概率的路径到达当前节点
continue;
}
for(int i=0;i<graph[cur_id].size();i++){
int neight_id=graph[cur_id][i][0];
double neight_cost=graph[cur_id][i][1];
double cur_cost=node_cost[cur_id]*neight_cost;
if(cur_cost>node_cost[neight_id]){
node_cost[neight_id]=cur_cost;
state neight= state(neight_id,cur_cost);
que.push(neight);
}
}
}
return 0.0;
}
double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
vector<vector<vector<double>>> graph(n+1);
for(int i=0;i<edges.size();i++){
int from=edges[i][0],to =edges[i][1];
double weight=succProb[i];
graph[from].emplace_back(vector<double>{(double)to,weight});
graph[to].emplace_back(vector<double>{(double)from,weight});
}
double res=dijistra(n,graph,start,end);
return res;
}
}; |
Beta Was this translation helpful? Give feedback.
-
class State {
public:
int x, y;
int effortFromStart;
State (int x, int y, int effortFromStart) {
this->x = x;
this->y = y;
this->effortFromStart = effortFromStart;
}
};
class ComparisonClass {
public:
bool operator() (const State l, const State r) const {
return l.effortFromStart > r.effortFromStart;
}
};
class Solution {
public:
int minimumEffortPath(vector<vector<int>>& heights) {
int m = heights.size(), n = heights[0].size();
vector<vector<int>> effortTo(m);
for (int i = 0; i < m; i ++) {
effortTo[i] = vector<int>(n, INT_MAX);
}
effortTo[0][0] = 0;
priority_queue<State, vector<State>, ComparisonClass> pq;
pq.push(State(0, 0, 0));
while (pq.size() > 0) {
State curState = pq.top(); pq.pop();
int curX = curState.x, curY = curState.y;
int curEffortFromStart = curState.effortFromStart;
if (curX == m - 1 && curY == n - 1) {
return curEffortFromStart;
}
if (curEffortFromStart > effortTo[curX][curY]) {
continue;
}
for (pair<int, int> neighbor: adj(heights, curX, curY)) {
int nextX = neighbor.first, nextY = neighbor.second;
int effortToNextNode = max(
effortTo[curX][curY],
abs(heights[curX][curY] - heights[nextX][nextY])
);
if (effortTo[nextX][nextY] > effortToNextNode) {
effortTo[nextX][nextY] = effortToNextNode;
pq.push(State(nextX, nextY, effortToNextNode));
}
}
}
return -1;
}
vector<pair<int, int>> adj(vector<vector<int>> matrix, int x, int y) {
vector<vector<int>> dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int m = matrix.size(), n = matrix[0].size();
vector<pair<int, int>> neighbors;
for (vector<int> dir: dirs) {
int nx = x + dir[0];
int ny = y + dir[1];
if (nx >= m || nx < 0 || ny >= n || ny < 0) {
continue;
}
neighbors.push_back({nx, ny});
}
return neighbors;
}
};改成下面的代码才通过，感觉cpp的编译优化做的不是很好。 class Solution {
public:
vector<vector<int>> dirs = {
{-1, 0},
{0, -1}, {0, 1},
{1, 0}
};
int minimumEffortPath(vector<vector<int>>& heights) {
using state = pair<int, pair<int, int>>;
int m = heights.size();
int n = heights[0].size();
vector<vector<int>> effortTo(m, vector<int>(n, INT_MAX));
effortTo[0][0] = 0;
priority_queue<state, vector<state>, greater<state>> pq;
pq.push({0, {0, 0}});
while (pq.size() > 0) {
auto curState = pq.top(); pq.pop();
int curEffortFromStart = curState.first;
int curX = curState.second.first;
int curY = curState.second.second;
if (curEffortFromStart > effortTo[curX][curY]) {
continue;
}
if (curX == m - 1 && curY == n - 1) {
return curEffortFromStart;
}
for (vector<int> dir: dirs) {
int nextX = curX + dir[0];
int nextY = curY + dir[1];
if (nextX >= m || nextX < 0 || nextY >= n || nextY < 0) {
continue;
}
int effortToNextNode = max(
effortTo[curX][curY],
abs(heights[curX][curY] - heights[nextX][nextY])
);
if (effortTo[nextX][nextY] > effortToNextNode) {
effortTo[nextX][nextY] = effortToNextNode;
pq.push({effortToNextNode, {nextX, nextY}});
}
}
}
return 0;
}
}; |
Beta Was this translation helpful? Give feedback.
-
|
而且，总体的耗时，居然比Java的慢很多。简直怀疑cpp的真实性能。 |
Beta Was this translation helpful? Give feedback.
-
|
Cpp 注意传值和传引用的区别。容器里装的应该都是指针引用而非值。 |
Beta Was this translation helpful? Give feedback.
-
while (!pq.isEmpty()) {
State curState = pq.poll();
int curNodeID = curState.id;
int curDistFromStart = curState.distFromStart;
// === A 代码块 开始 ===
if (curDistFromStart > distTo[curNodeID]) {
// 已经有一条更短的路径到达 curNode 节点了
continue;
}
// === A 代码块 结束 ===
// 将 curNode 的相邻节点装入队列
for (int nextNodeID : adj(curNodeID)) {
// ====== 问题 开始 ======
// 这里有个疑问，是取 distTo[curNodeID] 还是 curDistFromStart 参与计算呢？
// 能走到这，【A 代码块】保证了 curDistFromStart <= distTo[curNodeID] 的
// 问题：会不会有一种场景，curDistFromStart < distTo[curNodeID]，导致计算 distToNextNode 错误了
// ====== 问题 结束 ======
// 看看从 curNode 达到 nextNode 的距离是否会更短
int distToNextNode = distTo[curNodeID] + weight(curNodeID, nextNodeID);
}
} |
Beta Was this translation helpful? Give feedback.
-
|
while里面的第一个if判断是不是多余的 ？在进入for循环之前，一直都是curDistFromStart == distTo[curNodeID]吧。。不知道我的理解对不对 while (!pq.isEmpty()) {
State curState = pq.poll();
int curNodeID = curState.id;
int curDistFromStart = curState.distFromStart;
if (curDistFromStart > distTo[curNodeID]) {
// 已经有一条更短的路径到达 curNode 节点了
continue;
}
// 将 curNode 的相邻节点装入队列
for (int nextNodeID : adj(curNodeID)) {
// 看看从 curNode 达到 nextNode 的距离是否会更短
int distToNextNode = distTo[curNodeID] + weight(curNodeID, nextNodeID);
if (distTo[nextNodeID] > distToNextNode) {
// 更新 dp table
distTo[nextNodeID] = distToNextNode;
// 将这个节点以及距离放入队列
pq.offer(new State(nextNodeID, distToNextNode));
}
}
} |
Beta Was this translation helpful? Give feedback.
-
|
node1 第一次 push heap, 假設路徑是10 第二次經過 node1, 發現 路徑是5 現在 heap 內部, 有兩筆 node1 的資料 node1 第一次 pop 不滿足上述判斷式, 可以繼續尋訪鄰接節點 判斷式, 其實就是 visited 的功能 |
Beta Was this translation helpful? Give feedback.
-
|
谢大佬,终于懂了 |
Beta Was this translation helpful? Give feedback.
-
|
打卡，又是精神进化的一天2333 |
Beta Was this translation helpful? Give feedback.
-
1514. Path with Maximum Probability (Python3 version)import heapq
from typing import Any
class Solution:
def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
graph = [[] for _ in range(n)]
# construct the graph
for i in range(len(edges)):
f, t = edges[i][0], edges[i][1]
w = succProb[i]
graph[f].append([t, w])
graph[t].append([f, w])
return self.dijkstra(start, end, graph)
def dijkstra(self, start:int, end:int, graph:List[List[Any]]) -> float:
# Definition: proTo[i] is the maximum probability from the start node to the node i
# Set the initial value as -1
probTo = [-1 for _ in range(len(graph))]
# Base case, the probability from start to start is 1
probTo[start] = 1
# Priority Queue, the priority order is the bigger prob_from_start
# Definition of State: [id, prob_from_start]
pq = []
heapq.heappush(pq, (1, [start, 1]))
while pq:
cur_state = heapq.heappop(pq)[1]
cur_node_id, cur_prob_from_start = cur_state[0], cur_state[1]
# Return cur_prob_from_start if reach the end point
if cur_node_id == end:
return cur_prob_from_start
# Continue, if there is already a bigger probability
if probTo[cur_node_id] > cur_prob_from_start:
continue
# Push adjacent nodes into the Priority Queue
for neighbor in graph[cur_node_id]:
next_node_id = neighbor[0]
# Check if there is a bigger probability from cur_node_id to next_node_id
prob_to_next_node = probTo[cur_node_id] * neighbor[1]
if prob_to_next_node > probTo[next_node_id]:
probTo[next_node_id] = prob_to_next_node
# By the default in Python, the heap queue is a min heap.
# If we want to order the heap queue as max heap, add a negative symbol in your priority order
heapq.heappush(pq, (-prob_to_next_node, [next_node_id, prob_to_next_node]))
return 0.0 |
Beta Was this translation helpful? Give feedback.
-
|
heappush用法 heapq.heappush(heap, (priority order, value)) |
Beta Was this translation helpful? Give feedback.
-
|
1631题看的有点迷（感觉是题意还是不太了解），剩余两题还好，看完都能写出来， |
Beta Was this translation helpful? Give feedback.
-
|
1631题，有两个问题，有大神可以帮忙回答一下吗？
|
Beta Was this translation helpful? Give feedback.
-
|
明白啦 ，因为题目里effort定义是 A route's effort is the maximum absolute difference in heights between two consecutive cells of the route ！ |
Beta Was this translation helpful? Give feedback.
-
|
最小体力消耗这道题的退出条件为啥是第一次遇到右下角节点就退出了呢，其他节点都是可能重复入队来最小化问题的，为啥最后一个节点直接就返回了？ |
Beta Was this translation helpful? Give feedback.
-
|
我们需要思考curX和curY的值是怎么来的，很明显他们都是从pq里面poll出来的，那也就是说curX（假如curX=4）和curY（假如curY=5）的值在上一轮或者上几轮循环里是以邻居节点的身份offer到pq里的，在while循环里有一个判断语句: 言归正传，如果这个if语句成立，就会进行两个操作，第一，将effortTo[nextX][nextY]更新为更小的值，第二，会声明一个State对象，里面带有nextX（nextX=4）和nextY（nextY=5）以及对应的最小值effortToNextNode（假如为13）。当然此时的pq里可能（我说的是可能）已经存在nextX（nextX=4）和nextY（nextY=5）对应的另一个值effortToNextNode1（假如为14，反正肯定比13要大，不可能比13小，如果比13小的话，那么这个13根本就不可能offer到pq里，因为if语句不成立），由于if语句的成立，所以肯定有effortToNextNode 小于 effortToNextNode1。根据优先级队列自动排序的功能，所以当循环执行到int curX=curState.x（等于4）和 int curY=curState.y（等于5），int curEffortFromStart = curState.effortFromStart（等于13）时，取出的curEffortFromStart这个值，一定是curX（等于4）和curY（等于5）所对应的最小值（等于13）了。当然随着while循环继续遍历下去，后面也会把curX（等于4）和curY（等于5）以及curEffortFromStart（等于14）取出来，不过会被continue掉。 只要理解这个过程，你就能理解为啥第一次等于m-1和n-1时就直接返回了。 |
Beta Was this translation helpful? Give feedback.
-
|
如果最后想输出所有的路径有什么改进思路吗 |
Beta Was this translation helpful? Give feedback.
-
|
cpp dijkstra 框架，优先队列的比较函数有错误，应该是小于号变成小堆。 |
Beta Was this translation helpful? Give feedback.
-
|
我对这块代码的一些理解： if (curDistFromStart > distTo[curNodeID]) {
// 已经存在一条更短的路径，无需继续处理当前路径
// 这里刚开始有很大的疑问，continue了的话，他的邻居怎么办？？？
//实际上，如果出现curDistFromStart > distTo[curNodeID]的情况，说明这个节点曾经被另外的路径所遍历到并更新了distTo数组里的值，
//与此同时在后面的代码pq.offer(new State(nextNodeID, distToNextNode));，还会将更新的值再次入队，还是同样的id。
//由于是优先级队列，这个新入队的值会在目前遍历到的这个curState的前面遍历到，并在那时已经处理好了邻居节点，所以当前这个curState是一个没有用的废节点了。
continue;
} |
Beta Was this translation helpful? Give feedback.
and others
-
文章链接点这里：我写了一个模板，把 Dijkstra 算法变成了默写题
评论礼仪 见这里，违者直接拉黑。
Beta Was this translation helpful? Give feedback.
All reactions