Dijkstra 算法伪代码混淆
Dijkstra's Algorithm Pseudocode Confusion
我正在尝试针对旅行商问题实现 Dijkstra 算法的一个版本，我发现了这篇论文：https://www.researchgate.net/figure/Dijkstras-algorithm-for-many-targets-with-a-pruning-heuristic-An-upper-bound-B-for-d-v_fig2_257428759
我理解算法，但我对 'free' 在此伪代码中的含义感到困惑。谁能给我解释一下？
即在以下行中：
如果你有空就停止 fl
如果 v 是空闲的那么 B = min{c, b} fl
A Heuristic for Dijkstra's Algorithm with Many Targets (Pseudocode)
您 link 的论文似乎没有处理旅行商问题，而是处理二分匹配：
Both versions of the problem can be solved by solving
n,n=max(|A|,|B|), single-source many-targets shortest-path (SSMTSP)
problems in a derived graph, see Section 4.
一个free节点是指与二分图中任何其他节点都不匹配的节点。这在 linked 论文的第 4 节（页面标签 87）脚注 5:
中说明
A node is free if no edge in M is incident to it.
M定义为上一页需要计算的匹配
这个算法好像只对这个匹配问题有用，需要你运行多次。这只是对二分匹配的多个 运行s 的改进，它不是一个独立的算法。
我正在尝试针对旅行商问题实现 Dijkstra 算法的一个版本，我发现了这篇论文：https://www.researchgate.net/figure/Dijkstras-algorithm-for-many-targets-with-a-pruning-heuristic-An-upper-bound-B-for-d-v_fig2_257428759
我理解算法，但我对 'free' 在此伪代码中的含义感到困惑。谁能给我解释一下？
即在以下行中：
如果你有空就停止 fl
如果 v 是空闲的那么 B = min{c, b} fl
A Heuristic for Dijkstra's Algorithm with Many Targets (Pseudocode)
您 link 的论文似乎没有处理旅行商问题，而是处理二分匹配：
Both versions of the problem can be solved by solving n,n=max(|A|,|B|), single-source many-targets shortest-path (SSMTSP) problems in a derived graph, see Section 4.
一个free节点是指与二分图中任何其他节点都不匹配的节点。这在 linked 论文的第 4 节（页面标签 87）脚注 5:
A node is free if no edge in M is incident to it.
M定义为上一页需要计算的匹配
这个算法好像只对这个匹配问题有用，需要你运行多次。这只是对二分匹配的多个 运行s 的改进，它不是一个独立的算法。